Berenbrink, Petra ;
Giakkoupis, George ;
Kermarrec, AnneMarie ;
MallmannTrenn, Frederik
Bounds on the Voter Model in Dynamic Networks
Abstract
In the voter model, each node of a graph has an opinion, and in every round each node chooses independently a random neighbour and adopts its opinion. We are interested in the consensus time, which is the first point in time where all nodes have the same opinion. We consider dynamic graphs in which the edges are rewired in every round (by an adversary) giving rise to the graph sequence G_1, G_2, ..., where we assume that G_i has conductance at least phi_i. We assume that the degrees of nodes don't change over time as one can show that the consensus time can become superexponential otherwise. In the case of a sequence of dregular graphs, we obtain asymptotically tight results. Even for some static graphs, such as the cycle, our results improve the state of the art. Here we show that the expected number of rounds until all nodes have the same opinion is bounded by O(m/(d_{min}*phi)), for any graph with m edges, conductance phi, and degrees at least d_{min}. In addition, we consider a biased dynamic voter model, where each opinion i is associated with a probability P_i, and when a node chooses a neighbour with that opinion, it adopts opinion i with probability P_i (otherwise the node keeps its current opinion). We show for any regular dynamic graph, that if there is an epsilon > 0 difference between the highest and second highest opinion probabilities, and at least Omega(log(n)) nodes have initially the opinion with the highest probability, then all nodes adopt w.h.p. that opinion. We obtain a bound on the convergence time, which becomes O(log(n)/phi) for static graphs.
BibTeX  Entry
@InProceedings{berenbrink_et_al:LIPIcs:2016:6290,
author = {Petra Berenbrink and George Giakkoupis and AnneMarie Kermarrec and Frederik MallmannTrenn},
title = {{Bounds on the Voter Model in Dynamic Networks}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {146:1146:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6290},
URN = {urn:nbn:de:0030drops62901},
doi = {10.4230/LIPIcs.ICALP.2016.146},
annote = {Keywords: Voting, Distributed Computing, Conductance, Dynamic Graphs, Consensus}
}
2016
Keywords: 

Voting, Distributed Computing, Conductance, Dynamic Graphs, Consensus 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

2016 