Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm

Abstract

We investigate how much bias in the initial configuration is required to drive global agreement in synchronous, deterministic majority dynamics on large random $d$-regular graphs. Nodes take values $\pm 1$ and update their states at each discrete time step to align with the majority of their neighbors. Using the backtracking dynamical cavity method (BDCM), we estimate the minimal fraction of initial $+1$ nodes required to achieve a $+1$ consensus in $p$ time steps. Our analysis predicts that for $d\ge 4$ an initial global minority of $+1$ nodes is sufficient to quickly steer the entire system toward consensus on $+1$. We then investigate whether such initial conditions can be determined explicitly for a given large random regular graph. To this end, we introduce a new algorithm, which we name history-passing reinforcement (HPR), designed to find such initial configurations with a minority of $+1$ nodes. We find, as a main result, that the HPR algorithm finds initial configurations where the minority takes over the majority for $d$-regular random graphs with $d\ge 4$. The HPR algorithm outperforms standard simulated annealing-based methods, but does not reach the lowest densities predicted by the BDCM. Rather, the lowest density achievable by the algorithm is near the onset of a dynamical one-step replica symmetry breaking (d1RSB) phase, which we estimate using a one-step replica symmetry breaking (1RSB) formulation of the BDCM. While we focus on the majority dynamics and random $d$-regular graphs, the algorithm can be extended to other dynamical rules and classes of sparse graphs.

References in corpus (31)

• Statistical physics of social dynamics
• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Sociophysics: A review of Galam models
• A message passing approach for general epidemic models
• Phase Transitions in the Coloring of Random Graphs
• Anomalous cooling and heating - the Mpemba effect and its inverse
• Exponentially faster cooling in a colloidal system
• Reconstruction on trees and spin glass transition
• The Mpemba index and anomalous relaxation
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• The Mpemba effect in spin glasses is a persistent memory effect
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Optimizing spread dynamics on graphs by message passing
• Dynamic message-passing equations for models with unidirectional dynamics
• Survey-propagation decimation through distributed local computations
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Majority dynamics on trees and the dynamic cavity method
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
• Minimal contagious sets in random regular graphs
• Disordered Systems Insights on Computational Hardness
• The zero-patient problem with noisy observations
• A message-passing scheme for non-equilibrium stationary states
• Phase transitions in the $q$-coloring of random hypergraphs
• On the number of limit cycles in diluted neural networks
• Dynamical Phase Transitions in Graph Cellular Automata
• Backtracking Dynamical Cavity Method
• Bayes-optimal inference for spreading processes on random networks
• Statistical Mechanics of Inference in Epidemic Spreading
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs