Computability and Complexity of opinion dynamics

Computability and Complexity of opinion dynamics Computabilidad y Complejidad de la din´ amica de opiniones Bachelor’s Thesis (Trabajo de Fin de Grado) Academic year: 2022 - 2023 Author Mart´ın G´omez Abej´on Directors Ismael Rodr´ıguez Laguna Fernando Rubio Diez Doble Grado en Ingenier´ ıa Inform´ atica - Matem´ aticas Facultad de Inform´ atica Universidad Complutense de Madrid Contents 1 Introduction 4 1.1 Theoreticalframework ............................. 4 1.1.1 Spacecomplexity............................ 5 1.1.2 A standard model used for opinion dynamics . . . . . . . . . . . . . 6 1.1.3 Real-world social graphs . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Objectives and methodology . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Notation used in this work . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Definition of the general problem 10 2.1 General definition of opinion graphs . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Graphs based on lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 The deterministic problem is increasing . . . . . . . . . . . . . . . . . . . . 16 3 Complexity properties of opinion graphs 20 3.1 Opinion graphs are functionally complete . . . . . . . . . . . . . . . . . . . 20 3.2 Building a Turing machine with opinion graphs . . . . . . . . . . . . . . . 23 3.3 Decidability and complexity properties of opinion graphs . . . . . . . . . . 33 4 Heuristic analysis of real-world graphs 43 4.1 Theproblemweconsider............................ 43 4.2 Basic strategies to solve the problems and obtained results . . . . . . . . . 45 4.2.1 General comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.2.2 Benchmarks of the best basic strategy . . . . . . . . . . . . . . . . 47 4.3 Using a genetic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5 Conclusion 51 1 Abstract In this work, we discuss and prove several theoretical results related to computability and complexity properties of an opinion dynamics model we define. We also try to find low-complexity heuristics and algorithms which let us obtain approximate solutions of an NP-complete problem based on our model, and run simulations to determine to what extent these heuristics are effective. Although we conclude that most practical problems related to our model are undecidable in the infinite case and PSPACE-complete or NPcomplete in the finite case, the obtained low-complexity algorithms are effective at solving instances whose structure and properties are similar to those of real-world examples. Keywords Complexity, approximability, PSPACE-completeness, undecidability, heuristics, greedy algorithms, genetic algorithms. 2 Resumen En este trabajo, se abordan y demuestran varios resultados te´oricos relacionados con las propiedades de computabilidad y complejidad de un modelo de din´amica de opiniones que definimos. Tambi´en intentamos encontrar heur´ısticas y algoritmos de baja complejidad que nos permitan obtener soluciones aproximadas de un problema NP-completo basado en nuestro modelo, y ejecutamos simulaciones para determinar en qu´e medida estas heur´ısticas son efectivas. A pesar de que concluimos que la mayor´ıa de problemas pr´acticos relacionados con nuestro modelo son indecidibles en el caso infinito y PSPACEcompletos o NP-completos en el caso finito, los algoritmos de baja complejidad obtenidos son efectivos resolviendo instancias cuya estructura y propiedades son parecidas a las de ejemplos del mundo real. Palabras clave Complejidad, aproximabilidad, PSPACE-completitud, indecibilidad, heur´ısticas, algoritmos voraces, algoritmos gen´eticos. 3 1 Introduction In this work we use graphs to model opinion dynamics, discuss the complexity of the model we use and estimate to what extent real-world graphs which represent acquaintances can be processed by efficient enough algorithms to obtain relevant information. Studying opinion dynamics has many applications in modern society, since modifying the opinion of large groups of people can modify their behaviour and have important consequences, such as an increase in sales, an unexpected election result or a behavioural change. Therefore, a lot of resources are spent every year by various entities in order to change people’s opinion on a certain subject. Information and techniques for making this task easier are very valuable. This work provides certain insight into influencing opinion dynamics, so it can be directly used, helping to achieve better results. As part of this work, we have analysed how difficult this task is. We have also proposed, tested and compared various techniques for changing people’s opinion using limited resources. These techniques can be applied in real-world cases if enough information is known about the group of people whose opinion needs to be changed. Performance results for all proposed techniques have been empirically tested by using graphs of acquaintances whose design makes them very similar to real-world graphs of acquaintances. This is done to ensure empirical conclusions can be applied, since these conclusions might be different if the used graphs are not similar to real-world instances. In order to follow what has been done in this work, the reader needs to be familiar with certain relevant theoretical notions and research related to this topic. In this first section, we briefly discuss this necessary background. The references we use are self-contained and appropriate for readers who are not familiarised with any of the topics. We deliberately choose not to discuss concepts which are part of the syllabus of any Bachelor’s degree in Computer Science, such as the classes Pand NP. All this omitted theory can be found in [11]. It can also be found in [4], although the contents of [4] are much broader than those of [11]. The theoretical results we obtain are rather discouraging; problems related to infinite opinion graphs are not decidable, and for finite opinion graphs most interesting problems are either NP-complete or PSPACE-complete. However, by using greedy algorithms and genetic strategies, we are able to obtain good solutions for a problem which is NPcomplete in general. Therefore, solving problems related to opinion dynamics in real-world contexts is feasible, even if the obtained solutions might not be optimal. 1.1 Theoretical framework We now discuss all non-standard prerequisites we need for this work. This prerequisites consist of three major blocks. One of them covers certain aspects of advanced complexity and computability theory, while the latter two are related to how opinion dynamics are modelled with graphs, and which is the best approach to obtain realistic graphs which are topologically similar to real-world networks of acquaintances. 4 1.1.1 Space complexity We briefly explain the notions we need to know about space complexity in order to study how complex opinion dynamics are. The concepts we discuss have been extracted from [4]. Space complexity is not studied as part of a standard Bachelor’s degree. Just like with time complexity, we can define classes of problems which can be solved if a certain amount of space is given. Namely, we have the following definitions. Definition 1 (Space-bounded computation).A language L, or its corresponding problem P, is said to belong to SPACE(s(n)) if there is a constant Cand a deterministic Turing machine Mwhich decides L, thus solving P, such that not more than C·s(n)different cells are ever visited by M’s head when the length of the input equals n. We similarly define the class NSPACE;L∈NSPACE(s(n)) if there is a constant C and a non-deterministic Turing machine Mwhich decides L, such that not more than C·s(n)different cells are ever visited by M’s head when the length of the input equals n, for any set of non-deterministic choices taken by M. Time and space complexity are related to each other, since a Turing machine which runs for tcycles cannot visit more than tcells, and the number of different possible global configurations of a Turing machine Mwhich does not visit more than ccells is bounded by K1·Kc 2, for certain K1, K2which depend on M. Theorem 1 (Time and space complexity).The following set inclusions hold. DTIME(s(n)) ⊆SPACE(s(n)) ⊆NSPACE(s(n)) ⊆DTIME 2O(s(n)) A rigorous proof of this result can be found in [4]. The most relevant space complexity classes in this work are PSPACE def =[ c∈N SPACE(nc) and NPSPACE def =[ c∈N NSPACE(nc) which intuitively consists of all problems which can be solved using a polynomial amount of space. Just like for NP, there exists a notion of completeness, which we now define. Just like in [4], we use the symbol ≤pfor polynomial-time Karp reducibility. Definition 2 (PSPACE-completeness).A language L′is said to be PSPACE-hard if and only if ∀L∈PSPACE,L≤pL′. If L′is PSPACE-hard and L′∈PSPACE, it is said to be PSPACE-complete. It can be proved that the language Laccsp def ={(M, w, 1n)|Maccepts win space n}(1) is PSPACE-complete, where Mrepresents a variable semi-infinite tape Turing machine. Of course, it is indispensable that there exists a well-defined encoding which can be used to represent every possible Min a string. It is standard to assume that this encoding makes it possible to use polynomial-time algorithms for encoding and decoding for use in a universal Turing machine; for certain encodings for which infinitely many words represent 5 Turing machines whose numbers of states are not bounded by a multiple of a power of the length of the strings, the existence of these polynomial-time algorithms cannot be guaranteed. We use the same construction and assumptions as in [4]; polynomial-time algorithms exist, since Turing machines are encoded by listing the table of their transition functions. We make some additional remarks which are relevant for this work. It is almost immediate to prove Laccsp is PSPACE-complete if one is familiar enough with PSPACE. Nevertheless, it is not a satisfying PSPACE-complete language, since it does not give any intuition about what a PSPACE-hard problem looks like. A better example of a PSPACE-complete problem is the language of all quantified Boolean formulas which are true. A quantified Boolean formula has the structure Q1x1Q2x2. . . Qnxnφ(x1, x2, . . . , xn),(2) where ∀i∈Nn, Qi∈ {∀,∃} and φ(x1, x2, . . . , xn) is a propositional logic formula on variables x1, x2, . . . , xn. A proof of the PSPACE-completeness of this problem can be found in [4]. This PSPACE-complete problem provides more insight; since the quantifiers can appear in any order and alternate as frequently as needed, it is possible to use formulas like (2) to encode (possibly non-deterministic) two-player games. Each ∀represents a choice taken by the opponent, or a random event which takes place in the game, while each ∃ represents a voluntary choice taken by the player. One of these formulas is true if and only if there exists a strategy which leads to victory1. We finally state one last property without proving it; PSPACE =NPSPACE. It is a direct consequence of Theorem 1 from [16], which states that if s(n)≥log(n), then NSPACE(s(n)) ⊆SPACE(s(n)2). 1.1.2 A standard model used for opinion dynamics Many different models have been used to try to model human interactions and how a person’s opinion is determined depending on their entourage and their own initial opinion. The vast majority of these models are continuous stochastic processes in which an individual opinion is updated using a stochastic transition function which takes the initial opinion of a person and its interactions with others into account. A very used model for this purpose is the voter model from [13]. This model is a continuous time Markov process in which nodes in a lattice (Zd) interact with each other locally. Nodes can agree (1) or disagree (0), and the transition rates for each node are given by a function c(x, η), where xis a position in Zdand η∈ {0,1}Zdis the current state of the whole lattice. The higher cis for a specific node xat a given point in time, the more likely it is that the opinion of xchanges. cis assumed to have the following properties. (1) Let η1and η0be the states in which every node agrees or disagrees, respectively. 1If (2) is thought of as a game, victory is encoded in φ(x1, x2, . . . , xn), and the game which is played goes as follows: from left to right, a player determines the value of all ∃quantifiers, while the opponent determines the value of all ∀quantifiers. The ultimate goal for the player is to make φ(x1, x2, . . . , xn) true, while the opponent tries to make φ(x1, x2, . . . , xn) false. 6 Then, ∀x∈Zd, c(x, η1) = c(x, η0) = 0. This means nodes keep having the same opinion if no other node disagrees with them. (2) Opinions are symmetric; transition rates are the same if the opinions of all nodes are flipped. Quantitatively, c(x, ηα) = c(x, ηβ) if ∀y∈Zd, ηα(y) + ηβ(y) = 1. (3) Transition rates for a specific node xare higher when nodes uniformly disagree more with x. The word uniformly is very important in this property; since it is not known to what extent each individual node influences x, nothing can be said about the global change of the transition rate of xif some other nodes start to disagree with x, while others start to agree. This property can be expressed using two equivalent equations. If ∀y∈Zd, ηα(y)≤ηβ(y) and ηα(x) = ηβ(x) = 0, then c(x, ηα)≤c(x, ηβ). If ∀y∈Zd, ηα(y)≤ηβ(y) and ηα(x) = ηβ(x) = 1, then c(x, ηα)≥c(x, ηβ). (4) The transition rates are invariant under translations in Zd; if the opinions of all nodes are translated using a vector v, the transition rates can be obtained by translating the original transition rates using vas well. Despite the name of this model, it was originally not conceived for modelling opinion dynamics. However, it has been shown that modified versions of this model can accurately describe opinion dynamics in real-world contexts (see [8]). However, the original model from [13] has an issue; the graph topology used (a lattice) and the properties of transition rates, especially being invariant under translation, make the model very different from real-world social networks, as we will see. For instance, in [8], the graph of interactions which is considered is very different from the original graph proposed in [13]. In this work, we have analysed the complexity of a modified voter model; instead of being a continuous process, it is discrete. Also, it is deterministic, unlike almost any other voter model or variant thereof which has previously been considered by other authors. Certain deterministic models have been considered by certain authors, such as in [7], but they are very different from the model we consider in this work. We analyse the complexity and expressiveness of this deterministic model, which has never been done before in this context, to the best of our knowledge. Due to the law of large numbers, it can be assumed that a deterministic model is capable of simulating global properties of opinion dynamics. 1.1.3 Real-world social graphs The voter model discussed in [13] and its variants have been used in many different network topologies. Examples of this are [8], as well as [17], [14] and [5]. Most authors do not consider networks which are similar to real-life social interaction graphs. In [8], this is done successfully, but not all features of real-life graphs, such as average shortest path length and degree distribution (see below), are considered. In [17], the considered graphs are very different from real-life, as they are not sparse and their clustering coefficients (see below) are different from real-life coefficients like those obtained in [3]. In this work, we consider all relevant properties of social networks when modelling them. We now discuss the most relevant properties. 7 Although the dynamics of many voter models and other games have been considered for lattices (apart from the voter model, there are other examples in other contexts, such as [6] and [15], in which not only Znis considered), it has been shown by many authors (see, for example, [3] and [9]) that lattices are very different from real-life social networks. In [3], many different examples are studied and three important properties are deduced. (1) The average shortest path length is very small, and grows logarithmically compared to the number of nodes in the network. Random graphs (whose edges are determined randomly and independently) have this property. Graphs which have this property are known as small-world networks. (2) The clustering coefficient is relatively high compared to random graphs. This coefficient is obtained for each node by considering its neighbours and calculating the proportion of edges between them that exist. When the value of this coefficient is 1, the neighbours form a complete graph, and when it is low, it is highly unlikely that neighbours know each other. The average value of these coefficients is the clustering coefficient of the graph. (3) The distribution of node degrees follows a power law. This was studied in [3] and related papers. In order to obtain such a network, edges need to be added by giving more probability to nodes which are already very connected. A model which takes this approach is the Barab´asi-Albert model discussed in [3]. It has been shown in [18], as well as in [3], that combining different types of edges corresponding to lattices and more global edges, chosen randomly or depending on the degree of the nodes, yields networks which satisfy all of the properties discussed above. There exist other models or properties which characterise real-life social networks, which have been discussed in papers like [9] and [12], but these other approaches are very similar to the one taken in [3]. 1.2 Objectives and methodology In this work, we identify and prove the most important complexity properties of a deterministic model we define. This model is based on the voter model from [13], but it is modified by making it deterministic and discrete, and modifying its topology by considering lattices of blocks of nodes, instead of lattices of nodes. We consider each block to be a community which is influenced by nearby communities. It is true that the average shortest path length of this model remains high, as in the original voter model. Nevertheless, it is useful for proving worst-case complexity properties, and we will later modify it to make it more realistic when analysing its behaviour in real-world conditions. Despite the worst-case complexity properties we obtain, we try to simulate real-world examples of this model and use heuristic algorithms in order to evaluate to what extent these can give satisfying answers to problems whose exact solutions cannot be obtained easily. For this part of the work, we consider graphs which are as similar to real-world social graphs as possible using the properties discussed above, and consider different heuristic algorithms to solve problems related to these graphs. Additional information about the methodology used for these simulations and algorithms can be found in Section 4. 8 edges whose destination is Ip(r). A graph is said to be connected as successor to an interface Iif the same conditions for connection as predecessor, interchanging the roles of ↑and ↓, apply for a given injective function Is:Nk→V. The nodes which belong to the image of Ipare called phantom nodes. When it is not known if the block is connected as a successor or as a predecessor, we use the notation Ip,s for the injective function which marks phantom nodes. In Definition 3, the function Ip,s uniquely assigns a phantom node to each connection. Conditions (2) and (3) merely state that the edges which connect phantom nodes to other nodes should behave as intended by the interface I. If I(r) =↑, the phantom node Ip,s(r) behaves as a tube leaving the predecessor and entering the successor. On the other hand, if I(r) =↓, the phantom node Ip,s(r) behaves as a tube leaving the successor and entering the predecessor. Definition 4 makes it possible to connect several interfaces to a single block. In order to have a consistent definition which can be used to interconnect blocks in an L-shaped graph, phantom nodes must be different for each connection to an interface and they cannot interfere with each other. The latter condition is quite important in order to guarantee all connections are local and the L-shaped graph is well defined. Definition 4 (Opinion graph connected to multiple interfaces).An opinion graph G= (V, E)is said to be connected to multiple interfaces {Ij}j∈Jvia the functions {Ij p,s}j∈Jif it is connected to each interface Ijvia the function Ij p,s and the following conditions are satisfied. (1) The images of the injective functions {Ij p,s}j∈Jare pairwise disjoint. (2) There is no edge whose source vsand destination vdare in the union of the image sets of {Ij p,s}j∈J. The core Gcof a graph Gwhich is connected to multiple interfaces {Ij}j∈Jvia the functions {Ij p,s}j∈Jconsists of the graph G, from which all phantom nodes of all interfaces and all edges which leave or enter phantom nodes have been removed. In general, the core of a given block is not an opinion graph, since the sum of the weights of the influential edges of each node is not necessarily 1 after removing some of them. However, the sum of the weights becomes 1 again when the core is connected to other cores in an L-shaped graph. We now have enough tools to formally define what an L-shaped graph is, given an arbitrary L. This definition formalises the concepts discussed above. Definition 5 (L-shaped graph).Given L=E1×E2× · · · × Ed, an L-shaped graph is completely determined by the following definitions: (1) Interfaces {Ij}j∈Ndfor each of the ddimensions of L. (2) Finite opinion graphs GRfor all R∈Rel(L). It is necessary that these graphs be connected to the following interfaces. 15 (a) For all elements R∈Rel(L)and all j∈Nd, if the j-th element of Ris not Lst, then GRmust be connected to Ijas a predecessor. (b) For all elements R∈Rel(L)and all j∈Nd, if the j-th element of Ris not Fst, then GRmust be connected to Ijas a successor. The L-shaped graph Gcorresponding to these definitions consists of the disjoint union of the graphs Gl∼ =Gc Rel(l)for each l∈L, which are interconnected by adding the following edges. For all j∈Nd, e = (e1, e2, . . . , ej−1, ej, ej+1, . . . , ed)∈L, given Ij:Nk→ {↑,↓}, if ej+def = (e1, e2, . . . , ej−1, ej+ 1, ej+1, . . . , ed)∈L, then an edge is added to the L-shaped graph as follows for each r∈Nk. (1) If Ij(r) =↑, its source is the node originally connected to Ij p(r)in Gc e, its destination is the node originally connected to Ij s(r)in Gc ej+and its weight is the one of the only non-reflexive edge whose source is Ij s(r)in GRel(ej+). (2) If Ij(r) =↓, its source is the node originally connected to Ij s(r)in Gc ej+, its destination is the node originally connected to Ij p(r)in Gc eand its weight is the one of the only non-reflexive edge whose source is Ij p(r)in GRel(e). Each of the graphs Glis called a block. When constructing Gby following this definition, it is guaranteed that the sum of the weights of all edges of inf(vi)equals 1, for all v∈G. However, there might be edges with common source and destination if a node in GRinfluences or is influenced by several phantom nodes of an interface function Ip,s. If this happens, all these edges are removed and replaced by a single edge whose source and destination are the ones of the removed edges, and whose weight is the sum of the weights of the removed edges. Blocks are interconnected in Definition 5 by connecting the two sides of interfaces to which contiguous blocks are connected. Figure 5 shows how defining two interfaces and six graphs which are connected to those interfaces following a {Fst,Mid}×{Fst,Mid,Lst} arrangement characterise the N×N6-shaped graph depicted in Figure 3 via Definition 5. The reader can also have a look at Figure 6, which provides intuition in how blocks are connected to each other and how edge weights are assigned. 2.3 The deterministic problem is increasing Intuitively, the transition function we have defined for the general instance of an opinion graph is increasing when restricted to a specific node, and its properties are similar to those of increasing functions in general. We will now define these concepts more precisely and show how they limit certain expressiveness properties of the deterministic version of the problem. Given an opinion graph G= (V, E), LG def ={S:V7→ {0,1}} denotes the set of all possible labellings of 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 Figure 5: Definitions for the six necessary types of graphs used to define the graph from Figure 3. Reflexive edges and the weights of all edges are not 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 Figure 6: Definition of G(Mid,Mid)on the left and part of the resulting Z×Z-shaped graph on the right. Reflexive edges and some of the weights are not shown. The weights of connections to an interface which leave the block always equal 1 in GRby definition, and they are replaced by the weights of incoming connections when constructing an L-shaped graph, as it can be seen on the right. Definition 6 (partial order on LG).Given an opinion graph G= (V, E)we define a partial order on the functions LGby defining Sα≤Sβdef ⇐⇒ ∀v∈V, Sα(v)≤Sβ(v). This way we partially order the possible states of the graph G; the definition of the partial order implies that Sα≤Sβwhen and only when all node labels in Sαare lower than or equal to the corresponding labels in Sβ. We now give another definition which naturally extends the concept of increasing functions to the partial order in LG. Definition 7 (increasing functions LG7→ LG).Given an opinion graph G= (V, E), a function f:LG7→ LGis increasing if and only if ∀Sα, Sβ∈LG, Sα≤Sβ=⇒f(Sα)≤f(Sβ). The following theorem has a lot of consequences and significantly reduces the expressiveness of opinion graphs. Even though we will later prove opinion graphs are essentially Turing-complete, this theorem implies we need to be careful when defining the instances; in practice, we will need to construct pairwise non-comparable instances in order to guarantee that they are different enough. Theorem 2. Given an opinion graph G= (V, E), the transition function fwhich maps a certain state of labels in G(St) to the next state (St+1) is increasing. 18 Proof. Let Sα t, Sβ t∈LGand assume Sα t≤Sβ t. From the definition of ≤we need to prove that given any vertex vj∈V,Sα t+1(vj)≤Sβ t+1(vj). The inequality X vi∈infl(vj) Sα t(vi)|eij| ≤ X vi∈infl(vj) Sβ t(vi)|eij| is satisfied because Sα t(vi)≤Sβ t(vi)∀vi, the weights of the edges are non-negative and inequalities are preserved by sums. The function Sα t+1(vj) =      0,if Pvi∈infl(vj)Sα t(vi)|eij|<1 2, Sα t(vj),if Pvi∈infl(vj)Sα t(vi)|eij|=1 2, 1,if Pvi∈infl(vj)Sα t(vi)|eij|>1 2, seen as a function whose arguments are Pvi∈infl(vj)Sα t(vi)|eij|and Sα t(vj), is increasing6. That implies each individual output of the function Sα t+1 in function of Sα tis increasing, which in turn implies the global transition function is increasing. Two corollaries can be easily deduced from the previous theorem. Their proofs are trivial and not particularly relevant for the rest of the text, so we list them for completeness without proving them. Corollary 1 (inequalities relating instances preserved).Given a graph Gand two instances S= (G, S0), T = (G, T0), if S0≤T0then ∀t∈Z≥0, St≤Tt. Corollary 2 (increasing sequences of labels converge).Given an instance of the problem S= (G, S0), if S1≥S0then Sn1≥Sn2whenever n1≥n2. This implies that for each node vi, the sequence of its labels {vi(t)}tis eventually constant, although the convergence is not necessarily uniform7for all nodes. These corollaries have numerous important consequences; for instance, Corollary 1 implies NOT-gates cannot be simulated by choosing a specific graph, choosing a certain node v (input node) whose label at time 0 equals the input of the NOT-gate, simulating the graph for a fixed number of iterations and asserting the value of a certain node w(output node) equals the output of the NOT-gate; if the final wis 0 when the initial vis 1, changing the instance by decreasing the initial value of vcannot increase the value of w. Besides, Corollary 2 reduces the complexity of simulating opinion graphs for which Sα 1≥Sα 0, since only vertices whose label is 0 need to be reevaluated, and only when the value of a neighbour increases to 1. 6When both arguments increase, the value of the function increases, although maybe not strictly. Note that this implies Sα t+1(vj) increases or stays the same if the labels of Sα tare all increased or left unmodified. 7This means the sequence of values of any given node always converges, since these sequences are constant or flip once from 0 to 1. However, the values do not converge at the same time, and in infinite graphs there might not be a time at which all values have converged. 19 3 Complexity properties of opinion graphs In this section we prove opinion graphs based on lattices are Turing-complete and discuss some of the properties of the complexity of simulating such graphs. The results we obtain are mostly based on one key fact: it is possible to simulate Turing machines with opinion graphs by using a Z-shaped graph in which each block represents a cell and encodes the sets Qand Γ and the transition function δwhich describe the Turing machine. We first describe how opinion graphs are functionally complete, then explain how a Turing machine can be simulated. Last but not least, we deduce several important results about the problem’s complexity. 3.1 Opinion graphs are functionally complete The results discussed in previous sections might seem discouraging, since they show NOTgates cannot be simulated as such in opinion graphs. This makes it necessary to take a different approach when tackling this problem. In order to solve the issue, we are going to prove functional completeness by constructing graphs which duplicate information by keeping the opposite label of each node in another node. This duplication of information does not substantially increase the complexity of the graphs and solves the problem of the increasing transition function; if we consider two states Sα t0and Sβ t0of an opinion graph G= (V, E) which satisfy Sα t0(vi) = 0, Sβ t0(vi)=1, Sα t0(vj) = 1, Sβ t0(vj)=0, they are not comparable with respect to the partial order introduced in Definition 6, so none of the problems we have in Subsection 2.3 apply in this case. We now prove that opinion graphs are functionally complete, just like described in Theorem 3. Theorem 3 (Functional completeness of opinion graphs).Given variables x1, . . . , xtand a propositional logic formula P(x1, . . . , xt), there exists a non-negative integer ∆∈Z≥0, known as the propagation time, and a finite opinion graph G= (V, E)in which certain pairwise disjoint sets of nodes V+ xit i=1 ,V− xit i=1 , C and nodes v+ r, v− r(possibly in one of the former sets) satisfy the following properties: (1) Nodes in the sets V+ xit i=1 ,V− xit i=1 , C do not have any non-reflexive incoming edges, which implies that for any choice of initial values Sα t, Sα t+1(v) = Sα t(v)if v∈V+ xit i=1 ∪V− xit i=1 ∪C. (2) There exists a labelling SCfor nodes in C, such that if ∀i∈Nt, v ∈V+ xi, Sα t0(v) = xi, ∀i∈Nt, v ∈V− xi, Sα t0(v) = ¬xi, ∀v∈C, Sα t0(v) = SC(v), 20 then it is true that Sα t0+∆(v+ r) = P(x1, . . . , xt)and Sα t0+∆(v− r) = ¬P(x1, . . . , xt),(3) even if Gis integrated inside a larger graph, and its transitions are modified by influencing nodes in V+ xit i=1 ∪V− xit i=1 arbitrarily, by means of external nodes. Being able to arbitrarily add edges which influence nodes in V+ xit i=1 ∪V− xit i=1, while still satisfying (3), lets us use Theorem 3 to include graphs which calculate arbitrary propositional logic formulas inside larger graphs. This will be very useful when proving general complexity properties of opinion graphs. We use structural induction for proving opinion graphs are functionally complete. The possible base cases are the formulas ⊤,⊥and xifor any i. These base cases are easily seen to be satisfied. For ⊤, a possible Gconsists of two nodes v1=v+ rand v2=v− r and no non-reflexive edges. This graph satisfies the property of functional completeness explained above for ∆ = 0, provided that v1, v2∈Cand SC(v1)=1, SC(v2)=0. For ⊥, the same graph, output nodes and ∆ = 0 work, although the labelling SCmust then satisfy SC(v1)=0, SC(v2)=1. The third base case (P(x1, . . . , xt) = xi) can be obtained by considering the same graph, the same ∆ = 0, the same v+ r, v− rand the sets V+ xi={v1}, V − xi={v2}. In this base case, all other node sets considered in Theorem 3 (Cand all other sets V+ xj, V − xj|j∈Nt, j =i) are empty. We now discuss inductive steps. It suffices to prove that given two formulas P1and P2for which it is possible to construct opinion graphs as in Theorem 3, analogous graphs can be constructed for each of the formulae ¬P1, P1∨P2, P1∧P2, since it is well known that the set {¬,∨,∧} is functionally complete in logic. The construction for ¬Pgiven a construction for the formula Pis almost immediate. Given GP, ∆P, the sets V+,P xit i=1 ,V−,P xit i=1 , CP, the nodes v+,P r, v−,P rand SC,P , all of which satisfy the conditions in Theorem 3 for P, a construction for ¬Pis obtained by interchanging the roles of v+,P r(which becomes v−,¬P r) and v−,P r(which becomes v+,¬P r), and not altering any other element of the construction. We now give a proof for P1∨P2given constructions for P1and P2. Given both constructions, we first consider the disjoint union of both of them, which is defined as follows. Gdef = (VP1⊔VP2, EP1⊔EP2), V+ xi def =V+,P1 xi⊔V+,P2 xi, V− xi def =V−,P1 xi⊔V−,P2 xi, Cdef =CP1⊔CP2. 21 By using the symbol ⊔, we mean the disjoint union of the two sets involved; by using it here, we essentially create a graph which consists of two separate copies of the constructions for P1and P2. These two copies have no common vertices or edges, even if they have the same original definition (which might happen if P1and P2have a common subformula). SCis defined in Cand extends both SC,P1and SC,P2(it agrees with both SC,P1on CP1and SC,P2on CP2). We now describe how to complete this disjoint union in order to obtain a construction for P1∨P2. Intuitively, we need to add an OR-gate made of new nodes, whose input nodes are the original output nodes of G, which are v+,P1 r, v−,P1 r, v+,P2 r, v−,P2 r. The problem with such an approach is that we need to take time constraints into account. Let us suppose that the values of nodes in the sets V+ xit i=1 ,V− xit i=1 correspond to a certain assignment of the variables x1, . . . , xtat time t0. Then, the values of v+,P1 r and v−,P1 rencode P1(x1, . . . , xt) at time t0+ ∆P1, and those of v+,P2 rand v−,P2 rencode P2(x1, . . . , xt) at time t0+ ∆P2. Since ∆P1and ∆P2are not necessarily equal, the inputs given to the OR-gate do not necessarily enter the gate at the same time, which implies a correct result can never be guaranteed. This issue can be solved by adding chains of nodes which generate a delay in the fastest output, so both outputs arrive at the same time. If ∆P2<∆P1, we add the nodes vret+ ∆P2+1, vret+ ∆P2+2, . . . , vret+ ∆P1−1, vret+ ∆P1, vret− ∆P2+1, vret− ∆P2+2, . . . , vret− ∆P1−1, vret− ∆P1, and the following edges, whose weight is 1. (1) An edge whose source is v+,P2 rand whose destination is vret+ ∆P2+1. The presence of this edge implies the value of node vret+ ∆P2+1 at time t0+ ∆P2+ 1 is the value of node v+,P2 r at time t0+ ∆P2, which is P2(x1, . . . , xt). (2) For all i∈∆P2+ 2,∆P2+ 3,...,∆P1−1,∆P1, an edge whose source is vret+ i−1and whose destination is vret+ i. Analogously, the presence of these edges implies the value of node vret+ iat time t0+iis P2(x1, . . . , xt). (3) Analogous edges (like those in points (1) and (2)) which connect the nodes v−,P2 r→vret− ∆P2+1 →vret− ∆P2+2 → · · · → vret− ∆P1−1→vret− ∆P1. By adding these edges, the value of the node vret+ ∆P1at time t0+ ∆P1is P2(x1, . . . , xt), and that of the node vret− ∆P1at time t0+ ∆P1is ¬P2(x1, . . . , xt). These two nodes have a similar role to the original nodes v+,P2 rand v−,P2 r, but their delay is ∆P1instead of ∆P2, so they are coordinated with the nodes v+,P1 rand v−,P1 r. The new edges only influence new nodes, so all properties assumed in the induction hypotheses are preserved after modifying the graph. An analogue of this modification can be carried out if ∆P1<∆P2, so no matter how long delays are, we can always create an artificial delay in the fastest graph so all output nodes are coordinated. 22 We now describe how to add an OR-gate to the (possibly modified) disjoint union if ∆P1= ∆P2def = ∆, which we can now assume. We add four more nodes to the graph, which are v+ r, v− r, v+ OR, v− OR. The nodes v+ rand v− rare the output nodes of def =P1∨P2, which will be calculated in ∆+1 iterations. These nodes process the information provided by the output nodes of P1and P2at time t0+ ∆, so their values at time t0+ ∆ + 1 represent P1∨P2. The nodes v+ OR and v− OR are used to influence v+ rand v− rso the logical OR is calculated correctly. They need to have specific values, so we add them to Cand we extend the definition of SCby defining SC(v+ OR)=1, SC(v− OR) = 0. We add the following edges, which only affect the newly added nodes. (1) Reflexive edges whose weight is 1 for the nodes v+ OR,v− OR. (2) Three edges whose common weight is 1/3, whose common destination is v+ rand whose sources are v+ OR, v+,P1 r, v+,P2 r. It is trivial that if the constraints given by SC are satisfied, then the value of v+ rat time t+ 1 is the logical OR of the values of v+,P1 r, v+,P2 rat time t. (3) Three edges whose common weight is 1/3, whose common destination is v− rand whose sources are v− OR, v−,P1 r, v−,P2 r. Just like in point (2), it is trivial that if the constraints given by SCare satisfied, then the value of v− rat time t+1 is the logical AND8of the values of v−,P1 r, v−,P2 rat time t. After modifying the disjoint union by following the steps described above, we are left with a construction for P1∨P2which satisfies the properties of Theorem 3. Figure 7 represents the construction graphically. A construction for P1∧P2can be obtained similarly by defining SC(v+ AND) = 0, SC(v− AND)=1, and using them instead of v+ OR and v− OR, or by using De Morgan’s laws. The proof for functional completeness of opinion graphs is thus complete. 3.2 Building a Turing machine with opinion graphs Functional completeness of opinion graphs and the concept of L-shaped graphs let us define an N-shaped graph which can simulate a semi-infinite tape Turing machine. This construction will be extremely useful to prove many complexity properties of the problem we are considering. We basically use each block of the N-shaped graph to encode a cell of the Turing machine we are considering, and construct the graph such that simulating its evolution is equivalent to simulating the evolution of the Turing machine. Before we begin to discuss the central topic of this section, we make an important remark related to terminology. The word state in the context of Turing machines can be ambiguous if not used properly, since it can have two different meanings. On the one hand, the 8This makes sense for the role of v− r, since De Morgan’s laws state that, in particular, ¬P1∧ ¬P2= ¬(P1∨P2). 23 Figure 7: Graphical representation of the inductive step carried out when adding an ORgate. The direction and weight of newly added edges are not shown. Pairs of nodes with opposite values are shown as two semicircles. Input nodes and nodes in C(bottom of the triangles) generate intermediate outputs (top of the triangles), whose OR-value (node above) is computed by means of two nodes (one circle), whose values always equal 1 and 0, and the six edges mentioned in the text. machine’s state can refer to the content of the state register, which always is one of the finitely many possible states. On the other hand, the machine’s state can mean the global state, which consists of the m-configuration, the position of the head and the contents of the tape. During the rest of this work, we use the terms m-configuration, internal state and state for the former concept, and we use the terms global state, state of progress and state of the system for the latter. Given a semi-infinite tape Turing machine whose alphabet is Γ, whose set of states is Q and whose transition function is δ:Q×Γ→Q×Γ× {L,S,R}(if the machine is in state q,σis read and δ(q, σ)=(q′, σ′, D), then the machine will replace σby σ′on the tape, change its internal state to q′and move left, stay or move right, if Dequals L,Sor R respectively, except for the first cell, for which the effect of Lis staying in the same cell), we assume without loss of generality that the values of the sets Γ and Qcan be encoded by using a finite number of binary variables. In general, we use the notation s1, s2, . . . , sµ for binary variables which encode the states, and a1, a2, . . . , aνfor binary variables which encode the alphabet. The two encodings need not be related to each other. The definition of a semi-infinite tape Turing machine implies that for every cell eof the machine, given the following information, •the definition of the Turing machine, •whether or not the head is currently pointing at eor a cell next to it, and if it is the case, the current m-configuration, •the symbols written on cell eand the cell(s) next to it, it is possible to calculate the following information (which can be calculated by a Boolean circuit if the states and the alphabet have been encoded by means of binary variables), 24 Let us define some notation first in order to describe these edges. Every graph G ∈ Gis constructed from Theorem 3, so there exist output nodes (v+ r, v− r) which store the value of a certain variable calculated by Gafter ∆ simulation steps. Inside the block Gewhose relative position is R∈ {Fst,Mid}, we define Sp,+and Sp,−to be the output nodes v+ r and v− r, respectively, of the copy of Gp Rin Ge. We use similar notation for the rest of the graphs: Sa,+ iand Sa,− iare the output nodes of the copy of Ga R,i inside Ge, and Ss,+ jand Ss,− jare the output nodes of the copy of Gs R,j. Inside Ge, we connect output nodes to v-nodes by using edges whose weight is 1 (so information in output nodes is fully transmitted to v-nodes). These connections are made naturally, by connecting the output nodes of every variable to the v-nodes of the same variable, as follows. Sp,∗→vp,∗ e,Ss,∗ j→vs,∗ e,j ,Sa,∗ i→va,∗ e,i .(19) We have now completely described Gand all the edges which connect v-nodes, w-nodes and copies of GRto each other. We have already discussed why Gsatisfies the conditions of Theorem 4 informally. After describing Gformally, we now explain why Gsimulates an arbitrary semi-infinite tape Turing Machine M. Taking ∆M= ∆+3 in Theorem 4, where ∆ is the propagation time of all graphs in G, and given an initial state S0which represents a certain state of progress α=q0,{dn}n∈N, x0, we know that the v-nodes represent α, just like in the first three conditions of Definition 8. Also, the labels of all vertices v∈Care the labels assigned by SC. Due to how we have defined Cand SCabove in G, this basically means the constraints of all graphs in Gare satisfied. Therefore, these graphs compute propositional logic formulas whose variables are read from input nodes and whose result is produced in output nodes after ∆ steps. Inside each copy of a graph from G, we have only changed the way input nodes are influenced when defining G. This means all constraints of all graphs will always be satisfied for all successive states of S0, so the values of all propositional logic formulas F ∈ Fwill be computed every simulation step, with a delay of ∆ steps. Since v-nodes are connected to w-nodes as we described in (15), w-nodes have the value their corresponding v-node had in the previous simulation step of G. Therefore, after one simulation step S0→S1,w-nodes encode the state α. Also, since w-nodes are connected to the corresponding input nodes of all graphs, like we described in (16), (17) and (18), all input nodes of all graphs in Ghave the values of all variables which encode αafter two simulation steps (S2). As we have explained before, the way we have defined Fand G, the construction of Gand the assumptions about S0imply that, after ∆ simulation steps (S2→S∆+2), all information about the next state of progress of Mhas been computed and is stored in the output nodes of the graphs of G. Finally, since we have connected these output nodes to v-nodes as in (19), that is, by connecting nodes which are related to the same variable of the next state of progress of M, this information is transferred back to v-nodes after one simulation step (S∆+2 →S∆+3). Let us summarise: after ∆ + 3 = ∆Msimulation steps, Definition 8 is satisfied, but instead of representing the global state α,S∆+3 represents the next global state. By using induction, we conclude that after simulating the evolution of Gfor ∆M·tsteps starting from the labelling S0, the information in v-nodes encodes the global state of Mobtained after titerations of the machine, if the initial global state was α. We end this section with some remarks which we are not going to discuss and prove in 31 detail. First and foremost, it is important to note that the construction of Gexplained above can be modified in order to simulate an infinite tape in both directions. This is done by using a Z-shaped graph in which only a general block exists (GMid). It can also be made finite, by generating a finite number of blocks whose relative position is Mid and adding a block at the end, Gr+1, whose outgoing interfaces are always sending the information pr+1 t=⊥back to Gr. This graph simulates a Turing machine which can only use a finite amount of space, and whose head disappears if it tries to move beyond the r-th cell. If we consider the last two blocks as one single block whose relative position is Lst, we can simulate an instance of Mwhich uses no more than rcells by using an Nr-shaped graph. This fact is quite important, so we state it here as a theorem we will refer to later. Theorem 5 (Semi-infinite tape Turing machines which use rcells can be simulated by Nr-shaped opinion graphs).Given a semi-infinite tape Turing machine Mand r∈N, there exist a ∆M∈Nand an Nr-shaped opinion graph Gwith disjoint subsets of nodes of Gc Bvp,+ Fst , vp,− Fst ,vs,+ Fst,iµ i=1 ,vs,− Fst,iµ i=1 ,va,+ Fst,iν i=1 ,va,− Fst,iν i=1 , CFst,(20) and labellings SC Bof CBfor B∈ {Fst,Mid,Lst}, such that given an initial state of progress α=q0,{dn}n∈N, x0, starting from which the head of Mnever moves beyond the r-th cell, and a labelling S0of G, if S0represents α, then S∆M·trepresents the state of progress obtained starting from αafter simulating Mfor tsteps. Definition 8 only applies to N-shaped opinion graphs. However, it can be restricted for Nr-shaped graphs, so the notion of representing a global state is well defined in Theorem 5. The second remark related to Theorem 4 is the fact that the construction of Gcan be modified so we only need basic local initial conditions; a reset signal could be sent from left to right by using appropriate additional nodes, which would initialise the contents of the tape and set pe t=⊥for blocks to which the reset signal arrives. This signal or a finite number of different signals could be used to initialise nodes in C, to make sure logic gates work as intended after receiving the reset signal. Furthermore, simulating Gusing limited resources every step can be done by assuming all nodes have constant values which are the same across different blocks and never change beyond the rightmost block which has ever been visited by the head. These labels should be chosen to represent the head not being present and a blank symbol on the tape. Last but not least, there is an important remark which is indispensable for the proofs of some results we state and prove below. These proofs rely on the construction we explain for proving Theorem 4. In this construction, v-nodes, which display the state of progress of Mevery ∆Msimulation steps, transmit all their information to w-nodes every simulation step, and this transmission of information is unconditional and only depends on the values of v-nodes. In the next simulation step, information is transmitted from w-nodes to input nodes of elements of G. This transmission of information is unconditional as well, and is not corrupted if the values of v-nodes are manually modified after the first simulation step, since all information has already been transmitted to w-nodes. Theorem 3 implies information about the next global state of Mwill be transmitted to the output nodes of elements of Gduring the next ∆ = ∆M−3 simulation steps, even if the values of v-nodes are manually modified during these ∆ cycles; Theorem 3 guarantees 32 the values of variables which have already reached input nodes will not be altered, since v-nodes do not belong to any element of G. This independence makes it possible to simulate ∆Mdifferent instances of Mby using a single simulation of G, as follows: in order to initialise Gwith the states of progress {α1, α2, . . . , α∆M}, we start from a labelling Sfor which ∀v∈Ce,S(v) = SC(v) (so logic gates function properly) and apply the following algorithm to G. Algorithm 1 Initialising Gto simulate ∆Minstances simultaneously starting from the states of progress {α1, α2, . . . , α∆M} 1: for i= 1,2,...,∆Mdo 2: Replace the labels of v-nodes so the labelling of Gnow represents αi 3: Advance the simulation of Gone step 4: end for Theorem 4 and the independence properties we have just discussed imply all instances are simulated at the same time and are represented in v-nodes cyclically. When replacing the labels of v-nodes in Algorithm 1, instances which have already been inserted are not corrupted, since the simulation has advanced, but not more than ∆M−1 steps. At the end of Algorithm 1, ∆Msimulation steps have passed since α1was introduced in G, so the next state of progress is represented in v-nodes. During the next iteration consisting of ∆Msimulation steps, the next states of progress corresponding to all initial global states {α1, α2, . . . , α∆M}are represented in Gin order of insertion. This process repeats every ∆Msimulation steps and simulates every instance one step further. In order to use this parallel simulation and conceptually describe which instances we intend to simulate in specific cases, we use the term level of information when referring to one of the ∆Mavailable slots there are for running an instance of ∆M. The first one consists of information stored in v-nodes, the second one consists of information stored in w-nodes, and so on. Conceptually, information moves to the next level every simulation step, and transforms to represent the next state of progress when moving from the last level to the first one. Of course, it can be decided to simulate a single instance by initialising v-nodes correctly in S0and initialising all other nodes which are not in Cto random values. 3.3 Decidability and complexity properties of opinion graphs The results we have obtained in previous sections are very useful for analysing the complexity properties of opinion graphs in general, and those of L-shaped graphs in particular. The two key results we have obtained so far are Theorem 4 and Theorem 5, from which all relevant complexity results about opinion graphs can be deduced. We begin this subsection by discussing general properties infinite opinion graphs have, and end it determining the complexity of simulating finite L-shaped opinion graphs. Theorem 4 implies L-shaped opinion graphs can be as expressive as Turing machines. We have also mentioned it is not necessary to initialise an infinite number of nodes in order to obtain this expressiveness; initialising a finite number of nodes at the leftmost block of an N-shaped graph suffices. This leads us to the following theorem. 33 Theorem 6 (Limit properties in L-shaped graphs are undecidable).Given an L-shaped graph Gand a finite or infinite initialisation condition17 for G, the following problems are undecidable in general. (a) Given a node vof G, does there exist a certain labelling S0of G, which respects the initialisation condition, and a certain t∈N, for which St(v) = 1? (b) Does there exist a certain labelling S0of G, which respects the initialisation condition and eventually stabilises (∃t∈N|St+1 =St)? (c) Given a finite set Zof nodes of G, does there exist a certain labelling S0of G, which respects the initialisation condition and for which it is possible to estimate the asymptotic proportion of nodes which agree (or disagree) in Z? Proof. (a) Consider the universal semi-infinite tape Turing machine Udefined in [4]. This machine accepts the input ⟨x, α⟩if the machine which is represented by α accepts x. We define a Turing machine Uawhose behaviour is slightly different from that of U. For our purpose, the input of Uaalways begins with the special tape symbol σ⊥(which is not used elsewhere), and is then followed by ⟨x, α⟩.Ua simulates the instance ⟨x, α⟩, just like U, but without modifying the first cell of the machine. If Uaccepts ⟨x, α⟩, then Uaalso does, but moves its head to the first cell and overwrites it with the symbol σ⊤(also never used elsewhere) before stopping completely. For problem (a), we define Gto be the graph which is constructed using the proof of Theorem 4 with M=Ua. We assume without loss of generality that the following two properties are true. •If σx t=σ⊤, then ax 1,t = 1, and if σx t=σ⊤, then ax 1,t = 0. In other words, the first bit used to encode σ⊤is 1, while it is 0 for all other alphabet elements. •Gcan be initialised locally by appropriately setting the values of the nodes in the first mcells, and it will simulate Uacorrectly, since it can correctly interpret areset signal sent from Gm+1. Given a general input ⟨x, α⟩, Theorem 4 and related results provide a finite18 or infinite19 initialisation condition of Gwhich makes it possible to simulate how Ua processes ⟨x, α⟩. The initialisation condition makes sure logic gates work as expected, and saves the initial state, place of the head and contents of the tape in all levels of information of G, or in the one which corresponds to v-nodes. Note that due to the encoding of tape symbols we have assumed (first assumed property) and how Uaworks, ⟨x, α⟩being accepted by Uis equivalent to the first 17This means the initial labelling of the L-shaped graph is a certain S0, and a possibly infinite list of conditions of the form S0(vi) = li,S0(vi) = S0(vj) or S0(vi) = ¬S0(vj) is given. We formulate this theorem in a very general way, allowing incomplete descriptions of S0, in order to emphasise that the undecidability of the problems we consider is not related to infinite initialisation conditions which cannot be fully processed in a finite amount of time. 18This initialisation can be specified by using a finite initialisation condition, due to the second assumed property. 19The infinite case is also included here, since arbitrarily defining more nodes starting from a finite initialisation condition merely gives more details about the initial state of progress of M, without changing the answer to the problem. 34 symbol of the tape of Uaeventually becoming σ⊤, which is in turn equivalent to the label of va,+ 1,1(the v-node which codifies the first bit of the symbol on the first cell) eventually taking the value 1 forever during the simulation steps in which v-nodes represent the global state of Ua. Therefore, the behaviour of Uon any input of the form ⟨x, α⟩can be reduced to problem (a) for a certain subset of simulation steps, making it undecidable as well. We are not done with the proof of (a) yet, as we know that va,+ 1,1only represents one of the variables of the state of the system every ∆Uasteps, so it might be possible to prove the label of va,+ 1,1equals 1 in a simulation state in which v-nodes do not represent the state of progress of Ua. However, as we discussed before, the way we have constructed Uain Theorem 4 makes it possible to simulate ∆Uainstances simultaneously, and exactly one of them is represented in v-nodes every cycle. If ∆Uacopies of the same instance are simulated in all ∆Ualevels of information, the label of va,+ 1,1becomes 1 if and only if σ⊥is replaced by σ⊤on the first cell of Ua. This makes it possible to guarantee that the initial condition of Gchosen for ⟨x, α⟩ extends the equivalence discussed before to all simulation cycles of G. That implies the behaviour of Uon arbitrary inputs can be reduced to problem (a) the usual way, so problem (a) is undecidable. (b) For proving (b), we use some ideas from (a), but change the construction of the semiinfinite tape Turing machine. In this case, we choose Ubto be a Turing machine whose global state stabilises20 when its input is ⟨x, α⟩if and only if Uaccepts ⟨x, α⟩. Constructing Ubcan be done in many different ways; inserting cyclic loops in the transition function for stationary global states in which ⟨x, α⟩is not accepted, is one possible approach. We now define Gto be the graph which is constructed taking Ub, not Ua. Using the same argument as in (a), it is possible to simulate ∆Ubequal instances of Ubin G. If all simulated instances are equal, Geventually stabilises if and only if the state of progress of Ubstabilises; it is obvious that Gdoes not stabilise if one of the instances does not stabilise, and if they are all equal and eventually stabilise, Gstabilises, since each level of information of Geventually contains the information related to the stable state of progress, which does not change when instances flow through the levels of information of G, as all instances attain the stable state of progress. This leads us to a reduction which maps the behaviour of Ufor an arbitrary given input ⟨x, α⟩to problem (b). Therefore, (b) is undecidable. (c) In general, this problem is undecidable, even if Zis arbitrarily large. We choose Ucsuch that, given input ⟨x, α⟩, the machine eventually writes the symbol σ⊥on all cells from left to right if Udoes not accept ⟨x, α⟩, while σ⊤is written if Udoes accept. In order to implement this, the symbol σ⊥can be written progressively from left to right while Uis simulated on the right, and if it is seen that Uaccepts the given input, then the head goes to the beginning of the tape and overwrites everything using σ⊤. Analogously, we now use Gto denote the graph constructed using Uc. If, as in the previous problems, we assume the same input is provided in 20By definition, Mstabilises if and only if the state of progress of Mstops changing, i.e. the head of Mstays in the same place, the m-configuration does not change and the symbol on the tape is not modified. 35 all levels of information of Gand choose Zk=va,+ e,1k e=1 21, then the values of all nodes of Zkwill eventually be 1 if ⟨x, α⟩is accepted by U, since all tape symbols will eventually become σ⊤, or 0 if ⟨x, α⟩is not accepted. This construction reduces the same undecidable problem considered in (a) and (b) to problem (c), which is thus undecidable. Even though Theorem 6 might seem natural given the results we obtained in Section 3.2, it is not a direct consequence of any previously proved theorem, and looks very discouraging at first glance: it implies the problem of simulating opinion graphs and deducing their behaviour, which can be directly applied to model opinion dynamics in modern societies, is undecidable, and we are not even able to give global quantitative estimations of the graph’s evolution for arbitrarily large amounts of time. We now state and prove the finite version of this result. Just like Theorem 4 was used for proving Theorem 6, the proof of the following theorem heavily relies on the corresponding finite version of Theorem 4, which is Theorem 5. We first give a definition which provides a way to generate L-shaped graphs with the same invariant local structure. This definition is closely related to Definition 5, and is very relevant for a special case of the theorem we discuss below. Definition 9 (L-shaped graphs of variable size).Given d∈N, interfaces {Ij}j∈Ndand finite opinion graphs GRfor every R∈ {Fst,Mid,Lst}dwhich are multiply connected to the following interfaces, (a) If the j-th element of Ris not Lst, then GRmust be connected to Ijas a predecessor. (b) If the j-th element of Ris not Fst, then GRmust be connected to Ijas a successor. we define, for each L=E1×E2× · · · × Ed(where each Eiequals Nsifor certain si≥ 3), the graph G(L)as the finite L-shaped graph obtained by using the construction from Definition 5. We define |L|, the block cardinality of G(L), to be the cardinality of L=Qd i=1 Ei= Qd i=1 Nsi, which equals Qd i=1 si. We state almost all of the properties related to finite graphs in one single theorem, since they are closely related to each other and we obtain the same complexity class. We remind the reader some assumptions we make. These assumptions are natural and used in [4]. (1) The way Turing machines are encoded guarantees that given a machine’s description by listing the tables of the transition functions, there exists a polynomial-time algorithm which encodes it. Similarly, the algorithm for decoding is also polynomial (the number of alphabet symbols and states is bounded by a polynomial function of the length of the string which represents the semi-infinite tape Turing machine). 21Zkis the set of v-nodes which encode the first bit of the symbol written on the tape, for the first k cells. Its cardinality is k. 36 (2) When encoding opinion graphs in a language, we list the nodes and edges of the graph, so this representation is a polynomial function of the number of nodes. We also list all the rational weights of all edges. The representation used for rational numbers guarantees that operating with them is possible by using polynomial-time algorithms. Problems (c) and (d) of Theorem 7 are not decision problems. However, they can trivially be transformed to a number of decision problems which is linear in the input of problems (c) and (d). Besides, problems (c) and (d) are very practical and have many applications. Therefore, we state them as optimisation problems. What we prove is that obtaining all bits of their solutions can be done using a polynomial amount of space, and they are also PSPACE-hard. This approach is equivalent to decision problems, as defined in [4]. Theorem 7 (PSPACE-completeness of global properties of L-shaped graphs).The following problems, whose inputs are a finite L-shaped graph Gand an initialisation condition for G, are PSPACE-complete. (a) Given a node v∈G, does there exist a labelling S0of G, which satisfies the initialisation condition, and a t∈N, for which St(v)=1? (b) Does there exist a labelling S0of Gwhich satisfies the initialisation condition and eventually stabilises? (c) Of all possible initial labellings Sα 0which satisfy the initialisation condition, which one maximises the proportion of nodes whose value is 1at time t22? Which maximum proportion and corresponding initial and final graphs are obtained? What about all possible times? (d) Suppose there exist polynomial-time functions which calculate the cost of initial labellings, and the benefit of labellings at time t. Which initial labelling, with cost not higher than cand which satisfies the initialisation condition, maximises the benefit at time t? Which maximum benefit and corresponding initial and final graphs are obtained? What about all possible times? Proof. First of all, we check all of these problems belong to PSPACE. Simulating opinion graphs for an arbitrary number of steps can be done in polynomial space, due to our assumptions. Problem (a) can be solved using polynomial space by considering all possible initial labellings one at a time and simulating all of them. Binary counters can be used to detect when to stop simulating, since the number of simulation steps eventually exceeds the number of possible steps of the graph. It is well-known and discussed in [4] that these counters use a linear amount of space. Saving the labelling S0also uses linear space. Problem (b) can be solved similarly; an initial labelling is discarded if it has not converged when the number of steps attains the number of possible labellings of G. Problem (c) is a special case of problem (d), which can be solved by considering all possible initial labellings, one at a time, simulating them if they satisfy all requirements and keeping the best initial and final labellings depending on the outcome at time t. If 22In (c) and (d) of Theorem 7, tis given as a binary number. 37 the best result is needed for all times t∈Z≥0, then the simulations can be run until the number of simulation steps exceeds the number of possible configurations of the graph. This can be done using a polynomial amount of space, as explained in [4]. We now show these problems are PSPACE-complete by showing that Laccsp ≤pLfor all of the considered Lassociated with the problems described in (a-d), where Laccsp is the language defined in Equation (1), in Part 1.1.1 of the introduction. Given an instance (M, w, 1n) of this problem, it is possible to transform it to (M′, w, 1p(n)) using a polynomial-time algorithm, so that if Maccepts win space n, then M′accepts wand the first cell, with an initial value of σ⊥, changes once to σ⊤, and the global state of M′stabilises, while M′does not accept, the first cell keeps its initial value of σ⊥and the global state does not stabilise if not. We know by Theorem 5 that this problem can be transformed to an opinion graph Gwhich simulates M′, and due to the first transformation from Mto M′, the simulation of Gleads to the answer to the problem Laccsp for (M, w, 1n). After the transformation from (M, w, 1n) to G, all problems (a-d) can be used to determine if (M, w, 1n)∈Laccsp; the problem described in (a) can be used by taking v=va,+ 1,1and using the same construction as in Theorem 6. The problem described in (b) can also be used, since Gconverges if and only if the global state of M′converges23. Problems (c) and (d) can be used to analyse Gby looking at the final opinion graph after simulating, which these problems obtain. For all problems (a-d), the initialisation condition we use consists of the initial assignments when constructing G using Theorem 5 to make sure logic gates work, as well as the construction from the proof of Theorem 6, which assigns fixed values to all levels of information. This initialisation condition assigns a value to each node, which implies no freedom to modify the nodes’ labels is given. For problems (c) and (d), this means a completely determined graph is simulated, and whether or not M′accepts is deduced by looking at the final label of va,+ 1,1, which is calculated by problems (c) and (d) as part of the final graph. Regarding problems (a) and (b), the completely determined graph is simulated as well and the definition of M′given input (M, w, 1n) implies that M′accepts if and only if problems (a) and (b) are true. All we need to show in order to finish this proof is that transforming an instance (M, w, 1n) to its corresponding Gcan be done in polynomial time. This follows from previous theorems we have already discussed. First of all, the construction used in Theorem 3 transforms propositional logic formulas to opinion graphs in polynomial time, since in most of the construction a constant number of nodes and edges is added for each symbol in a formula. There is an exception, which is when chains of nodes are added to achieve equal delays for different opinion graphs. However, the length of these chains is a linear function of the delay of an already constructed graph. This makes the construction quadratic in the length of the formulas. Also, it is shown in [4] that there exist polynomial-time algorithms to transform a semi-infinite tape Turing machine Mto the set of logic formulas FMwhich determine its transition functions. All these formulas are then transformed to the corresponding set of graphs GMfrom Theorems 4 and 5 using the polynomialtime algorithm discussed in 3. These graphs are then copied not more than ntimes to construct G, so the time complexity remains bounded by a polynomial. Initialising 23Of course, in order to make sure Gconverges if and only if the global state of M′converges, it is necessary to use the same type of initialisation as in Theorem 6; all levels of information have to simulate the same instance. 38 nodes as described in the proofs of Theorems 4 and 6 by using Algorithm 1 can also be done in polynomial time. Therefore, transforming (M, w, 1n) to Gis possible using a polynomial-time algorithm, which implies all problems discussed in this theorem are PSPACE-complete. This theorem is very discouraging as well; important questions about arbitrary graphs cannot be easily answered. This might make it extremely difficult to understand opinion dynamics in real life. Nevertheless, this task might turn out to be much easier in real-life conditions. After all, the graphs we are considering in the proof of Theorem 7, which are first defined in the proof of Theorem 3, are clearly very different from real-life social graphs; all nodes influence exactly one node, apart from themselves, and many of them just receive an opinion from one node during a cycle and pass it on to another node. It is important to note that the proof given above can be applied to finite opinion graphs in general; although the arguments used to prove polynomial reduction from Laccsp to the problems described in Theorem 7 rely heavily on repetitive patterns in N-shaped graphs and the constructions discussed in previous sections, proving that all problems from Theorem 7 belong to PSPACE can be done without assuming that Gis an Lshaped graph. Therefore, the space which is needed to simulate an arbitrary opinion graph to obtain conclusions about its behaviour is a polynomial function of its number of vertices, and nothing can be said about the time complexity, apart from what is implied by Theorem 1, since we now know the general problem is PSPACE-complete. Of course, there are several special cases for which the complexity can be determined; one of them is Corollary 2. If the initial condition of Gcompletely determines the value of all nodes and satisfies Corollary 2, then it is possible to simulate the evolution of Gin polynomial time, since the number of simulation steps before the labels of nodes in Gconverge does not exceed the number of vertices24. We now state and prove a specific case of Theorem 7 which can be used when the structure of the L-shaped graph is fixed. Although this Corollary is predictable, it provides more precise space bounds for the fixed structure case, so we state it for completeness. Corollary 3 (Space bounds for L-shaped graphs of variable size).Given d∈N, interfaces {Ij}j∈Ndand finite opinion graphs GRfor every R∈ {Fst,Mid,Lst}das in Definition 9, there exist Turing machines Ma, Mb, Mcand a constant Ksuch that problems (a), (b) and (c) from Theorem 7 can be solved by Ma, Mb, Mcrespectively, using no more than K· |L| cells if the input graph of the problem is G(L), for all L=E1×E2× · · · × Ed. Proof. Iterating through all states, saving states, counting the number of nodes which agree for a certain state and counting the number of simulation steps can all be done in linear space. All we need to prove is that the graph can be saved in linear space and be simulated in linear space, as a function of |L|. Since the local structure of the graph is fixed, it is possible to make the alphabet of the Turing machines rich enough to save two copies of the following information as a tape symbol. 24Suppose Ghas nVnodes, and it takes nC> nVsimulation steps for their labels to converge. Then, since every node v∈Gflips its opinion at most once due to Corollary 2, not more than nVopinion changes take place in strictly more than nVsimulation steps, during which the graph has not stabilised yet. That is a contradiction, since the pigeonhole principle implies there have been no opinion changes during a certain cycle, which is impossible, since that implies Ghas actually converged before nCsteps. 39 (a) The state of the nodes belonging to a block Ge. (b) Information about the relative position of Ge, which is given by an element of {Fst,Mid,Lst}d. (c) A Boolean it(Ge), which is usually ⊥. Blocks of the graph can be encoded using linear space by using this method and saving them in lexicographical order. In order to simulate the graph, the machine can iterate through all blocks of the graph and compute their next state, saving a copy of it in each block without destroying the copy of the current state, which needs to be saved to compute the next state of other blocks. In order to calculate the next state of a block Ge, information about nodes which are connected to incoming interfaces of Geis needed. If this information is obtained, the transition functions of the nodes of Gecan be encoded in Ma, Mb, Mc, since the structure of the blocks is fixed. In order to obtain this information for a certain dimension d, the Turing machines can set it(Ge) = ⊤to remember its position and move their heads to the left and to the right in order to find the positions at which the position of the block in dimension dchanges (this can be done by looking for blocks whose relative positions are all Fst for dimensions which have a lower priority than din the lexicographic order), and set their it Boolean to ⊤as well. In order to find the blocks which are above and below Gein dimension d, the Turing machines need to find the blocks which are at the same distance of the following increase (or decrease) in the value of dimension das Ge. This calculation can be done without using counters, by marking blocks (modifying their it value, or even using a constant number of additional Boolean variables inside every block). This makes it possible to find all the needed information to compute the next state of every block without using more than |L|cells, so simulating the graph, and thus problems (a), (b) and (c) from Theorem 7 can be solved using a linear amount of space. Of course, similar space bounds for problem (d) from Theorem 7 can be calculated, as long as bounds are given for the space used by the cost and benefit functions. The last theorem of this part of the work provides the complexity class of simpler versions of the problems discussed above. We remind the reader that the language Ltmsat def =⟨α, x, 1n,1t⟩ | ∃u∈ {0,1}ns. t. Mαaccepts 1 on input ⟨x, u⟩within tsteps is NP-complete. For a proof of this fact, see [4]. We also remind the reader that we assume certain standard properties of the representation of opinion graphs and Turing machines, just like we explained before Theorem 7. Theorem 8 (NP-completeness of local properties of L-shaped graphs).The following problems, whose inputs are a finite L-shaped graph G, an initialisation condition for G and a positive integer t∈Nwhich is given in unary25, are NP-complete. (a) Given a node v∈G, does there exist a certain labelling S0of Gwhich satisfies the initialisation condition and for which St(v) = 1? 25In the input, tis given as 1t. This fact is extremely important, since the problems are not NPcomplete if tis given in binary. 40 Modification Alg0 Alg1 Alg2 Alg3 Alg4 Standard 0.7480152 0.7828424 0.7940712 0.7780384 0.7901952 NonReGE 0.7522288 0.7767368 0.7881176 0.7721000 0.7855128 Stretched 0.7042544 0.7374504 0.7479160 0.7356360 0.7447552 Both 0.7032392 0.7233448 0.7352504 0.7184056 0.7308472 Modification Alg5 Alg6 Alg7 Alg8 Alg9 Standard 0.8768376 0.8994000 0.9118392 0.8956056 0.9078544 NonReGE 0.8793336 0.8964144 0.9079536 0.8923088 0.9042080 Stretched 0.8235320 0.8445024 0.8573536 0.8411672 0.8538840 Both 0.8225656 0.8327856 0.8479816 0.8266624 0.8420864 Table 1: Average proportion of favourable nodes obtained when applying all basic algorithms to different modifications of the standard problem. 50 different instances for each cell were used. By remembering what each algorithm is based on, we conclude that first influence is a better criterion than second influence, although it intuitively seems better to use second influence, since it considers more information. It can also be seen that considering the cost per unit of influence is a better approach than considering the number of units of influence of a node. Only considering the weight of nodes when selecting them is the worst possible strategy. However, what affects results the most is dividing heuristics in five steps and temporarily locking nodes (Alg5-Alg9) or not (Alg0-Alg4). When the graph is stretched or global nodes are not realistic, the graph is less compact, so obtaining a good solution becomes more difficult, and the attained proportions of favourable nodes in Table 1 are lower. There are two exceptions, which are Alg0 and Alg5. These two algorithms only consider cost when choosing nodes, and their success rate increases when transitioning from standard graphs to NonReGE-graphs. This is because all other algorithms always select all or almost all of the nodes whose first influence is very high, while Alg0 and Alg5 do not. When global edges are distributed randomly, the number of highly influential nodes decreases significantly, making it less problematic when a certain heuristic does not take influence into account. 4.2.2 Benchmarks of the best basic strategy In order to better understand how changing parameters affects the problem we are trying to solve, we analyse how the best basic strategy (Alg7) behaves when certain generation parameters of the opinion graphs change. All obtained results have been tested by using at least 50 different instances, and hypothesis testing methods from [10] (implemented in [2]) have been used to verify all statistically significant claims we make. Changing the maximum weight of reflexive edges When we defined the standard model we use for constructing graphs, we specified that the weights of global edges are taken randomly and uniformly from N25. More generally, they could be taken from Nx, and this choice greatly affects the average stubbornness of nodes, making it much more difficult to change the value of other nodes by influencing 47 them from outside when xis large. Figure 8: Changing the maximum possible weight of reflexive nodes affects the results obtained by the best basic strategy. 50 different graphs were generated and solved for each data point in order to obtain average results. Apart from the change in the reflexive nodes’ maximum weight, no parameters are different from the standard ones. 21 different values ({0,5,10,...,100}) have been considered. Figure 8 shows what the consequences of changing this parameter are; our intuition is confirmed. Although the general trend is clear, it can also be seen that changing this parameter affects the average favourable proportion of nodes more when it becomes large, while the effects are less noticeable when x≤40. Changing the number of global edges We can also modify the standard model by modifying the number of global edges without altering any of the other parameters. This should theoretically make the graph more compact and interconnected, reducing the average shortest path length and making it easier to spread opinion trends. Figure 9: Changing the number of global edges affects Alg7’s performance. 50 different graphs were generated and solved for each data point in order to obtain average results. It can be seen that the trend is almost linear. The correlation between both variables equals 0.996. Nevertheless, this trend is not global, since the maximum attainable value in the y-axis is 1. Only the number of global edges is changed, all other parameters are the standard ones. 26 different numbers of global edges ({0,4000,8000,...,100000}) have been considered. 48 The trend in Figure 9 is confirmed and is essentially linear, but simulations beyond 100000 global edges show that it is not (the slope decreases beyond 100000 global edges), and the proportion of favourable nodes stabilises at around 0.996 when the number of global edges is greater than 140000. Changing the available cost The last parameter we have studied in order to understand how problem conditions alter results is the available budget. It is obvious that increasing the available budget necessarily increases the average proportion of favourable nodes, since previous assignments of labels can be reused and completed to solve graphs which have the same structure. However, nothing can be said about the trend type before simulating instances and obtaining conclusions. Figure 10: Proportion of favourable nodes compared to total available cost. 50 different graphs were generated and solved for each data point, and were not reused for other data points, in order to obtain average results. The trend seems to be exponential if the proportion of opposing nodes is considered instead (the coefficient of determination, R2, equals 0.943). All used instances of graphs are generated using the standard methods described in 4.1. 26 different available budgets ({0,4000,8000,...,100000}) have been considered. Even though there seems to be an exponential trend, it might not be a correct assumption. It is interesting to see that the success rate stabilises at a total available cost of around 70000. It seems that nothing else can be done beyond that point to convince more nodes, since the remaining nodes which disagree are almost always locked and are influenced by other nodes which disagree and are locked as well. 4.3 Using a genetic algorithm A genetic algorithm has been designed and used to improve the results of Alg7. This algorithm is initialised by using the results from Algorithms Alg5 to Alg9. Crossover and mutation are defined as follows. For crossover, each sample is randomly ranked before crossover takes place; nodes which appear before in the sample after ranking are more important than nodes which appear at the end. Crossover consists of selecting the most important nodes from each sample (iteratively selecting the most important node left for both samples at the same time, and 49 of course not selecting a node again if there are repetitions), and stop selecting when it is no longer possible because no more budget is available. For mutation, the graph is simulated for 20 cycles and a bribed node is unmarked if it is detected that the sum of the weights of incoming edges (from nodes whose label value is 1) is high (>0.6), since it is assumed that the label of that node would become 1 anyway, due to influence from neighbours. Then, new nodes are added randomly by using the weight which has been given back by unmarked nodes. No more than 10 nodes are unmarked per iteration in order not to substantially alter a solution when mutating. Every iteration starts by considering five instances. Crossovers for each possible combination are done, and each instance is also randomly mutated six times. The best five instances of all of these modifications, including the initial ones, are used in the next iteration. In order to test this genetic algorithm, we have chosen the available budgets c1= 20000 and c2= 40000, and run this genetic algorithm using 50 graphs for each of these budgets. The obtained proportions of favourable nodes can be found in Table 2. Cost used Alg7 10 iterations 20 iterations 30 iterations 40 iterations c10.7045312 0.7063823 0.7138368 0.7194051 0.7231830 c20.8592466 0.8647835 0.8674822 0.8714732 0.8751670 Table 2: Average proportion of favourable nodes obtained when applying the genetic algorithm described in this section to the standard problem, which has been modified by changing the available cost to c1and c2. 50 different instances for each cell were used. Although there seems to be some improvement and it has been checked using [2] that the improvement is statistically significant, this algorithm takes a very long time to run, and the improvement is not very significant. It might be possible to obtain similar or better results by considering additional heuristics or a more efficient genetic algorithm. However, it is true that the genetic algorithm we have considered seems to be better than the best basic strategy (Alg7), and it might also be the case that the improvement is not very significant because the proportion of favourable nodes cannot be increased much more for these instances using any method. 50 5 Conclusion This work has allowed us to obtain important complexity properties about opinion graphs; they are essentially as expressive as Turing machines. Therefore, fully solving optimisation problems in order to determine a good strategy for influencing a population’s opinion is, in most cases, not feasible. All relevant problems for carrying out this task are at least NP-hard, and the most complex ones are even PSPACE-hard. In spite of this hurdle, we have been able to propose relatively simple strategies to solve one of the NP-complete problems successfully using opinion graphs whose properties make them similar to real-world examples. As we have already mentioned, the graphs we have considered when proving complexity properties are very different from real-world examples. It appears that real-world graphs are much more regular, and very simple heuristics yield good results. Of course, the performance of greedy strategies can be improved by temporarily locking promising nodes in intermediate steps and using genetic algorithms, which improve the proportion of favourable nodes even more. Even though the results we have obtained are satisfying and provide a lot of insight, there remains much to be done. On the one hand, more types of graphs could have been analysed. Besides, the types of graphs we have considered could have been analysed in greater depth. On the other hand, not many different heuristics have been used to analyse the problem we wanted to optimise, and more complex genetic algorithms could have been used to obtain better results. The practical problem we have analysed is relatively general, but some variations of the problem could be considered in further research. For instance, the weight distribution could be modified. In the real world, people who are influential are usually more expensive to bribe than people whose influence is lower. Taking this correlation into account would make the graph even more realistic. The theoretical results we have obtained are very complete and have made us understand the type of problems which arise when studying opinion graphs. Nevertheless, there are aspects which have not been covered, some of which are average case complexity and approximability classes. More research could be done in order to provide a more accurate classification of the theoretical problems we have discussed in this work. There is one more aspect which could be studied to generalise the obtained results; the transition function used to update node labels in opinion graphs in general could be made probabilistic and possibly non-linear to compare how nodes behave depending on the considered function. A lot of recent papers have focused on non-linear voter models, and applying these models to our problem would make it possible to obtain very general conclusions which could even be applied outside the scope of this work. 51 References [1] Binary Indexed Tree : Range Update and Range Queries. https://www. geeksforgeeks.org/binary-indexed-tree-range-update-range-queries/. [Accessed 13-March-2023]. [2] Non-parametric multiple groups one vs all. https://tec.citius.usc.es/stac/ ranking.html. [Accessed 15-April-2023]. [3] R´eka Albert and Albert-L´aszl´o Barab´asi. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47–97, January 2002. [4] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. [5] Claudio Castellano, Miguel A. Mu˜noz, and Romualdo Pastor-Satorras. Nonlinear q-voter model. Physical Review E, 80(4), October 2009. [6] Raymond Chiong and Michael Kirley. Effects of iterated interactions in multiplayer spatial evolutionary games. IEEE Transactions on Evolutionary Computation, 16(4):537–555, August 2012. [7] Kari Eloranta. Voter dynamics in deterministic cellular automata, volume 8, pages 51–58. De Gruyter, 1996. [8] Juan Fern´andez-Gracia, Krzysztof Suchecki, Jos´e J. Ramasco, Maxi San Miguel, and V´ıctor M. Egu´ıluz. Is the voter model a model for voters? Physical Review Letters, 112(15), April 2014. [9] Roger Guimer`a, Leon Danon, Albert D´ıaz-Guilera, Francesc Giralt, and Alex Arenas. Self-similar community structure in a network of human interactions. Physical Review E, 68(6), December 2003. [10] Sture Holm. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6:65–70, 1979. [11] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to automata theory, languages, and computation. Pearson, Upper Saddle River, NJ, 3 edition, June 2006. [12] Hui-Jia Li, Lin Wang, Yan Zhang, and Matjaˇz Perc. Optimization of identifiability for efficient community detection. New Journal of Physics, 22(6):063035, June 2020. [13] Thomas M. Liggett. Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Springer Berlin Heidelberg, 1999. [14] Naoki Masuda, Nathanael Gibert, and Sidney Redner. Heterogeneous voter models. Physical Review E, 82(1), July 2010. [15] Matjaˇz Perc, Jes´us G´omez-Garde˜nes, Attila Szolnoki, Luis M. Flor´ıa, and Yamir Moreno. Evolutionary dynamics of group interactions on structured populations: a review. Journal of The Royal Society Interface, 10(80):20120997, March 2013. 52 [16] Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177–192, 1970. [17] Vishal Sood, Tibor Antal, and Sidney Redner. Voter models on heterogeneous networks. Physical Review E, 77(4), April 2008. [18] Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440–442, June 1998. 53 Appendix I: More information about used software In order to simulate the problem and the performance of the algorithms we have considered, as well as for writing this document, two computer programs have been developed and used. One of them generates random graphs with given parameters and simulates their performance, just like it has been described in this document. There has not been enough time to make this program user-friendly, so it has been used by designing tests as part of the program and running them separately. The other program has been designed to help the author to create the figures of this document and the final presentation. It is impossible to find any other tools which can generate figures like the ones of this document and successfully integrate them in a L A T EX document, so it seemed necessary to develop such a program. The program iteratively visits folders of the location from which it is run, and looks for TikZ code and scripts whose syntax has been created by the author. This program then transforms TikZ code as indicated by the scripts to create new TikZ code which integrates transformed copies of the original TikZ code. Using these script files might not be very intuitive, but it was found to be very practical, since one of the original TikZ files can be modified and the transformed TikZ code can be instantly regenerated. Two classes of the code which generates random opinion graphs are refactored code obtained from https://www.geeksforgeeks.org/binary-indexed-tree-range-update-range-queries/ to implement Algorithm 2 efficiently. The license of this code is CC-BY-SA, whose full text can be read at https://creativecommons.org/licenses/by-sa/2.0/. This license has been reused for that part of the code and it is indicated in code files. All of the code which has been written and used for this work has been submitted along with this document and will be made available at https://github.com/Martin-ga when possible. 54 Appendix II: Raw data examples Large samples of raw data have been submitted along with this document, and even larger samples of raw data will later be published at https://github.com/Martin-ga when deemed appropriate. Here we give a small example, which corresponds to proportions of favourable nodes obtained for generating the fifth data row of Table 1. Each entry is calculated using the proportions obtained from 50 instances. 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