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\geq4$ 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\geq4$. 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.
Introduction
In the study of "majority dynamics," individuals in a network update their opinions to match the majority of their neighbors. Conventional wisdom suggests that a group starting with more than 50% of the population will eventually achieve global consensus. However, this research explores the strategic bribery problem: what is the smallest possible initial bias (the "seed" group) needed to drive the entire network to a specific consensus within a fixed timeframe?
By combining statistical physics with a new reinforcement algorithm, the authors demonstrate that for many networks, a strategic minority can flip the entire system. While finding the absolute "cheapest" initial configuration remains algorithmically difficult, the proposed History-Passing Reinforcement (HPR) algorithm successfully identifies rare initial states that lead to global consensus even when starting from a minority position.
Theoretical Framework and Methods
The study bridges theoretical physics and algorithmic optimization using three primary tools:
- Backtracking Dynamical Cavity Method (BDCM): A statistical physics framework used to count possible trajectories, allowing for the estimation of the theoretical minimum number of seed nodes required.
- History-Passing Reinforcement (HPR): The paper's primary algorithmic contribution. This dynamical version of "Belief Propagation Reinforcement" iteratively calculates and reinforces the marginal probabilities of node states to converge on valid initial configurations.
- Replica Symmetry Breaking (1RSB): A sophisticated tool used to analyze the solution landscape. It explains why some solutions are easily found while others are "frozen" in isolated clusters, becoming unreachable for standard algorithms.
These methods were evaluated on Random $d$-Regular Graphs (RRGs) with $n = 100$ to $10,000$ nodes, testing various degrees ($d=3$ to $12$) and time horizons ($p=1$ to $14$ steps). HPR was benchmarked against Simulated Annealing (SA), a standard optimization metaheuristic.
Key Results and Insights
- The Power of the Minority: For networks with $d \ge 4$, a global minority is sufficient to drive consensus. As connectivity increases, the required initial bias scales as $1/\sqrt{d}$. For example, in a 4-regular graph with a 3-step window ($p=3$), HPR found initial configurations with negative magnetization (a $+1$ minority) that still led to a $+1$ consensus.
- The Algorithmic Wall: A gap exists between theoretical possibility and algorithmic reach. The HPR algorithm hits a limit at the "d1RSB" transition. Beyond this point, solutions become so rare and isolated (frozen) that they are effectively invisible to message-passing techniques.
- Superior Performance: HPR consistently outperformed Simulated Annealing, finding solutions with significantly lower initial costs. For $d=4, p=1$, the random threshold is $\approx 0.617$, but HPR successfully identified solutions at $\approx 0.263$.
- Logical Mpemba Effect: The authors observed that some "hotter" initial states—those further from consensus in raw numbers—actually reach the goal faster by following specific, efficient relaxation pathways, analogous to the Mpemba effect in physics.
Discussion and Limitations
While HPR is powerful, its computational complexity grows exponentially with the number of time steps ($p$) and node degree ($d$). Currently, the method is optimized for short trajectories, and its scalability to dynamics requiring hundreds of steps remains an open question. Furthermore, while random regular graphs provide a controlled environment, real-world social networks with "small-world" properties and hubs may exhibit different dynamics. Future work may extend HPR to models like epidemic spreading or rumor dynamics to see if similar strategic minorities can be identified in more complex topologies.
Summary updated