Search papers, labs, and topics across Lattice.
This paper extends the classical voter model to dynamic networks by introducing a new measure called temporal conductance, which captures connectivity through edges that appear over time. The authors generalize existing results on consensus time from static to dynamic networks, demonstrating that the expected time to reach consensus is bounded by \(O(m/(d_{\min}\Phi))\), where \(\Phi\) is the temporal conductance. Their findings not only refine the understanding of opinion dynamics in evolving networks but also establish a tight bound on consensus time, paving the way for further analysis of dynamics in temporal networks.
Temporal conductance reveals that consensus in dynamic networks can be reached significantly faster than previously thought, challenging assumptions about static connectivity.
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 $\phi$, then the voter model reaches consensus in expected $O(m/(d_{\min}\phi))$ 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 $\Phi$, a more general connectivity measure for dynamic networks. Unlike static conductance, which collapses to $0$ whenever some snapshot is disconnected, $\Phi$ 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}\Phi))$. 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.
