Document Open Access Logo

Bounds on the Voter Model in Dynamic Networks

Authors Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, Frederik Mallmann-Trenn

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.146.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Petra Berenbrink
George Giakkoupis
Anne-Marie Kermarrec
Frederik Mallmann-Trenn

Cite As Get BibTex

Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, and Frederik Mallmann-Trenn. Bounds on the Voter Model in Dynamic Networks. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 146:1-146:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.146

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.

Subject Classification

Keywords
  • Voting
  • Distributed Computing
  • Conductance
  • Dynamic Graphs
  • Consensus

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Mohammed Amin Abdullah and Moez Draief. Global majority consensus by local majority polling on graphs of a given degree sequence. Discrete Applied Mathematics, 180:1-10, 2015. Google Scholar
  2. D. Aldous and J. Fill. Reversible markov chains and random walks on graphs, 2002. Unpublished. URL: http://www.stat.berkeley.edu/~aldous/RWG/book.html.
  3. Chen Avin, Michal Koucký, and Zvi Lotker. How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, pages 121-132, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70575-8_11.
  4. C. Cooper, R. Elsässer, H. Ono, and T. Radzik. Coalescing random walks and voting on connected graphs. SIAM J. Discrete Math., 27(4):1748-1758, 2013. URL: http://dx.doi.org/10.1137/120900368.
  5. C. Cooper, R. Elsässer, and T. Radzik. The power of two choices in distributed voting. In ICALP, pages 435-446, 2014. Google Scholar
  6. Colin Cooper, Robert Elsässer, Tomasz Radzik, Nicolás Rivera, and Takeharu Shiraga. Fast Consensus for Voting on General Expander Graphs. In Proc. DISC ’15, pages 248-262, 2015. Google Scholar
  7. James Cruise and Ayalvadi Ganesh. Probabilistic consensus via polling and majority rules. Queueing Systems, 78(2):99-120, 2014. Google Scholar
  8. J. Díaz, L. Goldberg, G. Mertzios, D. Richerby, M. Serna, and P. Spirakis. Approximating fixation probabilities in the generalized moran process. Algorithmica, 69(1):78-91, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9722-7.
  9. P. Donnelly and D. Welsh. Finite particle systems and infection models. Mathematical Proceedings of the Cambridge Philosophical Society, 94:167-182, 1983. Google Scholar
  10. R. Elsässer, T. Friedetzky, D. Kaaser, F. Mallmann-Trenn, and H. Trinker. Efficient k-Party Voting with Two Choices. ArXiv e-prints, February 2016. URL: http://arxiv.org/abs/1602.04667.
  11. G. Giakkoupis. Tight bounds for rumor spreading in graphs of a given conductance. In STACS, pages 57-68, 2011. Google Scholar
  12. G. Giakkoupis, T. Sauerwald, and A. Stauffer. Randomized rumor spreading in dynamic graphs. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 495-507, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_42.
  13. Y. Hassin and D. Peleg. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248-268, 2001. URL: http://dx.doi.org/http://dx.doi.org/10.1006/inco.2001.3088.
  14. R. Holley and T. Liggett. Ergodic theorems for weakly interacting infinite systems and the voter model. The Annals of Probability, 3(4):643-663, 1975. URL: http://www.jstor.org/stable/2959329.
  15. B. Houchmandzadeh and M. Vallade. The fixation probability of a beneficial mutation in a geographically structured population. New Journal of Physics, 13(7):073020, 2011. URL: http://stacks.iop.org/1367-2630/13/i=7/a=073020.
  16. M. Kearns and J. Tan. Biased voting and the democratic primary problem. In WINE, pages 639-652, 2008. Google Scholar
  17. F. Kuhn, N. Lynch, and R. Oshman. Distributed computation in dynamic networks. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 513-522, 2010. URL: http://dx.doi.org/10.1145/1806689.1806760.
  18. H. Lam, Z. Liu, M. Mitzenmacher, X. Sun, and Y. Wang. Information dissemination via random walks in d-dimensional space. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'12, pages 1612-1622. SIAM, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095244.
  19. N. Lanchier and C. Neuhauser. Voter model and biased voter model in heterogeneous environments. Journal of Applied Probability, 44(3):770-787, 2007. Google Scholar
  20. T. Liggett. Interacting Particle Systems. Springer Berlin Heidelberg, 1985. URL: http://dx.doi.org/10.1007/b138374.
  21. G. Mertzios and P. Spirakis. Strong bounds for evolution in networks. In ICALP, pages 669-680, 2013. Google Scholar
  22. T. Nakata, H. Imahayashi, and M. Yamashita. A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem. Networks, 35(4):266-273, 2000. URL: http://dx.doi.org/10.1002/1097-0037(200007)35:4<266::AID-NET5>3.0.CO;2-4.
  23. R. Oliveira. On the coalescence time of reversible random walks. Trans. Am. Math. Soc., 364(4):2109-2128, 2012. Google Scholar
  24. Y Peres, A. Sinclair, P. Sousi, and A. Stauffer. Mobile geometric graphs: detection, coverage and percolation. Probability Theory and Related Fields, 156(1-2):273-305, 2013. URL: http://dx.doi.org/10.1007/s00440-012-0428-1.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact