Abstract
We introduce two models of consensus following a majority rule on time-evolving stochastic block models (SBM), in which the network evolution is Markovian or non-Markovian. Under the majority rule, in each round, each agent simultaneously updates his/her opinion according to the majority of his/her neighbors. Our network has a community structure and randomly evolves with time. In contrast to the classic setting, the dynamics is not purely deterministic and reflects the structure of SBM by resampling the connections at each step, making agents with the same opinion more likely to connect than those with different opinions. In the Markovian model, connections between agents are resampled at each step according to the SBM law. We prove a "power-of-one" type result, where any initial bias leads to a non-trivial advantage of winning in the end. In the non-Markovian model, a connection is resampled only when an agent changes opinion. We study the phase transition between fast convergence to consensus and a halt of the dynamics, establishing thresholds for the initial lead.
Introduction
In the study of distributed computing and social networks, majority dynamics is a classic rule: every individual (agent) adopts the opinion held by the majority of their neighbors. While most previous research focused on static graphs, real-world social ties are inherently dynamic. We often seek out people who agree with us, a phenomenon known as homophily. This paper addresses the gap by modeling majority dynamics on a graph that evolves based on the agents' current opinions using the Stochastic Block Model (SBM). In this framework, the probability of a connection between two people is higher ($p$) if they share an opinion and lower ($q$) if they do not.
The Markovian Model: The Power of One
In the Markovian model, the network's entire connectivity is reset at every time step. All connections are erased and redrawn based on the current opinions of the agents. This makes the number of people holding a specific opinion a Markov Chain, where the next state depends only on the current one.
A key finding in this model is the "power-of-one" result. The authors prove that even if the initial lead is just one person ($\Delta = 1$), that side has a statistically significant advantage and is more likely to win in the long run, regardless of how large the network is. For any initial bias $\Delta > 0$, the probability of that opinion winning is at least $1/2 + 1/L$ (where $L$ is a constant). If the bias grows with the network size, the probability of winning approaches 100%.
The Non-Markovian Model: Phase Transitions and Rapid Convergence
The non-Markovian model introduces memory into the system: connections are only redrawn for agents who change their opinion. If you keep your opinion, you keep your old connections. This partial resampling introduces complex dependencies that make mathematical analysis more challenging.
This model exhibits a sharp phase transition. The SBM structure ($p > q$) creates a "stubbornness" effect; if the initial lead is below a specific critical threshold ($\Delta_c$), the dynamics simply stop because no one has enough "opposite" neighbors to justify changing their mind. However, if the initial bias is strong enough to overcome this halting threshold, the network reaches total consensus incredibly fast—typically within just three steps.
Numerical Validation
As a theoretical probability paper, the authors conducted numerical simulations to validate their theorems. They simulated networks with up to 500 agents, running the dynamics 1,000 times for various values of $p, q,$ and initial bias $\Delta$. These simulations confirmed their theoretical "H-constant" for the phase transition. For example, with $p=1.0$ and $q=0.3$, the predicted critical value $L^* \approx 2.788$ matched the point where the simulation results flipped from 100% consensus to nearly 100% halting.
Conclusion and Future Work
This research provides a rigorous framework for understanding how opinion-based network evolution affects consensus. While the current proofs assume a "dense" regime where $p$ and $q$ are constants, future work could extend these results to sparse graphs. Other promising directions include exploring $k$-majority dynamics, where agents only sample a small number of neighbors, or integrating fixed community blocks that exist independently of current opinions.
Summary updated