Majority Dynamics on Assortative Sparse Stochastic Block Models

Abstract

Majority dynamics is a two-opinion process in which each vertex repeatedly updates to the majority opinion among its neighbors. We study this process on a resampled sparse binary stochastic block model in the assortative regime. At each time step, a graph is sampled from the current opinion partition: vertices with the same opinion are joined with probability $\hat{I}\pm =a\log N/N$, while vertices with differing opinions are joined with probability ${\hat{I}}^2=b\log N/N$, where $a>b>1$. Let $B_t$ and $R_t$ denote the blue and red camps at time $t$. We show that the weighted advantage $\tilde{\hat{I}}{”}_t=b|B_t|-a|R_t|$, rather than the unweighted advantage $\hat{I}{”}_t=|B_t|-|R_t|$ alone, governs the pace to unanimity. Our results, which hold with high probability as \(N\to\infty\), identify three regimes for blue unanimity under the initial blue advantage, i.e., $\hat{I}{”}_0>0$: constant time, subpolynomial time, and polynomial time. First, when $\tilde{\hat{I}}{”}_0\gtrsim -N/\sqrt{\log N}$, blue unanimity occurs within three updates. Second, when $\tilde{\hat{I}}{”}_0<0$ and $|\tilde{\hat{I}}{”}_0|=o(N)$, blue unanimity occurs within $N^{o(1)}$ updates. Furthermore, when $\tilde{\hat{I}}{”}_0<0$, $|\tilde{\hat{I}}{”}_0|=O(N)$, and $\hat{I}{”}_0\gg \sqrt{N/\log N}$, blue unanimity still occurs within $N^{I_0+o(1)}$ updates, where \[ I_0= \left(\mathbf{ReLU}\Big(\sqrt{a\frac{|R_0|}{N}}-\sqrt{b\frac{|B_0|}{N}}\Big)\right)^2, \] and $\mathbf{ReLU}(x)=\max \{x,0\}$. Conversely, away from the weighted threshold, when $|B_0|/|R_0|\le a/b-\hat{I}º$ and $\hat{I}{”}_0>0$, $N^{I_0-o(1)}$ updates are necessary for blue unanimity. Our analysis relies on detailed estimates for one-vertex flip probabilities in sparse binomial differences, which could be of independent interest.

56 pages, 6 figures