[Paper] Temporal Conductance and Bounds on the Voter Model for Dynamic Networks
Source: arXiv - 2606.13374v1
Overview
The voter model is a classical stochastic process that models how opinions might spread through a network: at each step, every node lazily adopts the opinion of a random neighbour; eventually all nodes share the same opinion (consensus). Stronger connectivity should yield faster consensus. Berenbrink, Giakkoupis, Kermarrec, and Mallmann-Trenn (ICALP 2016) make this precise via the network’s conductance: if the network has $m$ edges, minimum degree $d_{\min}$, and conductance at least $φ$, then the voter model reaches consensus in expected $O(m/(d_{\min}φ))$ steps. Their results extend to dynamic networks with fixed vertex degrees by considering the network’s conductance at each time step. We introduce temporal conductance $Φ$, a more general connectivity measure for dynamic networks. Unlike static conductance, which collapses to $0$ whenever some snapshot is disconnected, $Φ$ captures connectivity through edges that appear at different times. We generalise the results of Berenbrink et al. from static conductance to temporal conductance, showing that the expected consensus time of the standard voter model is at most $O(m/(d_{\min}Φ))$. Moreover, we prove that this bound is tight up to constant factors. We expect temporal conductance to be a useful primitive for analysing other dynamics on temporal networks, and potentially time-inhomogeneous Markov chains more generally.
Key Contributions
This paper presents research in the following areas:
- cs.DC
- cs.DS
- math.PR
Methodology
Please refer to the full paper for detailed methodology.
Practical Implications
This research contributes to the advancement of cs.DC.
Authors
- Tatiana Rocha Avila
- Holger Dell
- John Lapinskas
Paper Information
- arXiv ID: 2606.13374v1
- Categories: cs.DC, cs.DS, math.PR
- Published: June 11, 2026
- PDF: Download PDF