Consensus on Dynamic Stochastic Block Models: Fast Convergence and Phase Transitions

Haoyu Wang, Jiaheng Wei, Zhenyuan Zhang

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.

In the Markovian model, all connections are resampled at each step based on the current opinion distribution.

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.

The non-Markovian model only resamples connections for agents who switch opinions, leading to a "stubbornness" effect.

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

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 \emph{Markovian model}, connections between agents are resampled at each step according to the SBM law and each agent updates his/her opinion via the majority rule. We prove a \emph{power-of-one} type result, i.e., any initial bias leads to a non-trivial advantage of winning in the end, uniformly in the size of the network. In the \emph{non-Markovian model}, a connection between two agents is resampled according to the SBM law only when some of the two changes opinion and is otherwise kept the same. We study the phase transition between the fast convergence to the consensus and a halt of the dynamics. Moreover, we establish thresholds of the initial lead for various convergence speeds.
BibTeX
@misc{wang2022consensus,
  author = {Haoyu Wang and Jiaheng Wei and Zhenyuan Zhang},
  title = {{Consensus on Dynamic Stochastic Block Models: Fast Convergence and Phase Transitions}},
  year = {2022},
  eprint = {2209.03999},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.03999},
}
Figure