Networks maximizing the consensus time of voter models

2014/04/30 by Yuni Iwamasa, Naoki Masuda
Computer Science · Mathematics · Physics and Astronomy · Social Sciences · #Complex Network Analysis Techniques #Computer science #Electoral Systems and Political Participation #Graph #Mathematics #Opinion Dynamics and Social Influence #Statistics #Theoretical computer science #Voter model #cond-mat.dis-nn #cs.SI #physics.soc-ph

paper · pdf · doi:10.1103/physreve.90.012816

published as Physical Review E, 90, 012816 (2014) · 9 figures, 2 tables

openalex publication_date 2014/07/30 · arxiv created 2014/08/02 · arxiv updated 2014/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We explore the networks that yield the largest mean consensus time of voter models under different update rules. By analytical and numerical means, we show that the so-called lollipop graph, barbell graph, and double-star graph maximize the mean consensus time under the update rules called the link dynamics, voter model, and invasion process, respectively. For each update rule, the largest mean consensus time scales as O(N³), where N is the number of nodes in the network.

Citations

• Maximum hitting time for random walks on graphs
• Incomplete ordering of the voter model on small-world networks
• Comparison of voter and Glauber ordering dynamics on networks
• Voter model dynamics in complex networks: Role of dimensionality, disorder, and degree distribution
• Voter models on heterogeneous networks
• Conservation laws for the voter model in complex networks
• Statistical physics of social dynamics
• Evolutionary dynamics and fixation probabilities in directed networks
• Voter model on the two-clique graph
• Analytical solution of the voter model on uncorrelated networks
• Stochastic Processes in Physics and Chemistry