Switch Analysis for Opinion Dynamics on Arbitrary Graphs, With Explicit Constants

Many network processes are simple to describe and hard to time. Agents adopt the majority view of their neighbors, rumors pass from node to node, infections spread and get cured. For each, we want to know how many steps it takes to reach a target state, such as everyone agreeing on the correct opinion. Exact answers exist only on idealized graphs like the complete graph, where the whole state collapses to a single count. On real graphs, proofs use couplings to simpler, deliberately slower processes. These give the right growth rate, but the constants are left unspecified and the results hold only for one random-graph family.

We propose to use switch analysis instead. Switch analysis is a technique from the runtime theory of evolutionary algorithms: it bounds the hitting time of a hard Markov chain by comparing it, step by step, with a reference chain whose hitting time is known exactly. The hard chain here is the opinion dynamics on an arbitrary graph $G$. The reference chain is the same dynamics on the complete graph, solved numerically to exact constants. The price of the comparison is a switch cost: the expected extra delay caused by $G$ differing from the complete graph, summed over the states the process actually visits. Because the cost is averaged over visited states rather than taken in the worst case, it can stay small on sparse graphs whose worst-case spectral quantities are poor. That matches the empirical finding that the spectral gap is a poor predictor of how network topology affects decentralized processes.

Core Claim

For asynchronous majority dynamics, consider a graph $G$ on $n$ nodes and an initial configuration whose correct-opinion count is $m_0$. The expected time to correct consensus satisfies a non-asymptotic bound of the form

$$\mathbb{E}[\tau_G] \;\le\; R(m_0) + \sum_{t \ge 0} \rho_t(G).$$

The terms are defined as follows. $R(m)$ is the exact expected remaining time of the complete-graph reference chain started from $m$ correct agents, computed by solving an $(n+1)$-state linear system. $\rho_t(G)$ is the expected one-step switch cost at time $t$: the difference between the reference remaining time after one true step on $G$ and after one reference step from the same count. A symmetric inequality, with the switch cost bounded from below, gives lower bounds.

Our substantive claim is that $\sum_t \rho_t$ can be bounded analytically in terms of a local quantity. That quantity, which we call the neighborhood majority discrepancy, is the gap between the probability that a random node's neighbors hold a correct majority and the same probability on the complete graph, evaluated on configurations the dynamics actually produces. Expander-style worst-case arguments bound this discrepancy only through the spectral gap. On random regular graphs, sparse Erdős–Rényi graphs and Chung–Lu power-law graphs, we expect the trajectory-averaged discrepancy to be much smaller than the worst-case one. On community-structured graphs, where opinions can stay split between groups (echo chambers), we expect it to be large and positive, which would yield explicit lower bounds.

Where This Sits

The method comes from A General Approach to Running Time Analysis of Multi-objective Evolutionary Algorithms. That paper formalizes switch analysis with a progress function and a reference chain, and obtains explicit constants such as $\le 6n^3$ for GSEMO on LOTZ. A Lower Bound Analysis of Population-based Evolutionary Algorithms for Pseudo-Boolean Functions uses the same comparison in the lower-bound direction. Both apply it only to centralized search on bit strings, with no graph in sight. We carry the technique over unchanged and supply the new ingredient: a topology-dependent switch cost.

The problem and the gap come from the network side. Asynchronous Majority Dynamics on Binomial Random Graphs proves correct consensus in $n\log n$ steps with high probability on $G(n,p)$ with $np \gg \log n$ and $p = o(1)$. It does this by coupling to a strictly less efficient auxiliary process, with no explicit constant and no result outside $G(n,p)$. Simple and optimal randomized fault-tolerant rumor spreading and A lower bound on the performance of dynamic curing policies for epidemics on graphs use the same style of argument, coupling or stochastic dominance onto a simple chain, but restrict themselves to the complete graph or to worst-case starts on high-cutwidth graphs. Our approach differs from all three in two ways. The reference process is exact rather than deliberately slowed, and the loss is charged state by state, so it can be measured.

Two papers constrain the design. Beyond spectral gap: the role of the topology in decentralized learning shows that the spectral gap mispredicts behavior: a ring beats a star even though the star has the larger gap. Any bound driven by worst-case expansion will therefore misrank topologies, and that is why we average the switch cost over visited states. Approximating Optimization Problems using EAs on Scale-Free Networks shows that guarantees tied to power-law structure vanish on clustered small-world graphs. We include such graphs specifically to test whether our discrepancy quantity tracks that breakdown.

A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning supplies a precedent rather than a method. Its exact decomposition of coupled errors cut transient-time dependence from $(1-\lambda)^{-6}$ to $(1-\lambda)^{-2}$, which shows that removing slack can change qualitative conclusions.

Research Program

The first component is the reference chain. On the complete graph, asynchronous majority dynamics depends only on the count $m$ of correct agents, so $R(m)$ can be computed exactly for every $n$ up to about $10^5$. We will also derive closed-form leading constants for its asymptotic form, so that $R(m_0)$ comes as an explicit number rather than a $\Theta(n \log n)$ envelope.

The second component is the choice of progress function on irregular graphs. Following the observation in A General Approach to Running Time Analysis of Multi-objective Evolutionary Algorithms that progress-function design is the hard, human step, we will compare two candidates. One is the plain count of correct agents. The other is a degree-weighted count, which is the natural invariant when high-degree nodes influence more neighbors. We will prove that switch-cost bounds hold under each.

The third component is the analytic bound on the switch cost. We will split the per-state cost into a degree-heterogeneity term and a correlation term. The correlation term captures how far the opinions in a node's neighborhood are from independent draws at the global rate. We will then bound the correlation term along trajectories using a concentration argument, applied while the configuration is still close to exchangeable. The variance-based drift theorem of Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms is the planned tool for the early phase, where the count's drift is weak and variance dominates. We target theorems for random $d$-regular graphs, $G(n,p)$ extended below the Mohan–Pralat density regime, and Chung–Lu power-law graphs with $\beta \in (2,3)$. We also target an explicit lower bound for two-block stochastic block models, stated in terms of the ratio of edges within communities to edges between them.

The fourth component is a diagnostic rather than a theorem. On any finite graph, the terms $\rho_t$ can be estimated by Monte Carlo along simulated trajectories. This shows where in the run the topology costs time, early mixing or late cleanup, and whether that cost is local or global.

Baselines

The naive reference point is direct simulation of $\tau_G$: 1,000 independent runs per graph and per size, matching the replication count used in Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms. This is ground truth, not a competitor for prediction. Every bound is scored by its ratio to the simulated mean, so a ratio of 1 is perfect. We also report the complete-graph prediction $R(m_0)$ alone, which amounts to ignoring topology. Any useful theory must beat it on the graphs where it errs.

The strongest existing analytical result is the auxiliary-process coupling of Asynchronous Majority Dynamics on Binomial Random Graphs, which reports consensus in $n\log n$ steps with high probability for $np \gg \log n$. No explicit leading constant is reported on Lacuna for this bound. To compare fairly, we will carry out its coupling with every constant tracked as carefully as we can, on the same $G(n,p)$ instances. We beat it if our bound's ratio to the simulated mean is smaller at every tested $n$ inside its valid regime, and if our bound remains non-vacuous below that regime, where the existing bound does not apply.

The second analytical baseline is a spectral version of our own bound. It uses the same switch analysis but bounds each per-state cost by its worst case over all configurations of that count, via the expander mixing lemma, so the spectral gap enters. This is also the key ablation. Any gain over it isolates the value of averaging the switch cost over visited states rather than taking the worst case. A second ablation swaps the degree-weighted progress function for the plain count, holding everything else fixed.

Why not just…?

Why not just simulate? For one graph of moderate size, simulation is cheaper and more accurate than any bound, and we concede that. Simulation does not deliver a guarantee for graph families as $n$ grows. It also does not explain which structural property causes a slowdown. Our Monte Carlo estimates of $\rho_t$ are useful only as a diagnostic, and we do not present them as bounds.

Why not just use drift analysis on the correct-opinion count? This is the most serious alternative. When the reference chain is one-dimensional, an additive or multiplicative drift theorem applied to $h$ may recover similar bounds with less machinery. The difference is that a drift theorem needs a single worst-case drift lower bound per state, whereas switch analysis charges only the expected deviation along the trajectory. That said, the two can coincide in the limit. We will derive the best drift-theorem bound on the same progress function and compare constants on every graph family. If drift matches switch analysis within a few percent everywhere, we will report the simpler proof as the result.

Why not just parameterize everything by the spectral gap? Beyond spectral gap: the role of the topology in decentralized learning shows that the spectral gap misranks ring and star topologies, and that it tends to zero on large sparse graphs where processes still converge. The spectral-ablation baseline tests directly whether this failure carries over to majority dynamics.

Why not apply this to decentralized SGD (stochastic gradient descent run by networked workers), the obvious target? Linear gossip averaging has an exact second-moment recursion via matrix powers, so a comparison chain adds nothing there. Switch analysis earns its place only for nonlinear discrete dynamics such as majority voting, where no such recursion exists.

Proposed Experiments

The graph suite covers the main structural regimes. It includes $G(n,p)$ with $np$ ranging from $\log n$ to $(\log n)^2$, random $d$-regular graphs with $d \in \{3, 8, 32\}$, Chung–Lu power-law graphs with $\beta \in \{2.2, 2.5, 2.9\}$, Watts–Strogatz small-world graphs at several rewiring rates, two-block stochastic block models across a range of between-block densities, and the ring, star, torus and hypercube topologies of Beyond spectral gap: the role of the topology in decentralized learning. Sizes run from $n = 10^3$ to $10^5$, with the initial correct fraction swept just above one half.

The metrics are three: the ratio of each bound to the simulated mean hitting time, the rank correlation across topologies between predicted and observed slowdown relative to the complete graph, and the probability of correct consensus.

Three outcomes would settle the proposal. First, on the expander-like families, the analytic bound's ratio to the simulated mean should stay bounded by a small constant, below 2, as $n$ grows. The constant-tracked coupling baseline should not. Second, the trajectory-averaged discrepancy should rank the ring, star, torus and hypercube topologies correctly where the spectral ablation does not. Third, on the two-block models, the lower bound should predict the between-block density at which consensus time stops scaling like $n \log n$, with the predicted transition point within a constant factor of the empirical one. If the second check fails, then averaging over visited states buys nothing over worst-case spectral reasoning, and the proposal reduces to a constant-tightening exercise on $G(n,p)$.