Message Passing Approach to the dynamics of opinion

1 Complex Networks: an overview 2 Contents 1 Complex Networks: an overview . . . . . . . . . . . . . . . . . . 2 1.1 Erdos-Renyi graph: Denition and Characteristics . . . . . . . . 2 2 Opinion Dynamics: Voter model . . . . . . . . . . . . . . . . . . 3 2.1 Conservation laws . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Analytical solution on the 1-D regular lattice . . . . . . . . . . . 6 2.3 Analytical solution on uncorrelated networks . . . . . . . . . . . 7 3 Variational Approximations for Ising-like models . . . . . . . . . 10 3.1 Variational Approximations denition . . . . . . . . . . . . . . . 10 3.2 Star Approximation Method . . . . . . . . . . . . . . . . . . . . . 11 3.3 Diamond Approximation method . . . . . . . . . . . . . . . . . . 12 4 Results and discussions . . . . . . . . . . . . . . . . . . . . . . . 13 4.1 Voter Model on One-dimensional lattices . . . . . . . . . . . . . . 13 4.2 Voter Model on Erdos-Renyi graph . . . . . . . . . . . . . . . . . 13 4.3 q-Potts Voter Model . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.4 Parallel and asynchronous update comparison . . . . . . . . . . . 17 4.5 Towards multiopinion dynamics . . . . . . . . . . . . . . . . . . . 20 5 Conclusions and future prospects . . . . . . . . . . . . . . . . . . 23 1 Complex Networks: an overview Graph theory was born in the XVIIIth century with the work of Leonhard Euler who studied small graphs with high degree of regularity. Until the second half of the XXth century, this mathematical eld did not evolve very quickly. The real fundamental study was done around the 0 60 by Paul Erdos and Alfred Renyi who studied the properties of random graphs [1]. Thanks to the rst study of Erdos and Renyi, today it is possible to understand some basic and fundamental characteristics of networks with apparently unknown organizing principles. Erdos and Renyi, in fact for the rst time, gave a probabilistic interpretation to some general features regarding complex networks. 1.1 Erdos-Renyi graph: Denition and Characteristics Building an ER Graph: In mathematical terms a network is represented by a graph. A graph is denoted by the pair G = (@;E), such that@ represents the set of the nodes, whileE represents the set of edges, or links, which connect two elements of@. The Erdos Renyi graph can be generated in two dierent ways. In their rst article Erdos and Renyi described the random graph by G = (@;E), throwing completely at randoml edges2E among the N nodes2@, or in other words, among the N(N 1) 2 possible edges (E&R, 1959)[2]. In this case there are C l N(N 1) 2 dierent graphs with N nodes and l edges, which form a probability space. In the second method, the so-called binomial model, the graph can be generated starting from a fully connected graph (or a completely disconnected one) and with a probabilityp =const;p2 (0; 1) of having, or not, a link between two nodes. Thus for each node the probability to be connected with another one is completely independent. In this case the number of edges is not xed, but it is possible to compute the average number, as E(N) = p N(N 1) 2 . The two methods are completely equivalent; moreover the probability of obtaining