Temporal Conductance and Bounds on the Voter Model for Dynamic Networks
Abstract
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 dmin, and conductance at least ϕ, then the voter model reaches consensus in expected O(m/(dminϕ)) 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/(dminΦ)). 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.
Related
- Partisan voter model on complex networks: Dynamics of local ordering
- All-Minors Matrix-Tree Theory for Superport Networks: Completed Quotient-Incidence Determinants and Conductance-Weighted Subdivision Extensions
- A Non-Stationary Spatio-Temporal Covariance Model with Dynamic Advection Effects for Rainfall Data
- Sharp Causal Bounds for Dynamic Treatment Regimes
- Extended dynamic mode decomposition with Fourier dictionaries: Error bounds and fast implementation
BibTeX
@misc{avila2026temporal,
title = {{Temporal Conductance and Bounds on the Voter Model for Dynamic Networks}},
author = {Tatiana Rocha Avila and Holger Dell and John Lapinskas},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.13374},
eprint = {2606.13374},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.13374},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Temporal Conductance and Bounds on the Voter Model for Dynamic Networks
AU - Tatiana Rocha Avila
AU - Holger Dell
AU - John Lapinskas
PY - 2026
DA - 2026/10/31
PB - arXiv
DO - 10.48550/arxiv.2606.13374
UR - https://arxiv.org/abs/2606.13374
AB - 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.
ER -