Compu abili y and Complexi y o
opinion dynamics
Compu abilidad y Complejidad de la din´
amica de
opiniones
Bachelo ’s Thesis (T abajo de Fin de G ado)
Academic yea : 2022 - 2023
Au ho
Ma ´ın G´omez Abej´on
Di ec o s
Ismael Rod ´ıguez Laguna
Fe nando Rubio Diez
Doble G ado en Ingenie ´
ıa In o m´
a ica -
Ma em´
a icas
Facul ad de In o m´
a ica
Uni e sidad Complu ense de Mad id
Con en s
1 In oduc ion 4
1.1 Theo e ical amewo k ............................. 4
1.1.1 Spacecomplexi y............................ 5
1.1.2 A s anda d model used o opinion dynamics . . . . . . . . . . . . . 6
1.1.3 Real-wo ld social g aphs . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Objec i es and me hodology . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 No a ion used in his wo k . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 De ini ion o he gene al p oblem 10
2.1 Gene al de ini ion o opinion g aphs . . . . . . . . . . . . . . . . . . . . . . 10
2.2 G aphs based on la ices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 The de e minis ic p oblem is inc easing . . . . . . . . . . . . . . . . . . . . 16
3 Complexi y p ope ies o opinion g aphs 20
3.1 Opinion g aphs a e unc ionally comple e . . . . . . . . . . . . . . . . . . . 20
3.2 Building a Tu ing machine wi h opinion g aphs . . . . . . . . . . . . . . . 23
3.3 Decidabili y and complexi y p ope ies o opinion g aphs . . . . . . . . . . 33
4 Heu is ic analysis o eal-wo ld g aphs 43
4.1 Thep oblemweconside ............................ 43
4.2 Basic s a egies o sol e he p oblems and ob ained esul s . . . . . . . . . 45
4.2.1 Gene al compa ison . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.2 Benchma ks o he bes basic s a egy . . . . . . . . . . . . . . . . 47
4.3 Using a gene ic algo i hm . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5 Conclusion 51
1
Abs ac
In his wo k, we discuss and p o e se e al heo e ical esul s ela ed o compu abili y
and complexi y p ope ies o an opinion dynamics model we de ine. We also y o ind
low-complexi y heu is ics and algo i hms which le us ob ain app oxima e solu ions o an
NP-comple e p oblem based on ou model, and un simula ions o de e mine o wha
ex en hese heu is ics a e e ec i e. Al hough we conclude ha mos p ac ical p oblems
ela ed o ou model a e undecidable in he in ini e case and PSPACE-comple e o NP-
comple e in he ini e case, he ob ained low-complexi y algo i hms a e e ec i e a sol ing
ins ances whose s uc u e and p ope ies a e simila o hose o eal-wo ld examples.
Keywo ds
Complexi y, app oximabili y, PSPACE-comple eness, undecidabili y, heu is ics, g eedy
algo i hms, gene ic algo i hms.
2
Resumen
En es e abajo, se abo dan y demues an a ios esul ados e´o icos elacionados con las
p opiedades de compu abilidad y complejidad de un modelo de din´amica de opiniones
que de inimos. Tambi´en in en amos encon a heu ´ıs icas y algo i mos de baja comple-
jidad que nos pe mi an ob ene soluciones ap oximadas de un p oblema NP-comple o
basado en nues o modelo, y ejecu amos simulaciones pa a de e mina en qu´e medida
es as heu ´ıs icas son e ec i as. A pesa de que concluimos que la mayo ´ıa de p oblemas
p ´ac icos elacionados con nues o modelo son indecidibles en el caso in ini o y PSPACE-
comple os o NP-comple os en el caso ini o, los algo i mos de baja complejidad ob enidos
son e ec i os esol iendo ins ancias cuya es uc u a y p opiedades son pa ecidas a las de
ejemplos del mundo eal.
Palab as cla e
Complejidad, ap oximabilidad, PSPACE-comple i ud, indecibilidad, heu ´ıs icas, algo-
i mos o aces, algo i mos gen´e icos.
3
1 In oduc ion
In his wo k we use g aphs o model opinion dynamics, discuss he complexi y o he model
we use and es ima e o wha ex en eal-wo ld g aphs which ep esen acquain ances can
be p ocessed by e icien enough algo i hms o ob ain ele an in o ma ion.
S udying opinion dynamics has many applica ions in mode n socie y, since modi ying
he opinion o la ge g oups o people can modi y hei beha iou and ha e impo an
consequences, such as an inc ease in sales, an unexpec ed elec ion esul o a beha iou al
change. The e o e, a lo o esou ces a e spen e e y yea by a ious en i ies in o de o
change people’s opinion on a ce ain subjec . In o ma ion and echniques o making his
ask easie a e e y aluable. This wo k p o ides ce ain insigh in o in luencing opinion
dynamics, so i can be di ec ly used, helping o achie e be e esul s.
As pa o his wo k, we ha e analysed how di icul his ask is. We ha e also p oposed,
es ed and compa ed a ious echniques o changing people’s opinion using limi ed e-
sou ces. These echniques can be applied in eal-wo ld cases i enough in o ma ion is
known abou he g oup o people whose opinion needs o be changed. Pe o mance esul s
o all p oposed echniques ha e been empi ically es ed by using g aphs o acquain ances
whose design makes hem e y simila o eal-wo ld g aphs o acquain ances. This is done
o ensu e empi ical conclusions can be applied, since hese conclusions migh be di e en
i he used g aphs a e no simila o eal-wo ld ins ances.
In o de o ollow wha has been done in his wo k, he eade needs o be amilia wi h
ce ain ele an heo e ical no ions and esea ch ela ed o his opic. In his i s sec ion,
we b ie ly discuss his necessa y backg ound. The e e ences we use a e sel -con ained and
app op ia e o eade s who a e no amilia ised wi h any o he opics. We delibe a ely
choose no o discuss concep s which a e pa o he syllabus o any Bachelo ’s deg ee in
Compu e Science, such as he classes Pand NP. All his omi ed heo y can be ound
in [11]. I can also be ound in [4], al hough he con en s o [4] a e much b oade han
hose o [11].
The heo e ical esul s we ob ain a e a he discou aging; p oblems ela ed o in ini e
opinion g aphs a e no decidable, and o ini e opinion g aphs mos in e es ing p oblems
a e ei he NP-comple e o PSPACE-comple e. Howe e , by using g eedy algo i hms
and gene ic s a egies, we a e able o ob ain good solu ions o a p oblem which is NP-
comple e in gene al. The e o e, sol ing p oblems ela ed o opinion dynamics in eal-wo ld
con ex s is easible, e en i he ob ained solu ions migh no be op imal.
1.1 Theo e ical amewo k
We now discuss all non-s anda d p e equisi es we need o his wo k. This p e equisi es
consis o h ee majo blocks. One o hem co e s ce ain aspec s o ad anced complexi y
and compu abili y heo y, while he la e wo a e ela ed o how opinion dynamics a e
modelled wi h g aphs, and which is he bes app oach o ob ain ealis ic g aphs which
a e opologically simila o eal-wo ld ne wo ks o acquain ances.
4

1.1.1 Space complexi y
We b ie ly explain he no ions we need o know abou space complexi y in o de o s udy
how complex opinion dynamics a e. The concep s we discuss ha e been ex ac ed om [4].
Space complexi y is no s udied as pa o a s anda d Bachelo ’s deg ee. Jus like wi h
ime complexi y, we can de ine classes o p oblems which can be sol ed i a ce ain amoun
o space is gi en. Namely, we ha e he ollowing de ini ions.
De ini ion 1 (Space-bounded compu a ion).A language L, o i s co esponding p oblem
P, is said o belong o SPACE(s(n)) i he e is a cons an Cand a de e minis ic Tu ing
machine Mwhich decides L, hus sol ing P, such ha no mo e han C·s(n)di e en
cells a e e e isi ed by M’s head when he leng h o he inpu equals n.
We simila ly de ine he class NSPACE;L∈NSPACE(s(n)) i he e is a cons an C
and a non-de e minis ic Tu ing machine Mwhich decides L, such ha no mo e han
C·s(n)di e en cells a e e e isi ed by M’s head when he leng h o he inpu equals n,
o any se o non-de e minis ic choices aken by M.
Time and space complexi y a e ela ed o each o he , since a Tu ing machine which uns
o cycles canno isi mo e han cells, and he numbe o di e en possible global
con igu a ions o a Tu ing machine Mwhich does no isi mo e han ccells is bounded
by K1·Kc
2, o ce ain K1, K2which depend on M.
Theo em 1 (Time and space complexi y).The ollowing se inclusions hold.
DTIME(s(n)) ⊆SPACE(s(n)) ⊆NSPACE(s(n)) ⊆DTIME 2O(s(n))
A igo ous p oo o his esul can be ound in [4]. The mos ele an space complexi y
classes in his wo k a e
PSPACE de
=[
c∈N
SPACE(nc) and NPSPACE de
=[
c∈N
NSPACE(nc)
which in ui i ely consis s o all p oblems which can be sol ed using a polynomial amoun
o space. Jus like o NP, he e exis s a no ion o comple eness, which we now de ine.
Jus like in [4], we use he symbol ≤p o polynomial- ime Ka p educibili y.
De ini ion 2 (PSPACE-comple eness).A language L′is said o be PSPACE-ha d i
and only i ∀L∈PSPACE,L≤pL′. I L′is PSPACE-ha d and L′∈PSPACE, i is
said o be PSPACE-comple e.
I can be p o ed ha he language
Laccsp
de
={(M, w, 1n)|Maccep s win space n}(1)
is PSPACE-comple e, whe e M ep esen s a a iable semi-in ini e ape Tu ing machine.
O cou se, i is indispensable ha he e exis s a well-de ined encoding which can be used
o ep esen e e y possible Min a s ing. I is s anda d o assume ha his encoding
makes i possible o use polynomial- ime algo i hms o encoding and decoding o use in a
uni e sal Tu ing machine; o ce ain encodings o which in ini ely many wo ds ep esen
5
Tu ing machines whose numbe s o s a es a e no bounded by a mul iple o a powe o
he leng h o he s ings, he exis ence o hese polynomial- ime algo i hms canno be
gua an eed. We use he same cons uc ion and assump ions as in [4]; polynomial- ime
algo i hms exis , since Tu ing machines a e encoded by lis ing he able o hei ansi ion
unc ions.
We make some addi ional ema ks which a e ele an o his wo k. I is almos im-
media e o p o e Laccsp is PSPACE-comple e i one is amilia enough wi h PSPACE.
Ne e heless, i is no a sa is ying PSPACE-comple e language, since i does no gi e
any in ui ion abou wha a PSPACE-ha d p oblem looks like. A be e example o a
PSPACE-comple e p oblem is he language o all quan i ied Boolean o mulas which a e
ue. A quan i ied Boolean o mula has he s uc u e
Q1x1Q2x2. . . Qnxnφ(x1, x2, . . . , xn),(2)
whe e ∀i∈Nn, Qi∈ {∀,∃} and φ(x1, x2, . . . , xn) is a p oposi ional logic o mula on
a iables x1, x2, . . . , xn. A p oo o he PSPACE-comple eness o his p oblem can be
ound in [4].
This PSPACE-comple e p oblem p o ides mo e insigh ; since he quan i ie s can appea
in any o de and al e na e as equen ly as needed, i is possible o use o mulas like
(2) o encode (possibly non-de e minis ic) wo-playe games. Each ∀ ep esen s a choice
aken by he opponen , o a andom e en which akes place in he game, while each ∃
ep esen s a olun a y choice aken by he playe . One o hese o mulas is ue i and
only i he e exis s a s a egy which leads o ic o y1.
We inally s a e one las p ope y wi hou p o ing i ; PSPACE =NPSPACE. I is
a di ec consequence o Theo em 1 om [16], which s a es ha i s(n)≥log(n), hen
NSPACE(s(n)) ⊆SPACE(s(n)2).
1.1.2 A s anda d model used o opinion dynamics
Many di e en models ha e been used o y o model human in e ac ions and how a
pe son’s opinion is de e mined depending on hei en ou age and hei own ini ial opin-
ion. The as majo i y o hese models a e con inuous s ochas ic p ocesses in which an
indi idual opinion is upda ed using a s ochas ic ansi ion unc ion which akes he ini ial
opinion o a pe son and i s in e ac ions wi h o he s in o accoun .
A e y used model o his pu pose is he o e model om [13]. This model is a con inuous
ime Ma ko p ocess in which nodes in a la ice (Zd) in e ac wi h each o he locally.
Nodes can ag ee (1) o disag ee (0), and he ansi ion a es o each node a e gi en by
a unc ion c(x, η), whe e xis a posi ion in Zdand η∈ {0,1}Zdis he cu en s a e o he
whole la ice. The highe cis o a speci ic node xa a gi en poin in ime, he mo e
likely i is ha he opinion o xchanges. cis assumed o ha e he ollowing p ope ies.
(1) Le η1and η0be he s a es in which e e y node ag ees o disag ees, espec i ely.
1I (2) is hough o as a game, ic o y is encoded in φ(x1, x2, . . . , xn), and he game which is played
goes as ollows: om le o igh , a playe de e mines he alue o all ∃quan i ie s, while he opponen
de e mines he alue o all ∀quan i ie s. The ul ima e goal o he playe is o make φ(x1, x2, . . . , xn)
ue, while he opponen ies o make φ(x1, x2, . . . , xn) alse.
6
Then, ∀x∈Zd, c(x, η1) = c(x, η0) = 0. This means nodes keep ha ing he same
opinion i no o he node disag ees wi h hem.
(2) Opinions a e symme ic; ansi ion a es a e he same i he opinions o all nodes
a e lipped. Quan i a i ely, c(x, ηα) = c(x, ηβ) i ∀y∈Zd, ηα(y) + ηβ(y) = 1.
(3) T ansi ion a es o a speci ic node xa e highe when nodes uni o mly disag ee
mo e wi h x. The wo d uni o mly is e y impo an in his p ope y; since i is
no known o wha ex en each indi idual node in luences x, no hing can be said
abou he global change o he ansi ion a e o xi some o he nodes s a o
disag ee wi h x, while o he s s a o ag ee. This p ope y can be exp essed using
wo equi alen equa ions.
I ∀y∈Zd, ηα(y)≤ηβ(y) and ηα(x) = ηβ(x) = 0, hen c(x, ηα)≤c(x, ηβ).
I ∀y∈Zd, ηα(y)≤ηβ(y) and ηα(x) = ηβ(x) = 1, hen c(x, ηα)≥c(x, ηβ).
(4) The ansi ion a es a e in a ian unde ansla ions in Zd; i he opinions o all nodes
a e ansla ed using a ec o , he ansi ion a es can be ob ained by ansla ing
he o iginal ansi ion a es using as well.
Despi e he name o his model, i was o iginally no concei ed o modelling opinion
dynamics. Howe e , i has been shown ha modi ied e sions o his model can accu a ely
desc ibe opinion dynamics in eal-wo ld con ex s (see [8]). Howe e , he o iginal model
om [13] has an issue; he g aph opology used (a la ice) and he p ope ies o ansi ion
a es, especially being in a ian unde ansla ion, make he model e y di e en om
eal-wo ld social ne wo ks, as we will see. Fo ins ance, in [8], he g aph o in e ac ions
which is conside ed is e y di e en om he o iginal g aph p oposed in [13].
In his wo k, we ha e analysed he complexi y o a modi ied o e model; ins ead o being
a con inuous p ocess, i is disc e e. Also, i is de e minis ic, unlike almos any o he o e
model o a ian he eo which has p e iously been conside ed by o he au ho s. Ce ain
de e minis ic models ha e been conside ed by ce ain au ho s, such as in [7], bu hey
a e e y di e en om he model we conside in his wo k. We analyse he complexi y
and exp essi eness o his de e minis ic model, which has ne e been done be o e in his
con ex , o he bes o ou knowledge. Due o he law o la ge numbe s, i can be assumed
ha a de e minis ic model is capable o simula ing global p ope ies o opinion dynamics.
1.1.3 Real-wo ld social g aphs
The o e model discussed in [13] and i s a ian s ha e been used in many di e en
ne wo k opologies. Examples o his a e [8], as well as [17], [14] and [5]. Mos au ho s do
no conside ne wo ks which a e simila o eal-li e social in e ac ion g aphs. In [8], his
is done success ully, bu no all ea u es o eal-li e g aphs, such as a e age sho es pa h
leng h and deg ee dis ibu ion (see below), a e conside ed. In [17], he conside ed g aphs
a e e y di e en om eal-li e, as hey a e no spa se and hei clus e ing coe icien s (see
below) a e di e en om eal-li e coe icien s like hose ob ained in [3]. In his wo k, we
conside all ele an p ope ies o social ne wo ks when modelling hem. We now discuss
he mos ele an p ope ies.
7
Al hough he dynamics o many o e models and o he games ha e been conside ed o
la ices (apa om he o e model, he e a e o he examples in o he con ex s, such
as [6] and [15], in which no only Znis conside ed), i has been shown by many au ho s
(see, o example, [3] and [9]) ha la ices a e e y di e en om eal-li e social ne wo ks.
In [3], many di e en examples a e s udied and h ee impo an p ope ies a e deduced.
(1) The a e age sho es pa h leng h is e y small, and g ows loga i hmically compa ed
o he numbe o nodes in he ne wo k. Random g aphs (whose edges a e de e mined
andomly and independen ly) ha e his p ope y. G aphs which ha e his p ope y
a e known as small-wo ld ne wo ks.
(2) The clus e ing coe icien is ela i ely high compa ed o andom g aphs. This coe -
icien is ob ained o each node by conside ing i s neighbou s and calcula ing he
p opo ion o edges be ween hem ha exis . When he alue o his coe icien is 1,
he neighbou s o m a comple e g aph, and when i is low, i is highly unlikely ha
neighbou s know each o he . The a e age alue o hese coe icien s is he clus e ing
coe icien o he g aph.
(3) The dis ibu ion o node deg ees ollows a powe law. This was s udied in [3] and
ela ed pape s. In o de o ob ain such a ne wo k, edges need o be added by gi ing
mo e p obabili y o nodes which a e al eady e y connec ed. A model which akes
his app oach is he Ba ab´asi-Albe model discussed in [3].
I has been shown in [18], as well as in [3], ha combining di e en ypes o edges co e-
sponding o la ices and mo e global edges, chosen andomly o depending on he deg ee
o he nodes, yields ne wo ks which sa is y all o he p ope ies discussed abo e. The e
exis o he models o p ope ies which cha ac e ise eal-li e social ne wo ks, which ha e
been discussed in pape s like [9] and [12], bu hese o he app oaches a e e y simila o
he one aken in [3].
1.2 Objec i es and me hodology
In his wo k, we iden i y and p o e he mos impo an complexi y p ope ies o a de-
e minis ic model we de ine. This model is based on he o e model om [13], bu i is
modi ied by making i de e minis ic and disc e e, and modi ying i s opology by consid-
e ing la ices o blocks o nodes, ins ead o la ices o nodes. We conside each block o
be a communi y which is in luenced by nea by communi ies. I is ue ha he a e age
sho es pa h leng h o his model emains high, as in he o iginal o e model. Ne e -
heless, i is use ul o p o ing wo s -case complexi y p ope ies, and we will la e modi y
i o make i mo e ealis ic when analysing i s beha iou in eal-wo ld condi ions.
Despi e he wo s -case complexi y p ope ies we ob ain, we y o simula e eal-wo ld ex-
amples o his model and use heu is ic algo i hms in o de o e alua e o wha ex en hese
can gi e sa is ying answe s o p oblems whose exac solu ions canno be ob ained easily.
Fo his pa o he wo k, we conside g aphs which a e as simila o eal-wo ld social
g aphs as possible using he p ope ies discussed abo e, and conside di e en heu is ic
algo i hms o sol e p oblems ela ed o hese g aphs. Addi ional in o ma ion abou he
me hodology used o hese simula ions and algo i hms can be ound in Sec ion 4.
8
edges whose des ina ion is Ip( ).
A g aph is said o be connec ed as successo o an in e ace Ii he same condi ions o
connec ion as p edecesso , in e changing he oles o ↑and ↓, apply o a gi en injec i e
unc ion Is:Nk→V.
The nodes which belong o he image o Ipa e called phan om nodes.
When i is no known i he block is connec ed as a successo o as a p edecesso , we use
he no a ion Ip,s o he injec i e unc ion which ma ks phan om nodes. In De ini ion 3,
he unc ion Ip,s uniquely assigns a phan om node o each connec ion. Condi ions (2)
and (3) me ely s a e ha he edges which connec phan om nodes o o he nodes should
beha e as in ended by he in e ace I. I I( ) =↑, he phan om node Ip,s( ) beha es as a
ube lea ing he p edecesso and en e ing he successo . On he o he hand, i I( ) =↓, he
phan om node Ip,s( ) beha es as a ube lea ing he successo and en e ing he p edecesso .
De ini ion 4 makes i possible o connec se e al in e aces o a single block. In o de
o ha e a consis en de ini ion which can be used o in e connec blocks in an L-shaped
g aph, phan om nodes mus be di e en o each connec ion o an in e ace and hey
canno in e e e wi h each o he . The la e condi ion is qui e impo an in o de o
gua an ee all connec ions a e local and he L-shaped g aph is well de ined.
De ini ion 4 (Opinion g aph connec ed o mul iple in e aces).An opinion g aph G=
(V, E)is said o be connec ed o mul iple in e aces {Ij}j∈J ia he unc ions {Ij
p,s}j∈Ji
i is connec ed o each in e ace Ij ia he unc ion Ij
p,s and he ollowing condi ions a e
sa is ied.
(1) The images o he injec i e unc ions {Ij
p,s}j∈Ja e pai wise disjoin .
(2) The e is no edge whose sou ce sand des ina ion da e in he union o he image
se s o {Ij
p,s}j∈J.
The co e Gco a g aph Gwhich is connec ed o mul iple in e aces {Ij}j∈J ia he unc-
ions {Ij
p,s}j∈Jconsis s o he g aph G, om which all phan om nodes o all in e aces and
all edges which lea e o en e phan om nodes ha e been emo ed.
In gene al, he co e o a gi en block is no an opinion g aph, since he sum o he weigh s
o he in luen ial edges o each node is no necessa ily 1 a e emo ing some o hem.
Howe e , he sum o he weigh s becomes 1 again when he co e is connec ed o o he
co es in an L-shaped g aph.
We now ha e enough ools o o mally de ine wha an L-shaped g aph is, gi en an a bi a y
L. This de ini ion o malises he concep s discussed abo e.
De ini ion 5 (L-shaped g aph).Gi en L=E1×E2× · · · × Ed, an L-shaped g aph is
comple ely de e mined by he ollowing de ini ions:
(1) In e aces {Ij}j∈Nd o each o he ddimensions o L.
(2) Fini e opinion g aphs GR o all R∈Rel(L). I is necessa y ha hese g aphs be
connec ed o he ollowing in e aces.
15

(a) Fo all elemen s R∈Rel(L)and all j∈Nd, i he j- h elemen o Ris no
Ls , hen GRmus be connec ed o Ijas a p edecesso .
(b) Fo all elemen s R∈Rel(L)and all j∈Nd, i he j- h elemen o Ris no
Fs , hen GRmus be connec ed o Ijas a successo .
The L-shaped g aph Gco esponding o hese de ini ions consis s o he disjoin union o
he g aphs Gl∼
=Gc
Rel(l) o each l∈L, which a e in e connec ed by adding he ollowing
edges.
Fo all j∈Nd, e = (e1, e2, . . . , ej−1, ej, ej+1, . . . , ed)∈L, gi en Ij:Nk→ {↑,↓}, i
ej+de
= (e1, e2, . . . , ej−1, ej+ 1, ej+1, . . . , ed)∈L, hen an edge is added o he L-shaped
g aph as ollows o each ∈Nk.
(1) I Ij( ) =↑, i s sou ce is he node o iginally connec ed o Ij
p( )in Gc
e, i s des ina ion
is he node o iginally connec ed o Ij
s( )in Gc
ej+and i s weigh is he one o he only
non- e lexi e edge whose sou ce is Ij
s( )in GRel(ej+).
(2) I Ij( ) =↓, i s sou ce is he node o iginally connec ed o Ij
s( )in Gc
ej+, i s des ina-
ion is he node o iginally connec ed o Ij
p( )in Gc
eand i s weigh is he one o he
only non- e lexi e edge whose sou ce is Ij
p( )in GRel(e).
Each o he g aphs Glis called a block.
When cons uc ing Gby ollowing his de ini ion, i is gua an eed ha he sum o he
weigh s o all edges o in ( i)equals 1, o all ∈G. Howe e , he e migh be edges
wi h common sou ce and des ina ion i a node in GRin luences o is in luenced by se e al
phan om nodes o an in e ace unc ion Ip,s. I his happens, all hese edges a e emo ed
and eplaced by a single edge whose sou ce and des ina ion a e he ones o he emo ed
edges, and whose weigh is he sum o he weigh s o he emo ed edges.
Blocks a e in e connec ed in De ini ion 5 by connec ing he wo sides o in e aces o
which con iguous blocks a e connec ed. Figu e 5 shows how de ining wo in e aces and
six g aphs which a e connec ed o hose in e aces ollowing a {Fs ,Mid}×{Fs ,Mid,Ls }
a angemen cha ac e ise he N×N6-shaped g aph depic ed in Figu e 3 ia De ini ion 5.
The eade can also ha e a look a Figu e 6, which p o ides in ui ion in how blocks a e
connec ed o each o he and how edge weigh s a e assigned.
2.3 The de e minis ic p oblem is inc easing
In ui i ely, he ansi ion unc ion we ha e de ined o he gene al ins ance o an opinion
g aph is inc easing when es ic ed o a speci ic node, and i s p ope ies a e simila o
hose o inc easing unc ions in gene al. We will now de ine hese concep s mo e p ecisely
and show how hey limi ce ain exp essi eness p ope ies o he de e minis ic e sion o
he p oblem. Gi en an opinion g aph G= (V, E),
LG
de
={S:V7→ {0,1}}
deno es he se o all possible labellings o G.
16
12
1
2
12
11
22
12
1
1
2
2
12
1
11
2
22
1
1
2
2
1
11
2
22
Figu e 5: De ini ions o he six necessa y ypes o g aphs used o de ine he g aph om
Figu e 3. Re lexi e edges and he weigh s o all edges a e no shown.
17
10.6
0.3
1
0.4
1
10.8
0.6
0.3
0.4
0.8
0.6
0.3
0.4
0.8
0.6
0.3
0.4
0.8
0.6
0.3
0.4
0.8
0.6
0.3
0.4
0.8
0.6
0.3
0.4
0.8
0.6
0.3
0.4
0.8
0.6
0.3
0.4
0.8
0.6
0.3
0.4
0.8
Figu e 6: De ini ion o G(Mid,Mid)on he le and pa o he esul ing Z×Z-shaped g aph
on he igh . Re lexi e edges and some o he weigh s a e no shown. The weigh s o
connec ions o an in e ace which lea e he block always equal 1 in GRby de ini ion, and
hey a e eplaced by he weigh s o incoming connec ions when cons uc ing an L-shaped
g aph, as i can be seen on he igh .
De ini ion 6 (pa ial o de on LG).Gi en an opinion g aph G= (V, E)we de ine a
pa ial o de on he unc ions LGby de ining
Sα≤Sβde
⇐⇒ ∀ ∈V, Sα( )≤Sβ( ).
This way we pa ially o de he possible s a es o he g aph G; he de ini ion o he pa ial
o de implies ha Sα≤Sβwhen and only when all node labels in Sαa e lowe han o
equal o he co esponding labels in Sβ.
We now gi e ano he de ini ion which na u ally ex ends he concep o inc easing unc ions
o he pa ial o de in LG.
De ini ion 7 (inc easing unc ions LG7→ LG).Gi en an opinion g aph G= (V, E), a
unc ion :LG7→ LGis inc easing i and only i
∀Sα, Sβ∈LG, Sα≤Sβ=⇒ (Sα)≤ (Sβ).
The ollowing heo em has a lo o consequences and signi ican ly educes he exp essi e-
ness o opinion g aphs. E en hough we will la e p o e opinion g aphs a e essen ially
Tu ing-comple e, his heo em implies we need o be ca e ul when de ining he ins ances;
in p ac ice, we will need o cons uc pai wise non-compa able ins ances in o de o gua -
an ee ha hey a e di e en enough.
Theo em 2. Gi en an opinion g aph G= (V, E), he ansi ion unc ion which maps
a ce ain s a e o labels in G(S ) o he nex s a e (S +1) is inc easing.
18
P oo . Le Sα
, Sβ
∈LGand assume Sα
≤Sβ
. F om he de ini ion o ≤we need o p o e
ha gi en any e ex j∈V,Sα
+1( j)≤Sβ
+1( j). The inequali y
X
i∈in l( j)
Sα
( i)|eij| ≤ X
i∈in l( j)
Sβ
( i)|eij|
is sa is ied because Sα
( i)≤Sβ
( i)∀ i, he weigh s o he edges a e non-nega i e and
inequali ies a e p ese ed by sums. The unc ion
Sα
+1( j) = 




0,i P i∈in l( j)Sα
( i)|eij|<1
2,
Sα
( j),i P i∈in l( j)Sα
( i)|eij|=1
2,
1,i P i∈in l( j)Sα
( i)|eij|>1
2,
seen as a unc ion whose a gumen s a e P i∈in l( j)Sα
( i)|eij|and Sα
( j), is inc easing6.
Tha implies each indi idual ou pu o he unc ion Sα
+1 in unc ion o Sα
is inc easing,
which in u n implies he global ansi ion unc ion is inc easing.
Two co olla ies can be easily deduced om he p e ious heo em. Thei p oo s a e i ial
and no pa icula ly ele an o he es o he ex , so we lis hem o comple eness
wi hou p o ing hem.
Co olla y 1 (inequali ies ela ing ins ances p ese ed).Gi en a g aph Gand wo in-
s ances S= (G, S0), T = (G, T0), i S0≤T0 hen
∀ ∈Z≥0, S ≤T .
Co olla y 2 (inc easing sequences o labels con e ge).Gi en an ins ance o he p oblem
S= (G, S0), i S1≥S0 hen Sn1≥Sn2whene e n1≥n2. This implies ha o each
node i, he sequence o i s labels { i( )} is e en ually cons an , al hough he con e gence
is no necessa ily uni o m7 o all nodes.
These co olla ies ha e nume ous impo an consequences; o ins ance, Co olla y 1 implies
NOT-ga es canno be simula ed by choosing a speci ic g aph, choosing a ce ain node
(inpu node) whose label a ime 0 equals he inpu o he NOT-ga e, simula ing he g aph
o a ixed numbe o i e a ions and asse ing he alue o a ce ain node w(ou pu node)
equals he ou pu o he NOT-ga e; i he inal wis 0 when he ini ial is 1, changing
he ins ance by dec easing he ini ial alue o canno inc ease he alue o w. Besides,
Co olla y 2 educes he complexi y o simula ing opinion g aphs o which Sα
1≥Sα
0,
since only e ices whose label is 0 need o be ee alua ed, and only when he alue o a
neighbou inc eases o 1.
6When bo h a gumen s inc ease, he alue o he unc ion inc eases, al hough maybe no s ic ly.
No e ha his implies Sα
+1( j) inc eases o s ays he same i he labels o Sα
a e all inc eased o le
unmodi ied.
7This means he sequence o alues o any gi en node always con e ges, since hese sequences a e
cons an o lip once om 0 o 1. Howe e , he alues do no con e ge a he same ime, and in in ini e
g aphs he e migh no be a ime a which all alues ha e con e ged.
19
3 Complexi y p ope ies o opinion g aphs
In his sec ion we p o e opinion g aphs based on la ices a e Tu ing-comple e and discuss
some o he p ope ies o he complexi y o simula ing such g aphs. The esul s we ob ain
a e mos ly based on one key ac : i is possible o simula e Tu ing machines wi h opinion
g aphs by using a Z-shaped g aph in which each block ep esen s a cell and encodes
he se s Qand Γ and he ansi ion unc ion δwhich desc ibe he Tu ing machine. We
i s desc ibe how opinion g aphs a e unc ionally comple e, hen explain how a Tu ing
machine can be simula ed. Las bu no leas , we deduce se e al impo an esul s abou
he p oblem’s complexi y.
3.1 Opinion g aphs a e unc ionally comple e
The esul s discussed in p e ious sec ions migh seem discou aging, since hey show NOT-
ga es canno be simula ed as such in opinion g aphs. This makes i necessa y o ake a
di e en app oach when ackling his p oblem. In o de o sol e he issue, we a e going
o p o e unc ional comple eness by cons uc ing g aphs which duplica e in o ma ion by
keeping he opposi e label o each node in ano he node. This duplica ion o in o ma ion
does no subs an ially inc ease he complexi y o he g aphs and sol es he p oblem o he
inc easing ansi ion unc ion; i we conside wo s a es Sα
0and Sβ
0o an opinion g aph
G= (V, E) which sa is y
Sα
0( i) = 0, Sβ
0( i)=1,
Sα
0( j) = 1, Sβ
0( j)=0,
hey a e no compa able wi h espec o he pa ial o de in oduced in De ini ion 6, so
none o he p oblems we ha e in Subsec ion 2.3 apply in his case. We now p o e ha
opinion g aphs a e unc ionally comple e, jus like desc ibed in Theo em 3.
Theo em 3 (Func ional comple eness o opinion g aphs).Gi en a iables x1, . . . , x and
a p oposi ional logic o mula P(x1, . . . , x ), he e exis s a non-nega i e in ege ∆∈Z≥0,
known as he p opaga ion ime, and a ini e opinion g aph G= (V, E)in which ce ain
pai wise disjoin se s o nodes V+
xi
i=1 ,V−
xi
i=1 , C and nodes +
, −
(possibly in one o
he o me se s) sa is y he ollowing p ope ies:
(1) Nodes in he se s V+
xi
i=1 ,V−
xi
i=1 , C do no ha e any non- e lexi e incoming
edges, which implies ha o any choice o ini ial alues Sα
,
Sα
+1( ) = Sα
( )i ∈V+
xi
i=1 ∪V−
xi
i=1 ∪C.
(2) The e exis s a labelling SC o nodes in C, such ha i
∀i∈N , ∈V+
xi, Sα
0( ) = xi,
∀i∈N , ∈V−
xi, Sα
0( ) = ¬xi,
∀ ∈C, Sα
0( ) = SC( ),
20

hen i is ue ha
Sα
0+∆( +
) = P(x1, . . . , x )and Sα
0+∆( −
) = ¬P(x1, . . . , x ),(3)
e en i Gis in eg a ed inside a la ge g aph, and i s ansi ions a e modi ied by
in luencing nodes in V+
xi
i=1 ∪V−
xi
i=1 a bi a ily, by means o ex e nal nodes.
Being able o a bi a ily add edges which in luence nodes in V+
xi
i=1 ∪V−
xi
i=1, while
s ill sa is ying (3), le s us use Theo em 3 o include g aphs which calcula e a bi a y
p oposi ional logic o mulas inside la ge g aphs. This will be e y use ul when p o ing
gene al complexi y p ope ies o opinion g aphs.
We use s uc u al induc ion o p o ing opinion g aphs a e unc ionally comple e.
The possible base cases a e he o mulas ⊤,⊥and xi o any i. These base cases a e
easily seen o be sa is ied. Fo ⊤, a possible Gconsis s o wo nodes 1= +
and 2= −
and no non- e lexi e edges. This g aph sa is ies he p ope y o unc ional comple eness
explained abo e o ∆ = 0, p o ided ha 1, 2∈Cand
SC( 1)=1, SC( 2)=0.
Fo ⊥, he same g aph, ou pu nodes and ∆ = 0 wo k, al hough he labelling SCmus
hen sa is y
SC( 1)=0, SC( 2)=1.
The hi d base case (P(x1, . . . , x ) = xi) can be ob ained by conside ing he same g aph,
he same ∆ = 0, he same +
, −
and he se s
V+
xi={ 1}, V −
xi={ 2}.
In his base case, all o he node se s conside ed in Theo em 3 (Cand all o he se s
V+
xj, V −
xj|j∈N , j =i) a e emp y.
We now discuss induc i e s eps. I su ices o p o e ha gi en wo o mulas P1and P2 o
which i is possible o cons uc opinion g aphs as in Theo em 3, analogous g aphs can
be cons uc ed o each o he o mulae
¬P1, P1∨P2, P1∧P2,
since i is well known ha he se {¬,∨,∧} is unc ionally comple e in logic.
The cons uc ion o ¬Pgi en a cons uc ion o he o mula Pis almos immedia e.
Gi en GP, ∆P, he se s V+,P
xi
i=1 ,V−,P
xi
i=1 , CP, he nodes +,P
, −,P
and SC,P , all o
which sa is y he condi ions in Theo em 3 o P, a cons uc ion o ¬Pis ob ained by
in e changing he oles o +,P
(which becomes −,¬P
) and −,P
(which becomes +,¬P
),
and no al e ing any o he elemen o he cons uc ion.
We now gi e a p oo o P1∨P2gi en cons uc ions o P1and P2. Gi en bo h cons uc-
ions, we i s conside he disjoin union o bo h o hem, which is de ined as ollows.
Gde
= (VP1⊔VP2, EP1⊔EP2),
V+
xi
de
=V+,P1
xi⊔V+,P2
xi,
V−
xi
de
=V−,P1
xi⊔V−,P2
xi,
Cde
=CP1⊔CP2.
21
By using he symbol ⊔, we mean he disjoin union o he wo se s in ol ed; by using
i he e, we essen ially c ea e a g aph which consis s o wo sepa a e copies o he con-
s uc ions o P1and P2. These wo copies ha e no common e ices o edges, e en i
hey ha e he same o iginal de ini ion (which migh happen i P1and P2ha e a common
sub o mula). SCis de ined in Cand ex ends bo h SC,P1and SC,P2(i ag ees wi h bo h
SC,P1on CP1and SC,P2on CP2).
We now desc ibe how o comple e his disjoin union in o de o ob ain a cons uc ion o
P1∨P2. In ui i ely, we need o add an OR-ga e made o new nodes, whose inpu nodes
a e he o iginal ou pu nodes o G, which a e
+,P1
, −,P1
, +,P2
, −,P2
.
The p oblem wi h such an app oach is ha we need o ake ime cons ain s in o accoun .
Le us suppose ha he alues o nodes in he se s V+
xi
i=1 ,V−
xi
i=1 co espond o
a ce ain assignmen o he a iables x1, . . . , x a ime 0. Then, he alues o +,P1
and −,P1
encode P1(x1, . . . , x ) a ime 0+ ∆P1, and hose o +,P2
and −,P2
encode
P2(x1, . . . , x ) a ime 0+ ∆P2. Since ∆P1and ∆P2a e no necessa ily equal, he inpu s
gi en o he OR-ga e do no necessa ily en e he ga e a he same ime, which implies a
co ec esul can ne e be gua an eed.
This issue can be sol ed by adding chains o nodes which gene a e a delay in he as es
ou pu , so bo h ou pu s a i e a he same ime. I ∆P2<∆P1, we add he nodes
e +
∆P2+1, e +
∆P2+2, . . . , e +
∆P1−1, e +
∆P1, e −
∆P2+1, e −
∆P2+2, . . . , e −
∆P1−1, e −
∆P1,
and he ollowing edges, whose weigh is 1.
(1) An edge whose sou ce is +,P2
and whose des ina ion is e +
∆P2+1. The p esence o his
edge implies he alue o node e +
∆P2+1 a ime 0+ ∆P2+ 1 is he alue o node +,P2
a ime 0+ ∆P2, which is P2(x1, . . . , x ).
(2) Fo all i∈∆P2+ 2,∆P2+ 3,...,∆P1−1,∆P1, an edge whose sou ce is e +
i−1and
whose des ina ion is e +
i. Analogously, he p esence o hese edges implies he
alue o node e +
ia ime 0+iis P2(x1, . . . , x ).
(3) Analogous edges (like hose in poin s (1) and (2)) which connec he nodes
−,P2
→ e −
∆P2+1 → e −
∆P2+2 → · · · → e −
∆P1−1→ e −
∆P1.
By adding hese edges, he alue o he node e +
∆P1a ime 0+ ∆P1is P2(x1, . . . , x ), and
ha o he node e −
∆P1a ime 0+ ∆P1is ¬P2(x1, . . . , x ). These wo nodes ha e a simila
ole o he o iginal nodes +,P2
and −,P2
, bu hei delay is ∆P1ins ead o ∆P2, so hey
a e coo dina ed wi h he nodes +,P1
and −,P1
. The new edges only in luence new nodes,
so all p ope ies assumed in he induc ion hypo heses a e p ese ed a e modi ying he
g aph.
An analogue o his modi ica ion can be ca ied ou i ∆P1<∆P2, so no ma e how long
delays a e, we can always c ea e an a i icial delay in he as es g aph so all ou pu nodes
a e coo dina ed.
22
We now desc ibe how o add an OR-ga e o he (possibly modi ied) disjoin union i
∆P1= ∆P2de
= ∆, which we can now assume. We add ou mo e nodes o he g aph, which
a e
+
, −
, +
OR, −
OR.
The nodes +
and −
a e he ou pu nodes o de
=P1∨P2, which will be calcula ed in ∆+1
i e a ions. These nodes p ocess he in o ma ion p o ided by he ou pu nodes o P1and
P2a ime 0+ ∆, so hei alues a ime 0+ ∆ + 1 ep esen P1∨P2. The nodes +
OR and
−
OR a e used o in luence +
and −
so he logical OR is calcula ed co ec ly. They need o
ha e speci ic alues, so we add hem o Cand we ex end he de ini ion o SCby de ining
SC( +
OR)=1, SC( −
OR) = 0.
We add he ollowing edges, which only a ec he newly added nodes.
(1) Re lexi e edges whose weigh is 1 o he nodes +
OR, −
OR.
(2) Th ee edges whose common weigh is 1/3, whose common des ina ion is +
and
whose sou ces a e +
OR, +,P1
, +,P2
. I is i ial ha i he cons ain s gi en by SC
a e sa is ied, hen he alue o +
a ime + 1 is he logical OR o he alues o
+,P1
, +,P2
a ime .
(3) Th ee edges whose common weigh is 1/3, whose common des ina ion is −
and
whose sou ces a e −
OR, −,P1
, −,P2
. Jus like in poin (2), i is i ial ha i he
cons ain s gi en by SCa e sa is ied, hen he alue o −
a ime +1 is he logical
AND8o he alues o −,P1
, −,P2
a ime .
A e modi ying he disjoin union by ollowing he s eps desc ibed abo e, we a e le wi h
a cons uc ion o P1∨P2which sa is ies he p ope ies o Theo em 3. Figu e 7 ep esen s
he cons uc ion g aphically. A cons uc ion o P1∧P2can be ob ained simila ly by
de ining
SC( +
AND) = 0, SC( −
AND)=1,
and using hem ins ead o +
OR and −
OR, o by using De Mo gan’s laws. The p oo o
unc ional comple eness o opinion g aphs is hus comple e.
3.2 Building a Tu ing machine wi h opinion g aphs
Func ional comple eness o opinion g aphs and he concep o L-shaped g aphs le us
de ine an N-shaped g aph which can simula e a semi-in ini e ape Tu ing machine. This
cons uc ion will be ex emely use ul o p o e many complexi y p ope ies o he p oblem
we a e conside ing. We basically use each block o he N-shaped g aph o encode a cell
o he Tu ing machine we a e conside ing, and cons uc he g aph such ha simula ing
i s e olu ion is equi alen o simula ing he e olu ion o he Tu ing machine.
Be o e we begin o discuss he cen al opic o his sec ion, we make an impo an ema k
ela ed o e minology. The wo d s a e in he con ex o Tu ing machines can be ambigu-
ous i no used p ope ly, since i can ha e wo di e en meanings. On he one hand, he
8This makes sense o he ole o −
, since De Mo gan’s laws s a e ha , in pa icula , ¬P1∧ ¬P2=
¬(P1∨P2).
23
Figu e 7: G aphical ep esen a ion o he induc i e s ep ca ied ou when adding an OR-
ga e. The di ec ion and weigh o newly added edges a e no shown. Pai s o nodes wi h
opposi e alues a e shown as wo semici cles. Inpu nodes and nodes in C(bo om o
he iangles) gene a e in e media e ou pu s ( op o he iangles), whose OR- alue (node
abo e) is compu ed by means o wo nodes (one ci cle), whose alues always equal 1 and
0, and he six edges men ioned in he ex .
machine’s s a e can e e o he con en o he s a e egis e , which always is one o he
ini ely many possible s a es. On he o he hand, he machine’s s a e can mean he global
s a e, which consis s o he m-con igu a ion, he posi ion o he head and he con en s o
he ape. Du ing he es o his wo k, we use he e ms m-con igu a ion, in e nal s a e
and s a e o he o me concep , and we use he e ms global s a e, s a e o p og ess and
s a e o he sys em o he la e .
Gi en a semi-in ini e ape Tu ing machine whose alphabe is Γ, whose se o s a es is Q
and whose ansi ion unc ion is δ:Q×Γ→Q×Γ× {L,S,R}(i he machine is in s a e
q,σis ead and δ(q, σ)=(q′, σ′, D), hen he machine will eplace σby σ′on he ape,
change i s in e nal s a e o q′and mo e le , s ay o mo e igh , i Dequals L,So R
espec i ely, excep o he i s cell, o which he e ec o Lis s aying in he same cell),
we assume wi hou loss o gene ali y ha he alues o he se s Γ and Qcan be encoded
by using a ini e numbe o bina y a iables. In gene al, we use he no a ion s1, s2, . . . , sµ
o bina y a iables which encode he s a es, and a1, a2, . . . , aν o bina y a iables which
encode he alphabe . The wo encodings need no be ela ed o each o he .
The de ini ion o a semi-in ini e ape Tu ing machine implies ha o e e y cell eo he
machine, gi en he ollowing in o ma ion,
• he de ini ion o he Tu ing machine,
•whe he o no he head is cu en ly poin ing a eo a cell nex o i , and i i is
he case, he cu en m-con igu a ion,
• he symbols w i en on cell eand he cell(s) nex o i ,
i is possible o calcula e he ollowing in o ma ion (which can be calcula ed by a Boolean
ci cui i he s a es and he alphabe ha e been encoded by means o bina y a iables),
24
Le us de ine some no a ion i s in o de o desc ibe hese edges. E e y g aph G ∈ Gis
cons uc ed om Theo em 3, so he e exis ou pu nodes ( +
, −
) which s o e he alue
o a ce ain a iable calcula ed by Ga e ∆ simula ion s eps. Inside he block Gewhose
ela i e posi ion is R∈ {Fs ,Mid}, we de ine Sp,+and Sp,− o be he ou pu nodes +
and −
, espec i ely, o he copy o Gp
Rin Ge. We use simila no a ion o he es o he
g aphs: Sa,+
iand Sa,−
ia e he ou pu nodes o he copy o Ga
R,i inside Ge, and Ss,+
jand
Ss,−
ja e he ou pu nodes o he copy o Gs
R,j.
Inside Ge, we connec ou pu nodes o -nodes by using edges whose weigh is 1 (so
in o ma ion in ou pu nodes is ully ansmi ed o -nodes). These connec ions a e made
na u ally, by connec ing he ou pu nodes o e e y a iable o he -nodes o he same
a iable, as ollows.
Sp,∗→ p,∗
e,Ss,∗
j→ s,∗
e,j ,Sa,∗
i→ a,∗
e,i .(19)
We ha e now comple ely desc ibed Gand all he edges which connec -nodes, w-nodes
and copies o GR o each o he . We ha e al eady discussed why Gsa is ies he condi ions
o Theo em 4 in o mally. A e desc ibing G o mally, we now explain why Gsimula es
an a bi a y semi-in ini e ape Tu ing Machine M.
Taking ∆M= ∆+3 in Theo em 4, whe e ∆ is he p opaga ion ime o all g aphs in G, and
gi en an ini ial s a e S0which ep esen s a ce ain s a e o p og ess α=q0,{dn}n∈N, x0,
we know ha he -nodes ep esen α, jus like in he i s h ee condi ions o De ini ion 8.
Also, he labels o all e ices ∈Ca e he labels assigned by SC. Due o how we ha e
de ined Cand SCabo e in G, his basically means he cons ain s o all g aphs in Ga e
sa is ied. The e o e, hese g aphs compu e p oposi ional logic o mulas whose a iables a e
ead om inpu nodes and whose esul is p oduced in ou pu nodes a e ∆ s eps. Inside
each copy o a g aph om G, we ha e only changed he way inpu nodes a e in luenced
when de ining G. This means all cons ain s o all g aphs will always be sa is ied o all
successi e s a es o S0, so he alues o all p oposi ional logic o mulas F ∈ Fwill be
compu ed e e y simula ion s ep, wi h a delay o ∆ s eps.
Since -nodes a e connec ed o w-nodes as we desc ibed in (15), w-nodes ha e he alue
hei co esponding -node had in he p e ious simula ion s ep o G. The e o e, a e one
simula ion s ep S0→S1,w-nodes encode he s a e α. Also, since w-nodes a e connec ed
o he co esponding inpu nodes o all g aphs, like we desc ibed in (16), (17) and (18),
all inpu nodes o all g aphs in Gha e he alues o all a iables which encode αa e wo
simula ion s eps (S2). As we ha e explained be o e, he way we ha e de ined Fand G,
he cons uc ion o Gand he assump ions abou S0imply ha , a e ∆ simula ion s eps
(S2→S∆+2), all in o ma ion abou he nex s a e o p og ess o Mhas been compu ed
and is s o ed in he ou pu nodes o he g aphs o G. Finally, since we ha e connec ed
hese ou pu nodes o -nodes as in (19), ha is, by connec ing nodes which a e ela ed
o he same a iable o he nex s a e o p og ess o M, his in o ma ion is ans e ed
back o -nodes a e one simula ion s ep (S∆+2 →S∆+3). Le us summa ise: a e
∆ + 3 = ∆Msimula ion s eps, De ini ion 8 is sa is ied, bu ins ead o ep esen ing he
global s a e α,S∆+3 ep esen s he nex global s a e. By using induc ion, we conclude
ha a e simula ing he e olu ion o G o ∆M· s eps s a ing om he labelling S0,
he in o ma ion in -nodes encodes he global s a e o Mob ained a e i e a ions o
he machine, i he ini ial global s a e was α.
We end his sec ion wi h some ema ks which we a e no going o discuss and p o e in
31

de ail. Fi s and o emos , i is impo an o no e ha he cons uc ion o Gexplained
abo e can be modi ied in o de o simula e an in ini e ape in bo h di ec ions. This is
done by using a Z-shaped g aph in which only a gene al block exis s (GMid). I can also
be made ini e, by gene a ing a ini e numbe o blocks whose ela i e posi ion is Mid
and adding a block a he end, G +1, whose ou going in e aces a e always sending he
in o ma ion p +1
=⊥back o G . This g aph simula es a Tu ing machine which can only
use a ini e amoun o space, and whose head disappea s i i ies o mo e beyond he
- h cell. I we conside he las wo blocks as one single block whose ela i e posi ion
is Ls , we can simula e an ins ance o Mwhich uses no mo e han cells by using an
N -shaped g aph. This ac is qui e impo an , so we s a e i he e as a heo em we will
e e o la e .
Theo em 5 (Semi-in ini e ape Tu ing machines which use cells can be simula ed by
N -shaped opinion g aphs).Gi en a semi-in ini e ape Tu ing machine Mand ∈N,
he e exis a ∆M∈Nand an N -shaped opinion g aph Gwi h disjoin subse s o nodes o
Gc
B p,+
Fs , p,−
Fs , s,+
Fs ,iµ
i=1 , s,−
Fs ,iµ
i=1 , a,+
Fs ,iν
i=1 , a,−
Fs ,iν
i=1 , CFs ,(20)
and labellings SC
Bo CB o B∈ {Fs ,Mid,Ls }, such ha gi en an ini ial s a e o
p og ess α=q0,{dn}n∈N, x0, s a ing om which he head o Mne e mo es beyond
he - h cell, and a labelling S0o G, i S0 ep esen s α, hen S∆M· ep esen s he s a e
o p og ess ob ained s a ing om αa e simula ing M o s eps.
De ini ion 8 only applies o N-shaped opinion g aphs. Howe e , i can be es ic ed o
N -shaped g aphs, so he no ion o ep esen ing a global s a e is well de ined in Theo em 5.
The second ema k ela ed o Theo em 4 is he ac ha he cons uc ion o Gcan be
modi ied so we only need basic local ini ial condi ions; a ese signal could be sen om
le o igh by using app op ia e addi ional nodes, which would ini ialise he con en s o
he ape and se pe
=⊥ o blocks o which he ese signal a i es. This signal o a ini e
numbe o di e en signals could be used o ini ialise nodes in C, o make su e logic ga es
wo k as in ended a e ecei ing he ese signal.
Fu he mo e, simula ing Gusing limi ed esou ces e e y s ep can be done by assuming all
nodes ha e cons an alues which a e he same ac oss di e en blocks and ne e change
beyond he igh mos block which has e e been isi ed by he head. These labels should
be chosen o ep esen he head no being p esen and a blank symbol on he ape.
Las bu no leas , he e is an impo an ema k which is indispensable o he p oo s o
some esul s we s a e and p o e below. These p oo s ely on he cons uc ion we explain
o p o ing Theo em 4. In his cons uc ion, -nodes, which display he s a e o p og ess o
Me e y ∆Msimula ion s eps, ansmi all hei in o ma ion o w-nodes e e y simula ion
s ep, and his ansmission o in o ma ion is uncondi ional and only depends on he alues
o -nodes. In he nex simula ion s ep, in o ma ion is ansmi ed om w-nodes o inpu
nodes o elemen s o G. This ansmission o in o ma ion is uncondi ional as well, and
is no co up ed i he alues o -nodes a e manually modi ied a e he i s simula ion
s ep, since all in o ma ion has al eady been ansmi ed o w-nodes.
Theo em 3 implies in o ma ion abou he nex global s a e o Mwill be ansmi ed o
he ou pu nodes o elemen s o Gdu ing he nex ∆ = ∆M−3 simula ion s eps, e en i
he alues o -nodes a e manually modi ied du ing hese ∆ cycles; Theo em 3 gua an ees
32
he alues o a iables which ha e al eady eached inpu nodes will no be al e ed, since
-nodes do no belong o any elemen o G.
This independence makes i possible o simula e ∆Mdi e en ins ances o Mby using
a single simula ion o G, as ollows: in o de o ini ialise Gwi h he s a es o p og ess
{α1, α2, . . . , α∆M}, we s a om a labelling S o which ∀ ∈Ce,S( ) = SC( ) (so logic
ga es unc ion p ope ly) and apply he ollowing algo i hm o G.
Algo i hm 1 Ini ialising G o simula e ∆Mins ances simul aneously s a ing om he
s a es o p og ess {α1, α2, . . . , α∆M}
1: o i= 1,2,...,∆Mdo
2: Replace he labels o -nodes so he labelling o Gnow ep esen s αi
3: Ad ance he simula ion o Gone s ep
4: end o
Theo em 4 and he independence p ope ies we ha e jus discussed imply all ins ances
a e simula ed a he same ime and a e ep esen ed in -nodes cyclically. When eplacing
he labels o -nodes in Algo i hm 1, ins ances which ha e al eady been inse ed a e no
co up ed, since he simula ion has ad anced, bu no mo e han ∆M−1 s eps. A he
end o Algo i hm 1, ∆Msimula ion s eps ha e passed since α1was in oduced in G, so he
nex s a e o p og ess is ep esen ed in -nodes. Du ing he nex i e a ion consis ing o
∆Msimula ion s eps, he nex s a es o p og ess co esponding o all ini ial global s a es
{α1, α2, . . . , α∆M}a e ep esen ed in Gin o de o inse ion. This p ocess epea s e e y
∆Msimula ion s eps and simula es e e y ins ance one s ep u he .
In o de o use his pa allel simula ion and concep ually desc ibe which ins ances we in end
o simula e in speci ic cases, we use he e m le el o in o ma ion when e e ing o one o
he ∆Ma ailable slo s he e a e o unning an ins ance o ∆M. The i s one consis s o
in o ma ion s o ed in -nodes, he second one consis s o in o ma ion s o ed in w-nodes,
and so on. Concep ually, in o ma ion mo es o he nex le el e e y simula ion s ep, and
ans o ms o ep esen he nex s a e o p og ess when mo ing om he las le el o he
i s one. O cou se, i can be decided o simula e a single ins ance by ini ialising -nodes
co ec ly in S0and ini ialising all o he nodes which a e no in C o andom alues.
3.3 Decidabili y and complexi y p ope ies o opinion g aphs
The esul s we ha e ob ained in p e ious sec ions a e e y use ul o analysing he com-
plexi y p ope ies o opinion g aphs in gene al, and hose o L-shaped g aphs in pa icula .
The wo key esul s we ha e ob ained so a a e Theo em 4 and Theo em 5, om which all
ele an complexi y esul s abou opinion g aphs can be deduced. We begin his subsec-
ion by discussing gene al p ope ies in ini e opinion g aphs ha e, and end i de e mining
he complexi y o simula ing ini e L-shaped opinion g aphs.
Theo em 4 implies L-shaped opinion g aphs can be as exp essi e as Tu ing machines. We
ha e also men ioned i is no necessa y o ini ialise an in ini e numbe o nodes in o de
o ob ain his exp essi eness; ini ialising a ini e numbe o nodes a he le mos block o
an N-shaped g aph su ices. This leads us o he ollowing heo em.
33
Theo em 6 (Limi p ope ies in L-shaped g aphs a e undecidable).Gi en an L-shaped
g aph Gand a ini e o in ini e ini ialisa ion condi ion17 o G, he ollowing p oblems a e
undecidable in gene al.
(a) Gi en a node o G, does he e exis a ce ain labelling S0o G, which espec s he
ini ialisa ion condi ion, and a ce ain ∈N, o which S ( ) = 1?
(b) Does he e exis a ce ain labelling S0o G, which espec s he ini ialisa ion condi ion
and e en ually s abilises (∃ ∈N|S +1 =S )?
(c) Gi en a ini e se Zo nodes o G, does he e exis a ce ain labelling S0o G,
which espec s he ini ialisa ion condi ion and o which i is possible o es ima e he
asymp o ic p opo ion o nodes which ag ee (o disag ee) in Z?
P oo . (a) Conside he uni e sal semi-in ini e ape Tu ing machine Ude ined in [4].
This machine accep s he inpu ⟨x, α⟩i he machine which is ep esen ed by α
accep s x. We de ine a Tu ing machine Uawhose beha iou is sligh ly di e en
om ha o U. Fo ou pu pose, he inpu o Uaalways begins wi h he special
ape symbol σ⊥(which is no used elsewhe e), and is hen ollowed by ⟨x, α⟩.Ua
simula es he ins ance ⟨x, α⟩, jus like U, bu wi hou modi ying he i s cell o he
machine. I Uaccep s ⟨x, α⟩, hen Uaalso does, bu mo es i s head o he i s cell
and o e w i es i wi h he symbol σ⊤(also ne e used elsewhe e) be o e s opping
comple ely. Fo p oblem (a), we de ine G o be he g aph which is cons uc ed using
he p oo o Theo em 4 wi h M=Ua. We assume wi hou loss o gene ali y ha
he ollowing wo p ope ies a e ue.
•I σx
=σ⊤, hen ax
1, = 1, and i σx
=σ⊤, hen ax
1, = 0. In o he wo ds, he
i s bi used o encode σ⊤is 1, while i is 0 o all o he alphabe elemen s.
•Gcan be ini ialised locally by app op ia ely se ing he alues o he nodes in
he i s mcells, and i will simula e Uaco ec ly, since i can co ec ly in e p e
a ese signal sen om Gm+1.
Gi en a gene al inpu ⟨x, α⟩, Theo em 4 and ela ed esul s p o ide a ini e18 o
in ini e19 ini ialisa ion condi ion o Gwhich makes i possible o simula e how Ua
p ocesses ⟨x, α⟩. The ini ialisa ion condi ion makes su e logic ga es wo k as ex-
pec ed, and sa es he ini ial s a e, place o he head and con en s o he ape in all
le els o in o ma ion o G, o in he one which co esponds o -nodes.
No e ha due o he encoding o ape symbols we ha e assumed ( i s assumed
p ope y) and how Uawo ks, ⟨x, α⟩being accep ed by Uis equi alen o he i s
17This means he ini ial labelling o he L-shaped g aph is a ce ain S0, and a possibly in ini e lis
o condi ions o he o m S0( i) = li,S0( i) = S0( j) o S0( i) = ¬S0( j) is gi en. We o mula e his
heo em in a e y gene al way, allowing incomple e desc ip ions o S0, in o de o emphasise ha he
undecidabili y o he p oblems we conside is no ela ed o in ini e ini ialisa ion condi ions which canno
be ully p ocessed in a ini e amoun o ime.
18This ini ialisa ion can be speci ied by using a ini e ini ialisa ion condi ion, due o he second assumed
p ope y.
19The in ini e case is also included he e, since a bi a ily de ining mo e nodes s a ing om a ini e
ini ialisa ion condi ion me ely gi es mo e de ails abou he ini ial s a e o p og ess o M, wi hou changing
he answe o he p oblem.
34
symbol o he ape o Uae en ually becoming σ⊤, which is in u n equi alen o he
label o a,+
1,1( he -node which codi ies he i s bi o he symbol on he i s cell)
e en ually aking he alue 1 o e e du ing he simula ion s eps in which -nodes
ep esen he global s a e o Ua. The e o e, he beha iou o Uon any inpu o he
o m ⟨x, α⟩can be educed o p oblem (a) o a ce ain subse o simula ion s eps,
making i undecidable as well.
We a e no done wi h he p oo o (a) ye , as we know ha a,+
1,1only ep esen s one
o he a iables o he s a e o he sys em e e y ∆Uas eps, so i migh be possible
o p o e he label o a,+
1,1equals 1 in a simula ion s a e in which -nodes do no
ep esen he s a e o p og ess o Ua. Howe e , as we discussed be o e, he way
we ha e cons uc ed Uain Theo em 4 makes i possible o simula e ∆Uains ances
simul aneously, and exac ly one o hem is ep esen ed in -nodes e e y cycle. I
∆Uacopies o he same ins ance a e simula ed in all ∆Uale els o in o ma ion, he
label o a,+
1,1becomes 1 i and only i σ⊥is eplaced by σ⊤on he i s cell o Ua.
This makes i possible o gua an ee ha he ini ial condi ion o Gchosen o ⟨x, α⟩
ex ends he equi alence discussed be o e o all simula ion cycles o G. Tha implies
he beha iou o Uon a bi a y inpu s can be educed o p oblem (a) he usual way,
so p oblem (a) is undecidable.
(b) Fo p o ing (b), we use some ideas om (a), bu change he cons uc ion o he semi-
in ini e ape Tu ing machine. In his case, we choose Ub o be a Tu ing machine
whose global s a e s abilises20 when i s inpu is ⟨x, α⟩i and only i Uaccep s ⟨x, α⟩.
Cons uc ing Ubcan be done in many di e en ways; inse ing cyclic loops in he
ansi ion unc ion o s a iona y global s a es in which ⟨x, α⟩is no accep ed, is one
possible app oach. We now de ine G o be he g aph which is cons uc ed aking
Ub, no Ua. Using he same a gumen as in (a), i is possible o simula e ∆Ubequal
ins ances o Ubin G.
I all simula ed ins ances a e equal, Ge en ually s abilises i and only i he s a e o
p og ess o Ubs abilises; i is ob ious ha Gdoes no s abilise i one o he ins ances
does no s abilise, and i hey a e all equal and e en ually s abilise, Gs abilises,
since each le el o in o ma ion o Ge en ually con ains he in o ma ion ela ed o
he s able s a e o p og ess, which does no change when ins ances low h ough he
le els o in o ma ion o G, as all ins ances a ain he s able s a e o p og ess. This
leads us o a educ ion which maps he beha iou o U o an a bi a y gi en inpu
⟨x, α⟩ o p oblem (b). The e o e, (b) is undecidable.
(c) In gene al, his p oblem is undecidable, e en i Zis a bi a ily la ge. We choose
Ucsuch ha , gi en inpu ⟨x, α⟩, he machine e en ually w i es he symbol σ⊥on
all cells om le o igh i Udoes no accep ⟨x, α⟩, while σ⊤is w i en i Udoes
accep . In o de o implemen his, he symbol σ⊥can be w i en p og essi ely
om le o igh while Uis simula ed on he igh , and i i is seen ha Uaccep s
he gi en inpu , hen he head goes o he beginning o he ape and o e w i es
e e y hing using σ⊤. Analogously, we now use G o deno e he g aph cons uc ed
using Uc. I , as in he p e ious p oblems, we assume he same inpu is p o ided in
20By de ini ion, Ms abilises i and only i he s a e o p og ess o Ms ops changing, i.e. he head
o Ms ays in he same place, he m-con igu a ion does no change and he symbol on he ape is no
modi ied.
35
all le els o in o ma ion o Gand choose Zk= a,+
e,1k
e=1
21, hen he alues o all
nodes o Zkwill e en ually be 1 i ⟨x, α⟩is accep ed by U, since all ape symbols
will e en ually become σ⊤, o 0 i ⟨x, α⟩is no accep ed. This cons uc ion educes
he same undecidable p oblem conside ed in (a) and (b) o p oblem (c), which is
hus undecidable.
E en hough Theo em 6 migh seem na u al gi en he esul s we ob ained in Sec ion 3.2, i
is no a di ec consequence o any p e iously p o ed heo em, and looks e y discou aging
a i s glance: i implies he p oblem o simula ing opinion g aphs and deducing hei
beha iou , which can be di ec ly applied o model opinion dynamics in mode n socie ies,
is undecidable, and we a e no e en able o gi e global quan i a i e es ima ions o he
g aph’s e olu ion o a bi a ily la ge amoun s o ime.
We now s a e and p o e he ini e e sion o his esul . Jus like Theo em 4 was used o
p o ing Theo em 6, he p oo o he ollowing heo em hea ily elies on he co esponding
ini e e sion o Theo em 4, which is Theo em 5. We i s gi e a de ini ion which p o ides
a way o gene a e L-shaped g aphs wi h he same in a ian local s uc u e. This de ini ion
is closely ela ed o De ini ion 5, and is e y ele an o a special case o he heo em we
discuss below.
De ini ion 9 (L-shaped g aphs o a iable size).Gi en d∈N, in e aces {Ij}j∈Ndand
ini e opinion g aphs GR o e e y R∈ {Fs ,Mid,Ls }dwhich a e mul iply connec ed o
he ollowing in e aces,
(a) I he j- h elemen o Ris no Ls , hen GRmus be connec ed o Ijas a p edecesso .
(b) I he j- h elemen o Ris no Fs , hen GRmus be connec ed o Ijas a successo .
we de ine, o each L=E1×E2× · · · × Ed(whe e each Eiequals Nsi o ce ain si≥
3), he g aph G(L)as he ini e L-shaped g aph ob ained by using he cons uc ion om
De ini ion 5.
We de ine |L|, he block ca dinali y o G(L), o be he ca dinali y o L=Qd
i=1 Ei=
Qd
i=1 Nsi, which equals Qd
i=1 si.
We s a e almos all o he p ope ies ela ed o ini e g aphs in one single heo em, since
hey a e closely ela ed o each o he and we ob ain he same complexi y class. We emind
he eade some assump ions we make. These assump ions a e na u al and used in [4].
(1) The way Tu ing machines a e encoded gua an ees ha gi en a machine’s desc ip-
ion by lis ing he ables o he ansi ion unc ions, he e exis s a polynomial- ime
algo i hm which encodes i . Simila ly, he algo i hm o decoding is also polynomial
( he numbe o alphabe symbols and s a es is bounded by a polynomial unc ion
o he leng h o he s ing which ep esen s he semi-in ini e ape Tu ing machine).
21Zkis he se o -nodes which encode he i s bi o he symbol w i en on he ape, o he i s k
cells. I s ca dinali y is k.
36

(2) When encoding opinion g aphs in a language, we lis he nodes and edges o he
g aph, so his ep esen a ion is a polynomial unc ion o he numbe o nodes. We
also lis all he a ional weigh s o all edges. The ep esen a ion used o a ional
numbe s gua an ees ha ope a ing wi h hem is possible by using polynomial- ime
algo i hms.
P oblems (c) and (d) o Theo em 7 a e no decision p oblems. Howe e , hey can i ially
be ans o med o a numbe o decision p oblems which is linea in he inpu o p oblems
(c) and (d). Besides, p oblems (c) and (d) a e e y p ac ical and ha e many applica ions.
The e o e, we s a e hem as op imisa ion p oblems. Wha we p o e is ha ob aining all
bi s o hei solu ions can be done using a polynomial amoun o space, and hey a e also
PSPACE-ha d. This app oach is equi alen o decision p oblems, as de ined in [4].
Theo em 7 (PSPACE-comple eness o global p ope ies o L-shaped g aphs).The ol-
lowing p oblems, whose inpu s a e a ini e L-shaped g aph Gand an ini ialisa ion condi ion
o G, a e PSPACE-comple e.
(a) Gi en a node ∈G, does he e exis a labelling S0o G, which sa is ies he ini ial-
isa ion condi ion, and a ∈N, o which S ( )=1?
(b) Does he e exis a labelling S0o Gwhich sa is ies he ini ialisa ion condi ion and
e en ually s abilises?
(c) O all possible ini ial labellings Sα
0which sa is y he ini ialisa ion condi ion, which
one maximises he p opo ion o nodes whose alue is 1a ime 22? Which maximum
p opo ion and co esponding ini ial and inal g aphs a e ob ained? Wha abou all
possible imes?
(d) Suppose he e exis polynomial- ime unc ions which calcula e he cos o ini ial la-
bellings, and he bene i o labellings a ime . Which ini ial labelling, wi h cos no
highe han cand which sa is ies he ini ialisa ion condi ion, maximises he bene i
a ime ? Which maximum bene i and co esponding ini ial and inal g aphs a e
ob ained? Wha abou all possible imes?
P oo . Fi s o all, we check all o hese p oblems belong o PSPACE. Simula ing opinion
g aphs o an a bi a y numbe o s eps can be done in polynomial space, due o ou
assump ions. P oblem (a) can be sol ed using polynomial space by conside ing all possible
ini ial labellings one a a ime and simula ing all o hem. Bina y coun e s can be used o
de ec when o s op simula ing, since he numbe o simula ion s eps e en ually exceeds
he numbe o possible s eps o he g aph. I is well-known and discussed in [4] ha
hese coun e s use a linea amoun o space. Sa ing he labelling S0also uses linea
space. P oblem (b) can be sol ed simila ly; an ini ial labelling is disca ded i i has no
con e ged when he numbe o s eps a ains he numbe o possible labellings o G.
P oblem (c) is a special case o p oblem (d), which can be sol ed by conside ing all
possible ini ial labellings, one a a ime, simula ing hem i hey sa is y all equi emen s
and keeping he bes ini ial and inal labellings depending on he ou come a ime . I
22In (c) and (d) o Theo em 7, is gi en as a bina y numbe .
37
he bes esul is needed o all imes ∈Z≥0, hen he simula ions can be un un il he
numbe o simula ion s eps exceeds he numbe o possible con igu a ions o he g aph.
This can be done using a polynomial amoun o space, as explained in [4].
We now show hese p oblems a e PSPACE-comple e by showing ha Laccsp ≤pL o
all o he conside ed Lassocia ed wi h he p oblems desc ibed in (a-d), whe e Laccsp
is he language de ined in Equa ion (1), in Pa 1.1.1 o he in oduc ion. Gi en an
ins ance (M, w, 1n) o his p oblem, i is possible o ans o m i o (M′, w, 1p(n)) using
a polynomial- ime algo i hm, so ha i Maccep s win space n, hen M′accep s wand
he i s cell, wi h an ini ial alue o σ⊥, changes once o σ⊤, and he global s a e o
M′s abilises, while M′does no accep , he i s cell keeps i s ini ial alue o σ⊥and
he global s a e does no s abilise i no . We know by Theo em 5 ha his p oblem
can be ans o med o an opinion g aph Gwhich simula es M′, and due o he i s
ans o ma ion om M o M′, he simula ion o Gleads o he answe o he p oblem
Laccsp o (M, w, 1n). A e he ans o ma ion om (M, w, 1n) o G, all p oblems (a-d)
can be used o de e mine i (M, w, 1n)∈Laccsp; he p oblem desc ibed in (a) can be
used by aking = a,+
1,1and using he same cons uc ion as in Theo em 6. The p oblem
desc ibed in (b) can also be used, since Gcon e ges i and only i he global s a e o
M′con e ges23. P oblems (c) and (d) can be used o analyse Gby looking a he inal
opinion g aph a e simula ing, which hese p oblems ob ain. Fo all p oblems (a-d), he
ini ialisa ion condi ion we use consis s o he ini ial assignmen s when cons uc ing G
using Theo em 5 o make su e logic ga es wo k, as well as he cons uc ion om he p oo
o Theo em 6, which assigns ixed alues o all le els o in o ma ion. This ini ialisa ion
condi ion assigns a alue o each node, which implies no eedom o modi y he nodes’
labels is gi en. Fo p oblems (c) and (d), his means a comple ely de e mined g aph is
simula ed, and whe he o no M′accep s is deduced by looking a he inal label o a,+
1,1,
which is calcula ed by p oblems (c) and (d) as pa o he inal g aph. Rega ding p oblems
(a) and (b), he comple ely de e mined g aph is simula ed as well and he de ini ion o
M′gi en inpu (M, w, 1n) implies ha M′accep s i and only i p oblems (a) and (b) a e
ue.
All we need o show in o de o inish his p oo is ha ans o ming an ins ance (M, w, 1n)
o i s co esponding Gcan be done in polynomial ime. This ollows om p e ious
heo ems we ha e al eady discussed. Fi s o all, he cons uc ion used in Theo em 3
ans o ms p oposi ional logic o mulas o opinion g aphs in polynomial ime, since in
mos o he cons uc ion a cons an numbe o nodes and edges is added o each symbol in
a o mula. The e is an excep ion, which is when chains o nodes a e added o achie e equal
delays o di e en opinion g aphs. Howe e , he leng h o hese chains is a linea unc ion
o he delay o an al eady cons uc ed g aph. This makes he cons uc ion quad a ic
in he leng h o he o mulas. Also, i is shown in [4] ha he e exis polynomial- ime
algo i hms o ans o m a semi-in ini e ape Tu ing machine M o he se o logic o mulas
FMwhich de e mine i s ansi ion unc ions. All hese o mulas a e hen ans o med
o he co esponding se o g aphs GM om Theo ems 4 and 5 using he polynomial-
ime algo i hm discussed in 3. These g aphs a e hen copied no mo e han n imes
o cons uc G, so he ime complexi y emains bounded by a polynomial. Ini ialising
23O cou se, in o de o make su e Gcon e ges i and only i he global s a e o M′con e ges, i is
necessa y o use he same ype o ini ialisa ion as in Theo em 6; all le els o in o ma ion ha e o simula e
he same ins ance.
38
nodes as desc ibed in he p oo s o Theo ems 4 and 6 by using Algo i hm 1 can also
be done in polynomial ime. The e o e, ans o ming (M, w, 1n) o Gis possible using
a polynomial- ime algo i hm, which implies all p oblems discussed in his heo em a e
PSPACE-comple e.
This heo em is e y discou aging as well; impo an ques ions abou a bi a y g aphs
canno be easily answe ed. This migh make i ex emely di icul o unde s and opinion
dynamics in eal li e. Ne e heless, his ask migh u n ou o be much easie in eal-li e
condi ions. A e all, he g aphs we a e conside ing in he p oo o Theo em 7, which
a e i s de ined in he p oo o Theo em 3, a e clea ly e y di e en om eal-li e social
g aphs; all nodes in luence exac ly one node, apa om hemsel es, and many o hem
jus ecei e an opinion om one node du ing a cycle and pass i on o ano he node.
I is impo an o no e ha he p oo gi en abo e can be applied o ini e opinion g aphs
in gene al; al hough he a gumen s used o p o e polynomial educ ion om Laccsp o
he p oblems desc ibed in Theo em 7 ely hea ily on epe i i e pa e ns in N-shaped
g aphs and he cons uc ions discussed in p e ious sec ions, p o ing ha all p oblems
om Theo em 7 belong o PSPACE can be done wi hou assuming ha Gis an L-
shaped g aph. The e o e, he space which is needed o simula e an a bi a y opinion
g aph o ob ain conclusions abou i s beha iou is a polynomial unc ion o i s numbe o
e ices, and no hing can be said abou he ime complexi y, apa om wha is implied
by Theo em 1, since we now know he gene al p oblem is PSPACE-comple e. O cou se,
he e a e se e al special cases o which he complexi y can be de e mined; one o hem
is Co olla y 2. I he ini ial condi ion o Gcomple ely de e mines he alue o all nodes
and sa is ies Co olla y 2, hen i is possible o simula e he e olu ion o Gin polynomial
ime, since he numbe o simula ion s eps be o e he labels o nodes in Gcon e ge does
no exceed he numbe o e ices24.
We now s a e and p o e a speci ic case o Theo em 7 which can be used when he s uc u e
o he L-shaped g aph is ixed. Al hough his Co olla y is p edic able, i p o ides mo e
p ecise space bounds o he ixed s uc u e case, so we s a e i o comple eness.
Co olla y 3 (Space bounds o L-shaped g aphs o a iable size).Gi en d∈N, in e aces
{Ij}j∈Ndand ini e opinion g aphs GR o e e y R∈ {Fs ,Mid,Ls }das in De ini ion 9,
he e exis Tu ing machines Ma, Mb, Mcand a cons an Ksuch ha p oblems (a), (b) and
(c) om Theo em 7 can be sol ed by Ma, Mb, Mc espec i ely, using no mo e han K· |L|
cells i he inpu g aph o he p oblem is G(L), o all L=E1×E2× · · · × Ed.
P oo . I e a ing h ough all s a es, sa ing s a es, coun ing he numbe o nodes which
ag ee o a ce ain s a e and coun ing he numbe o simula ion s eps can all be done in
linea space. All we need o p o e is ha he g aph can be sa ed in linea space and be
simula ed in linea space, as a unc ion o |L|. Since he local s uc u e o he g aph is
ixed, i is possible o make he alphabe o he Tu ing machines ich enough o sa e wo
copies o he ollowing in o ma ion as a ape symbol.
24Suppose Ghas nVnodes, and i akes nC> nVsimula ion s eps o hei labels o con e ge. Then,
since e e y node ∈G lips i s opinion a mos once due o Co olla y 2, no mo e han nVopinion
changes ake place in s ic ly mo e han nVsimula ion s eps, du ing which he g aph has no s abilised
ye . Tha is a con adic ion, since he pigeonhole p inciple implies he e ha e been no opinion changes
du ing a ce ain cycle, which is impossible, since ha implies Ghas ac ually con e ged be o e nCs eps.
39
(a) The s a e o he nodes belonging o a block Ge.
(b) In o ma ion abou he ela i e posi ion o Ge, which is gi en by an elemen o
{Fs ,Mid,Ls }d.
(c) A Boolean i (Ge), which is usually ⊥.
Blocks o he g aph can be encoded using linea space by using his me hod and sa ing
hem in lexicog aphical o de . In o de o simula e he g aph, he machine can i e a e
h ough all blocks o he g aph and compu e hei nex s a e, sa ing a copy o i in each
block wi hou des oying he copy o he cu en s a e, which needs o be sa ed o compu e
he nex s a e o o he blocks.
In o de o calcula e he nex s a e o a block Ge, in o ma ion abou nodes which a e
connec ed o incoming in e aces o Geis needed. I his in o ma ion is ob ained, he
ansi ion unc ions o he nodes o Gecan be encoded in Ma, Mb, Mc, since he s uc u e
o he blocks is ixed. In o de o ob ain his in o ma ion o a ce ain dimension d, he
Tu ing machines can se i (Ge) = ⊤ o emembe i s posi ion and mo e hei heads o he
le and o he igh in o de o ind he posi ions a which he posi ion o he block in
dimension dchanges ( his can be done by looking o blocks whose ela i e posi ions a e all
Fs o dimensions which ha e a lowe p io i y han din he lexicog aphic o de ), and se
hei i Boolean o ⊤as well. In o de o ind he blocks which a e abo e and below Gein
dimension d, he Tu ing machines need o ind he blocks which a e a he same dis ance
o he ollowing inc ease (o dec ease) in he alue o dimension das Ge. This calcula ion
can be done wi hou using coun e s, by ma king blocks (modi ying hei i alue, o e en
using a cons an numbe o addi ional Boolean a iables inside e e y block). This makes
i possible o ind all he needed in o ma ion o compu e he nex s a e o e e y block
wi hou using mo e han |L|cells, so simula ing he g aph, and hus p oblems (a), (b)
and (c) om Theo em 7 can be sol ed using a linea amoun o space.
O cou se, simila space bounds o p oblem (d) om Theo em 7 can be calcula ed, as
long as bounds a e gi en o he space used by he cos and bene i unc ions.
The las heo em o his pa o he wo k p o ides he complexi y class o simple e sions
o he p oblems discussed abo e. We emind he eade ha he language
L msa
de
=⟨α, x, 1n,1 ⟩ | ∃u∈ {0,1}ns. . Mαaccep s 1 on inpu ⟨x, u⟩wi hin s eps
is NP-comple e. Fo a p oo o his ac , see [4]. We also emind he eade ha we
assume ce ain s anda d p ope ies o he ep esen a ion o opinion g aphs and Tu ing
machines, jus like we explained be o e Theo em 7.
Theo em 8 (NP-comple eness o local p ope ies o L-shaped g aphs).The ollowing
p oblems, whose inpu s a e a ini e L-shaped g aph G, an ini ialisa ion condi ion o G
and a posi i e in ege ∈Nwhich is gi en in una y25, a e NP-comple e.
(a) Gi en a node ∈G, does he e exis a ce ain labelling S0o Gwhich sa is ies he
ini ialisa ion condi ion and o which S ( ) = 1?
25In he inpu , is gi en as 1 . This ac is ex emely impo an , since he p oblems a e no NP-
comple e i is gi en in bina y.
40
Modi ica ion Alg0 Alg1 Alg2 Alg3 Alg4
S anda d 0.7480152 0.7828424 0.7940712 0.7780384 0.7901952
NonReGE 0.7522288 0.7767368 0.7881176 0.7721000 0.7855128
S e ched 0.7042544 0.7374504 0.7479160 0.7356360 0.7447552
Bo h 0.7032392 0.7233448 0.7352504 0.7184056 0.7308472
Modi ica ion Alg5 Alg6 Alg7 Alg8 Alg9
S anda d 0.8768376 0.8994000 0.9118392 0.8956056 0.9078544
NonReGE 0.8793336 0.8964144 0.9079536 0.8923088 0.9042080
S e ched 0.8235320 0.8445024 0.8573536 0.8411672 0.8538840
Bo h 0.8225656 0.8327856 0.8479816 0.8266624 0.8420864
Table 1: A e age p opo ion o a ou able nodes ob ained when applying all basic algo-
i hms o di e en modi ica ions o he s anda d p oblem. 50 di e en ins ances o each
cell we e used.
By emembe ing wha each algo i hm is based on, we conclude ha i s in luence is a
be e c i e ion han second in luence, al hough i in ui i ely seems be e o use second
in luence, since i conside s mo e in o ma ion. I can also be seen ha conside ing he
cos pe uni o in luence is a be e app oach han conside ing he numbe o uni s o
in luence o a node.
Only conside ing he weigh o nodes when selec ing hem is he wo s possible s a egy.
Howe e , wha a ec s esul s he mos is di iding heu is ics in i e s eps and empo a ily
locking nodes (Alg5-Alg9) o no (Alg0-Alg4).
When he g aph is s e ched o global nodes a e no ealis ic, he g aph is less compac ,
so ob aining a good solu ion becomes mo e di icul , and he a ained p opo ions o
a ou able nodes in Table 1 a e lowe . The e a e wo excep ions, which a e Alg0 and
Alg5. These wo algo i hms only conside cos when choosing nodes, and hei success a e
inc eases when ansi ioning om s anda d g aphs o NonReGE-g aphs. This is because
all o he algo i hms always selec all o almos all o he nodes whose i s in luence is
e y high, while Alg0 and Alg5 do no . When global edges a e dis ibu ed andomly,
he numbe o highly in luen ial nodes dec eases signi ican ly, making i less p oblema ic
when a ce ain heu is ic does no ake in luence in o accoun .
4.2.2 Benchma ks o he bes basic s a egy
In o de o be e unde s and how changing pa ame e s a ec s he p oblem we a e ying
o sol e, we analyse how he bes basic s a egy (Alg7) beha es when ce ain gene a ion
pa ame e s o he opinion g aphs change. All ob ained esul s ha e been es ed by using
a leas 50 di e en ins ances, and hypo hesis es ing me hods om [10] (implemen ed
in [2]) ha e been used o e i y all s a is ically signi ican claims we make.
Changing he maximum weigh o e lexi e edges
When we de ined he s anda d model we use o cons uc ing g aphs, we speci ied ha
he weigh s o global edges a e aken andomly and uni o mly om N25. Mo e gene ally,
hey could be aken om Nx, and his choice g ea ly a ec s he a e age s ubbo nness o
nodes, making i much mo e di icul o change he alue o o he nodes by in luencing
47

hem om ou side when xis la ge.
Figu e 8: Changing he maximum possible weigh o e lexi e nodes a ec s he esul s
ob ained by he bes basic s a egy. 50 di e en g aphs we e gene a ed and sol ed o
each da a poin in o de o ob ain a e age esul s. Apa om he change in he e lexi e
nodes’ maximum weigh , no pa ame e s a e di e en om he s anda d ones. 21 di e en
alues ({0,5,10,...,100}) ha e been conside ed.
Figu e 8 shows wha he consequences o changing his pa ame e a e; ou in ui ion is
con i med. Al hough he gene al end is clea , i can also be seen ha changing his
pa ame e a ec s he a e age a ou able p opo ion o nodes mo e when i becomes la ge,
while he e ec s a e less no iceable when x≤40.
Changing he numbe o global edges
We can also modi y he s anda d model by modi ying he numbe o global edges wi hou
al e ing any o he o he pa ame e s. This should heo e ically make he g aph mo e
compac and in e connec ed, educing he a e age sho es pa h leng h and making i
easie o sp ead opinion ends.
Figu e 9: Changing he numbe o global edges a ec s Alg7’s pe o mance. 50 di e en
g aphs we e gene a ed and sol ed o each da a poin in o de o ob ain a e age esul s.
I can be seen ha he end is almos linea . The co ela ion be ween bo h a iables
equals 0.996. Ne e heless, his end is no global, since he maximum a ainable alue
in he y-axis is 1. Only he numbe o global edges is changed, all o he pa ame e s a e
he s anda d ones. 26 di e en numbe s o global edges ({0,4000,8000,...,100000}) ha e
been conside ed.
48
The end in Figu e 9 is con i med and is essen ially linea , bu simula ions beyond 100000
global edges show ha i is no ( he slope dec eases beyond 100000 global edges), and
he p opo ion o a ou able nodes s abilises a a ound 0.996 when he numbe o global
edges is g ea e han 140000.
Changing he a ailable cos
The las pa ame e we ha e s udied in o de o unde s and how p oblem condi ions al e
esul s is he a ailable budge . I is ob ious ha inc easing he a ailable budge neces-
sa ily inc eases he a e age p opo ion o a ou able nodes, since p e ious assignmen s o
labels can be eused and comple ed o sol e g aphs which ha e he same s uc u e. How-
e e , no hing can be said abou he end ype be o e simula ing ins ances and ob aining
conclusions.
Figu e 10: P opo ion o a ou able nodes compa ed o o al a ailable cos . 50 di e en
g aphs we e gene a ed and sol ed o each da a poin , and we e no eused o o he
da a poin s, in o de o ob ain a e age esul s. The end seems o be exponen ial i he
p opo ion o opposing nodes is conside ed ins ead ( he coe icien o de e mina ion, R2,
equals 0.943). All used ins ances o g aphs a e gene a ed using he s anda d me hods
desc ibed in 4.1. 26 di e en a ailable budge s ({0,4000,8000,...,100000}) ha e been
conside ed.
E en hough he e seems o be an exponen ial end, i migh no be a co ec assump ion.
I is in e es ing o see ha he success a e s abilises a a o al a ailable cos o a ound
70000. I seems ha no hing else can be done beyond ha poin o con ince mo e nodes,
since he emaining nodes which disag ee a e almos always locked and a e in luenced by
o he nodes which disag ee and a e locked as well.
4.3 Using a gene ic algo i hm
A gene ic algo i hm has been designed and used o imp o e he esul s o Alg7. This
algo i hm is ini ialised by using he esul s om Algo i hms Alg5 o Alg9. C osso e and
mu a ion a e de ined as ollows.
Fo c osso e , each sample is andomly anked be o e c osso e akes place; nodes which
appea be o e in he sample a e anking a e mo e impo an han nodes which appea
a he end. C osso e consis s o selec ing he mos impo an nodes om each sample
(i e a i ely selec ing he mos impo an node le o bo h samples a he same ime, and
49
o cou se no selec ing a node again i he e a e epe i ions), and s op selec ing when i
is no longe possible because no mo e budge is a ailable.
Fo mu a ion, he g aph is simula ed o 20 cycles and a b ibed node is unma ked i i
is de ec ed ha he sum o he weigh s o incoming edges ( om nodes whose label alue
is 1) is high (>0.6), since i is assumed ha he label o ha node would become 1
anyway, due o in luence om neighbou s. Then, new nodes a e added andomly by using
he weigh which has been gi en back by unma ked nodes. No mo e han 10 nodes a e
unma ked pe i e a ion in o de no o subs an ially al e a solu ion when mu a ing.
E e y i e a ion s a s by conside ing i e ins ances. C osso e s o each possible combi-
na ion a e done, and each ins ance is also andomly mu a ed six imes. The bes i e
ins ances o all o hese modi ica ions, including he ini ial ones, a e used in he nex
i e a ion.
In o de o es his gene ic algo i hm, we ha e chosen he a ailable budge s c1= 20000
and c2= 40000, and un his gene ic algo i hm using 50 g aphs o each o hese budge s.
The ob ained p opo ions o a ou able nodes can be ound in Table 2.
Cos used Alg7 10 i e a ions 20 i e a ions 30 i e a ions 40 i e a ions
c10.7045312 0.7063823 0.7138368 0.7194051 0.7231830
c20.8592466 0.8647835 0.8674822 0.8714732 0.8751670
Table 2: A e age p opo ion o a ou able nodes ob ained when applying he gene ic
algo i hm desc ibed in his sec ion o he s anda d p oblem, which has been modi ied by
changing he a ailable cos o c1and c2. 50 di e en ins ances o each cell we e used.
Al hough he e seems o be some imp o emen and i has been checked using [2] ha he
imp o emen is s a is ically signi ican , his algo i hm akes a e y long ime o un, and
he imp o emen is no e y signi ican . I migh be possible o ob ain simila o be e
esul s by conside ing addi ional heu is ics o a mo e e icien gene ic algo i hm.
Howe e , i is ue ha he gene ic algo i hm we ha e conside ed seems o be be e han
he bes basic s a egy (Alg7), and i migh also be he case ha he imp o emen is
no e y signi ican because he p opo ion o a ou able nodes canno be inc eased much
mo e o hese ins ances using any me hod.
50
5 Conclusion
This wo k has allowed us o ob ain impo an complexi y p ope ies abou opinion g aphs;
hey a e essen ially as exp essi e as Tu ing machines. The e o e, ully sol ing op imisa ion
p oblems in o de o de e mine a good s a egy o in luencing a popula ion’s opinion is,
in mos cases, no easible. All ele an p oblems o ca ying ou his ask a e a leas
NP-ha d, and he mos complex ones a e e en PSPACE-ha d.
In spi e o his hu dle, we ha e been able o p opose ela i ely simple s a egies o sol e
one o he NP-comple e p oblems success ully using opinion g aphs whose p ope ies
make hem simila o eal-wo ld examples. As we ha e al eady men ioned, he g aphs
we ha e conside ed when p o ing complexi y p ope ies a e e y di e en om eal-wo ld
examples. I appea s ha eal-wo ld g aphs a e much mo e egula , and e y simple
heu is ics yield good esul s. O cou se, he pe o mance o g eedy s a egies can be
imp o ed by empo a ily locking p omising nodes in in e media e s eps and using gene ic
algo i hms, which imp o e he p opo ion o a ou able nodes e en mo e.
E en hough he esul s we ha e ob ained a e sa is ying and p o ide a lo o insigh ,
he e emains much o be done. On he one hand, mo e ypes o g aphs could ha e been
analysed. Besides, he ypes o g aphs we ha e conside ed could ha e been analysed in
g ea e dep h. On he o he hand, no many di e en heu is ics ha e been used o analyse
he p oblem we wan ed o op imise, and mo e complex gene ic algo i hms could ha e been
used o ob ain be e esul s.
The p ac ical p oblem we ha e analysed is ela i ely gene al, bu some a ia ions o he
p oblem could be conside ed in u he esea ch. Fo ins ance, he weigh dis ibu ion
could be modi ied. In he eal wo ld, people who a e in luen ial a e usually mo e expensi e
o b ibe han people whose in luence is lowe . Taking his co ela ion in o accoun would
make he g aph e en mo e ealis ic.
The heo e ical esul s we ha e ob ained a e e y comple e and ha e made us unde s and
he ype o p oblems which a ise when s udying opinion g aphs. Ne e heless, he e a e
aspec s which ha e no been co e ed, some o which a e a e age case complexi y and
app oximabili y classes. Mo e esea ch could be done in o de o p o ide a mo e accu a e
classi ica ion o he heo e ical p oblems we ha e discussed in his wo k.
The e is one mo e aspec which could be s udied o gene alise he ob ained esul s; he
ansi ion unc ion used o upda e node labels in opinion g aphs in gene al could be
made p obabilis ic and possibly non-linea o compa e how nodes beha e depending on
he conside ed unc ion. A lo o ecen pape s ha e ocused on non-linea o e models,
and applying hese models o ou p oblem would make i possible o ob ain e y gene al
conclusions which could e en be applied ou side he scope o his wo k.
51
Re e ences
[1] Bina y Indexed T ee : Range Upda e and Range Que ies. h ps://www.
geeks o geeks.o g/bina y-indexed- ee- ange-upda e- ange-que ies/.
[Accessed 13-Ma ch-2023].
[2] Non-pa ame ic mul iple g oups one s all. h ps:// ec.ci ius.usc.es/s ac/
anking.h ml. [Accessed 15-Ap il-2023].
[3] R´eka Albe and Albe -L´aszl´o Ba ab´asi. S a is ical mechanics o complex ne wo ks.
Re iews o Mode n Physics, 74(1):47–97, Janua y 2002.
[4] Sanjee A o a and Boaz Ba ak. Compu a ional Complexi y: A Mode n App oach.
Camb idge Uni e si y P ess, 2009.
[5] Claudio Cas ellano, Miguel A. Mu˜noz, and Romualdo Pas o -Sa o as. Nonlinea
q- o e model. Physical Re iew E, 80(4), Oc obe 2009.
[6] Raymond Chiong and Michael Ki ley. E ec s o i e a ed in e ac ions in mul i-
playe spa ial e olu iona y games. IEEE T ansac ions on E olu iona y Compu a ion,
16(4):537–555, Augus 2012.
[7] Ka i Elo an a. Vo e dynamics in de e minis ic cellula au oma a, olume 8, pages
51–58. De G uy e , 1996.
[8] Juan Fe n´andez-G acia, K zysz o Suchecki, Jos´e J. Ramasco, Maxi San Miguel, and
V´ıc o M. Egu´ıluz. Is he o e model a model o o e s? Physical Re iew Le e s,
112(15), Ap il 2014.
[9] Roge Guime `a, Leon Danon, Albe D´ıaz-Guile a, F ancesc Gi al , and Alex A enas.
Sel -simila communi y s uc u e in a ne wo k o human in e ac ions. Physical Re iew
E, 68(6), Decembe 2003.
[10] S u e Holm. A simple sequen ially ejec i e mul iple es p ocedu e. Scandina ian
Jou nal o S a is ics, 6:65–70, 1979.
[11] John E. Hopc o , Rajee Mo wani, and Je ey D. Ullman. In oduc ion o au oma a
heo y, languages, and compu a ion. Pea son, Uppe Saddle Ri e , NJ, 3 edi ion, June
2006.
[12] Hui-Jia Li, Lin Wang, Yan Zhang, and Ma jaˇz Pe c. Op imiza ion o iden i iabili y
o e icien communi y de ec ion. New Jou nal o Physics, 22(6):063035, June 2020.
[13] Thomas M. Ligge . S ochas ic In e ac ing Sys ems: Con ac , Vo e and Exclusion
P ocesses. Sp inge Be lin Heidelbe g, 1999.
[14] Naoki Masuda, Na hanael Gibe , and Sidney Redne . He e ogeneous o e models.
Physical Re iew E, 82(1), July 2010.
[15] Ma jaˇz Pe c, Jes´us G´omez-Ga de˜nes, A ila Szolnoki, Luis M. Flo ´ıa, and Yami
Mo eno. E olu iona y dynamics o g oup in e ac ions on s uc u ed popula ions: a
e iew. Jou nal o The Royal Socie y In e ace, 10(80):20120997, Ma ch 2013.
52

[16] Wal e J. Sa i ch. Rela ionships be ween nonde e minis ic and de e minis ic ape
complexi ies. Jou nal o Compu e and Sys em Sciences, 4(2):177–192, 1970.
[17] Vishal Sood, Tibo An al, and Sidney Redne . Vo e models on he e ogeneous ne -
wo ks. Physical Re iew E, 77(4), Ap il 2008.
[18] Duncan J. Wa s and S e en H. S oga z. Collec i e dynamics o ‘small-wo ld’ ne -
wo ks. Na u e, 393(6684):440–442, June 1998.
53
Appendix I: Mo e in o ma ion abou used so wa e
In o de o simula e he p oblem and he pe o mance o he algo i hms we ha e consid-
e ed, as well as o w i ing his documen , wo compu e p og ams ha e been de eloped
and used.
One o hem gene a es andom g aphs wi h gi en pa ame e s and simula es hei pe o -
mance, jus like i has been desc ibed in his documen . The e has no been enough ime
o make his p og am use - iendly, so i has been used by designing es s as pa o he
p og am and unning hem sepa a ely.
The o he p og am has been designed o help he au ho o c ea e he igu es o his docu-
men and he inal p esen a ion. I is impossible o ind any o he ools which can gene a e
igu es like he ones o his documen and success ully in eg a e hem in a L
A
T
EX docu-
men , so i seemed necessa y o de elop such a p og am. The p og am i e a i ely isi s
olde s o he loca ion om which i is un, and looks o TikZ code and sc ip s whose
syn ax has been c ea ed by he au ho . This p og am hen ans o ms TikZ code as in-
dica ed by he sc ip s o c ea e new TikZ code which in eg a es ans o med copies o
he o iginal TikZ code. Using hese sc ip iles migh no be e y in ui i e, bu i was
ound o be e y p ac ical, since one o he o iginal TikZ iles can be modi ied and he
ans o med TikZ code can be ins an ly egene a ed.
Two classes o he code which gene a es andom opinion g aphs a e e ac o ed code ob-
ained om h ps://www.geeks o geeks.o g/bina y-indexed- ee- ange-upda e- ange-que ies/
o implemen Algo i hm 2 e icien ly. The license o his code is CC-BY-SA, whose ull ex
can be ead a h ps://c ea i ecommons.o g/licenses/by-sa/2.0/. This license has
been eused o ha pa o he code and i is indica ed in code iles.
All o he code which has been w i en and used o his wo k has been submi ed along
wi h his documen and will be made a ailable a h ps://gi hub.com/Ma in-ga when
possible.
54
Appendix II: Raw da a examples
La ge samples o aw da a ha e been submi ed along wi h his documen , and e en la ge
samples o aw da a will la e be published a h ps://gi hub.com/Ma in-ga when
deemed app op ia e. He e we gi e a small example, which co esponds o p opo ions
o a ou able nodes ob ained o gene a ing he i h da a ow o Table 1. Each en y is
calcula ed using he p opo ions ob ained om 50 ins ances.
Alg5 Alg6 Alg7 Alg8 Alg9
0.87236 0.87672 0.90224 0.89008 0.90672
0.85836 0.86488 0.88288 0.85880 0.87560
0.87752 0.90848 0.91012 0.90732 0.91392
0.87684 0.91644 0.92016 0.91260 0.91960
0.87560 0.89868 0.90756 0.89604 0.90524
0.86604 0.86564 0.89108 0.87944 0.89136
0.89832 0.92832 0.93644 0.93716 0.94596
0.89148 0.89808 0.91628 0.89432 0.90344
0.89500 0.90968 0.92036 0.90508 0.91544
0.86404 0.90040 0.91092 0.88528 0.89972
0.90084 0.90472 0.92080 0.90104 0.91496
0.87920 0.88972 0.91000 0.89124 0.90856
0.87080 0.89908 0.90672 0.88912 0.89796
0.87104 0.90492 0.91140 0.89812 0.90992
0.87608 0.89860 0.91252 0.89028 0.90496
0.87884 0.88804 0.90436 0.88648 0.90284
0.88812 0.89192 0.90560 0.89312 0.90492
0.85032 0.86084 0.88200 0.85272 0.88176
0.87400 0.89500 0.91100 0.88876 0.89672
0.89408 0.93196 0.93572 0.92984 0.93256
0.87404 0.91648 0.91988 0.90088 0.91588
0.85096 0.86080 0.88040 0.85340 0.87020
0.86152 0.88620 0.90412 0.89280 0.89920
0.87464 0.91716 0.92304 0.91232 0.91764
0.90408 0.92512 0.92696 0.90288 0.92612
0.87676 0.90376 0.91744 0.88552 0.90788
0.85656 0.88808 0.89992 0.88192 0.88868
0.86632 0.87516 0.89652 0.85888 0.87940
0.87708 0.88844 0.90636 0.89140 0.89508
0.85544 0.89924 0.90964 0.89432 0.90912
0.89256 0.90904 0.93112 0.92272 0.92960
0.89480 0.91944 0.92896 0.92184 0.92820
0.90072 0.93552 0.93480 0.92920 0.92972
0.88712 0.90660 0.92520 0.89572 0.91592
0.86960 0.90424 0.90976 0.90164 0.91360
0.87304 0.88144 0.89064 0.87468 0.89016
0.86236 0.87400 0.89396 0.87000 0.88816
55
0.88404 0.91300 0.92468 0.91464 0.92060
0.89676 0.91836 0.93636 0.92120 0.93420
0.86796 0.90228 0.91576 0.89788 0.90452
0.88596 0.94116 0.93664 0.93068 0.93936
0.83724 0.85844 0.87712 0.85460 0.87584
0.89016 0.92668 0.93528 0.92684 0.93084
0.87508 0.89780 0.90896 0.90412 0.91328
0.90988 0.92224 0.93380 0.90308 0.91824
0.88132 0.91360 0.92188 0.92392 0.92752
0.88300 0.89252 0.91012 0.87832 0.90564
0.86080 0.88308 0.89240 0.87196 0.88372
0.87432 0.90016 0.91456 0.89748 0.91196
0.85888 0.87784 0.88752 0.87860 0.89028
56