License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.146
URN: urn:nbn:de:0030-drops-62901
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6290/
Berenbrink, Petra ;
Giakkoupis, George ;
Kermarrec, Anne-Marie ;
Mallmann-Trenn, 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 super-exponential otherwise. In the case of a sequence of d-regular 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 Anne-Marie Kermarrec and Frederik Mallmann-Trenn},
title = {{Bounds on the Voter Model in Dynamic Networks}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {146:1--146:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6290},
URN = {urn:nbn:de:0030-drops-62901},
doi = {10.4230/LIPIcs.ICALP.2016.146},
annote = {Keywords: Voting, Distributed Computing, Conductance, Dynamic Graphs, Consensus}
}
|
Keywords: |
|
Voting, Distributed Computing, Conductance, Dynamic Graphs, Consensus |
|
Collection: |
|
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
23.08.2016 |
