Phase transition of the 2-Choices dynamics on core–periphery networks

• Published in: Distributed computing 2021-06, Vol.34 (3), p.207-225
• Main Authors: Cruciani, Emilio, Natale, Emanuele, Nusser, André, Scornavacca, Giacomo
• Format: Article
• Language: English
• Subjects: Computer Communication Networks; Computer Hardware; Computer Science; Computer Systems Organization and Communication Networks; Distributed, Parallel, and Cluster Computing; Dynamic structural analysis; Networks; Phase transitions; Software Engineering/Programming and Operating Systems; Theory of Computation
• ISSN: 0178-2770; 1432-0452
• DOI: 10.1007/s00446-021-00396-5

The 2-Choices dynamics is a process that models voting behavior on networks and works as follows: Each agent initially holds either opinion blue or red ; then, in each round, each agent looks at two random neighbors and, if the two have the same opinion, the agent adopts it. We study its behavior on a class of networks with core–periphery structure. Assume that a densely-connected subset of agents, the core , holds a different opinion from the rest of the network, the periphery . We prove that, depending on the strength of the cut between core and periphery, a phase-transition phenomenon occurs: Either the core’s opinion rapidly spreads across the network, or a metastability phase takes place in which both opinions coexist for superpolynomial time. The interest of our result, which we also validate with extensive experiments on real networks, is twofold. First, it sheds light on the influence of the core on the rest of the network as a function of its connectivity toward the latter. Second, it is one of the first analytical results which shows a heterogeneous behavior of a simple dynamics as a function of structural parameters of the network.