Minority takeover in majority dynamics: Searching for rare initializations via the history passing algorithm

Area of Science:

• Statistical Physics
• Network Science
• Complex Systems

Background:

• Investigating consensus formation in complex systems is crucial for understanding emergent behavior.
• Synchronous, deterministic majority dynamics on random graphs model social and biological systems.
• Determining the minimal conditions for global agreement is a key challenge in network dynamics.

Purpose of the Study:

• To quantify the minimum initial bias needed for global consensus in majority dynamics.
• To develop an algorithm for finding such initial configurations on random d-regular graphs.
• To compare algorithmic performance with theoretical predictions.

Main Methods:

• Utilized the backtracking dynamical cavity method (BDCM) to estimate minimal initial fractions.
• Introduced a novel algorithm, history-passing reinforcement (HPR), to find minority-driven consensus configurations.
• Employed a one-step replica symmetry-breaking formulation of BDCM to estimate phase transitions.

Main Results:

• For d≥4, an initial minority of +1 nodes is sufficient to achieve global +1 consensus.
• The HPR algorithm successfully finds initial configurations where a minority drives consensus on d-regular random graphs (d≥4).
• HPR outperforms simulated annealing but achieves lower densities than BDCM predictions, near the one-step replica symmetry-breaking phase onset.

Conclusions:

• Minimal initial bias can effectively steer large random networks towards global consensus.
• The HPR algorithm provides a practical method for finding such configurations, demonstrating minority influence.
• Findings offer insights into phase transitions in network dynamics and have potential extensions to diverse systems.