Networks maximizing the consensus time of voter models

Area of Science:

• Complex systems
• Network science
• Statistical physics

Background:

• Voter models are widely used to study opinion dynamics and consensus formation in networks.
• Understanding how network topology influences the speed of consensus is critical for various applications.
• Previous research has explored consensus times but identifying maximal structures under specific rules requires further investigation.

Purpose of the Study:

• To determine which network structures maximize the mean consensus time for voter models under distinct update rules.
• To analytically and numerically investigate the relationship between network topology and consensus dynamics.
• To provide insights into the scalability of consensus time with network size.

Main Methods:

• Analytical calculations to derive consensus times for different network structures.
• Numerical simulations to verify analytical findings and explore complex scenarios.
• Systematic comparison of consensus times across various network types (lollipop, barbell, double-star graphs) and update rules (link dynamics, voter model, invasion process).

Main Results:

• The lollipop graph maximizes mean consensus time under link dynamics.
• The barbell graph maximizes mean consensus time under the voter model.
• The double-star graph maximizes mean consensus time under the invasion process.
• For all identified maximal structures, the largest mean consensus time scales as O(N^3), where N is the number of nodes.

Conclusions:

• Specific network topologies (lollipop, barbell, double-star) are optimal for slowing down consensus under different voter model update rules.
• The identified network structures and their O(N^3) scaling provide a theoretical basis for designing networks with controlled information diffusion.
• These findings have implications for understanding opinion polarization, rumor spreading, and the design of robust communication networks.