Document Open Access Logo

On the Voting Time of the Deterministic Majority Process

Authors Dominik Kaaser, Frederik Mallmann-Trenn, Emanuele Natale

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.55.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Author Details

Dominik Kaaser
Frederik Mallmann-Trenn
Emanuele Natale

Cite As Get BibTex

Dominik Kaaser, Frederik Mallmann-Trenn, and Emanuele Natale. On the Voting Time of the Deterministic Majority Process. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.55

Abstract

In the deterministic binary majority process we are given a simple graph where each node has one out of two initial opinions. In every round, each node adopts the majority opinion among its neighbors. It is known that this process always converges in O(|E|) rounds to a two-periodic state in which every node either keeps its opinion or changes it in every round.

It has been shown by Frischknecht, Keller, and Wattenhofer (2013) that the O(|E|) bound on the convergence time of the deterministic binary majority process is even for dense graphs tight. However, in many graphs such as the complete graph the process converges in just
a constant number of rounds from any initial opinion assignment.

We show that it is NP-hard to decide whether there exists an initial opinion assignment for which it takes more than k rounds to converge to the two-periodic stable state, for a given integer k. We then give a new upper bound on the voting time of the deterministic binary majority process. Our bound can be computed in linear time by carefully exploiting the structure of the potential function by Goles and Olivos. We identify certain modules of a graph G to obtain a new graph G^Delta. This new graph G^Delta has the property that the worst-case convergence time of G^Delta is an upper bound on that of G. Our new bounds asymptotically improve the best known bounds for various graph classes.

Subject Classification

Keywords
  • distributed voting
  • majority rule

Metrics

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

References

  1. 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.
  2. V. Auletta, I. Caragiannis, D. Ferraioli, C. Galdi, and G. Persiano. Minority Becomes Majority in Social Networks. In Proc. WINE ’15, pages 74-88, 2015. Google Scholar
  3. I. Benjamini, S.-O. Chan, R. O'Donnell, O. Tamuz, and L.-Y. Tan. Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs. CoRR, abs/1405.2486, 2014. URL: http://arxiv.org/abs/1405.2486.
  4. E. Berger. Dynamic Monopolies of Constant Size. Journal of Combinatorial Theory, Series B, 83(2):191-200, 2001. Google Scholar
  5. S. Brahma, S. Macharla, S.P. Pal, and S.K. Singh. Fair Leader Election by Randomized Voting. In Proc. ICDCIT ’04, pages 22-31, 2004. Google Scholar
  6. F. Bénézit, P. Thiran, and M. Vetterli. Interval consensus: From quantized gossip to voting. In Proc. ICASSP ’09, pages 3661-3664, 2009. Google Scholar
  7. L. Cardelli and A. Csikász-Nagy. The Cell Cycle Switch Computes Approximate Majority. Scientific Reports, 2(656), 2012. Google Scholar
  8. F. Chierichetti, J.M. Kleinberg, and S. Oren. On Discrete Preferences and Coordination. In Proc. EC ’13, pages 233-250, 2013. Google Scholar
  9. C. Cooper, R. Elsässer, H. Ono, and T. Radzik. Coalescing Random Walks and Voting on Connected Graphs. SIAM Journal on Discrete Mathematics, 27(4):1748-1758, 2013. Google Scholar
  10. G. Cordasco and L. Gargano. Community Detection via Semi–Synchronous Label Propagation Algorithms. In Proc. BASNA ’10, pages 1-8, 2010. Google Scholar
  11. A. Cournier and M. Habib. A New Linear Algorithm for Modular Decomposition. In Proc. 19th Colloquium on Trees in Algebra and Programming (CAAP ’94), pages 68-84, 1994. Google Scholar
  12. X. Deng and C. Papadimitriou. On the Complexity of Cooperative Solution Concepts. Mathematics of Operations Research, 19(2):257-266, 1994. Google Scholar
  13. P. Donnelly and D. Welsh. Finite particle systems and infection models. Mathematical Proceedings of the Cambridge Philosophical Society, 94(01):167-182, 1983. Google Scholar
  14. David Doty. Timing in Chemical Reaction Networks. In Proc. SODA ’14, pages 772-784, 2014. Google Scholar
  15. S. Frischknecht, B. Keller, and R. Wattenhofer. Convergence in (Social) Influence Networks. In Proc. DISC ’13, pages 433-446, 2013. Google Scholar
  16. D. Gifford. Weighted Voting for Replicated Data. In Proc. SOSP ’79, pages 150-162, 1979. Google Scholar
  17. E. Goles. Local Graph Transformations Driven by Lyapunov Functionals. Complex Systems, 3(1):173-184, 1989. Google Scholar
  18. E. Goles and S. Martínez. Neural and Automata Networks. Kluwer, 1990. Google Scholar
  19. E. Goles and A.M. Odlyzko. Decreasing Energy Functions and Lengths of Transients for Some Cellular Automata. Complex Systems, 2(5):501-507, 1988. Google Scholar
  20. E. Goles and J. Olivos. Periodic behaviour of generalized threshold functions. Discrete Mathematics, 30(2):187-189, 1980. Google Scholar
  21. E. Goles-Chacc, F. Fogelman-Soulié, and D. Pellegrin. Decreasing energy functions as a tool for studying threshold networks. Discrete Applied Mathematics, 12(3):261-277, 1985. Google Scholar
  22. Y. Hassin and D. Peleg. Distributed Probabilistic Polling and Applications to Proportionate Agreement. Information and Computation, 171(2):248-268, 2001. Google Scholar
  23. 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. Google Scholar
  24. Barry W. Johnson, editor. Design & Analysis of Fault Tolerant Digital Systems. Addison-Wesley, 1989. Google Scholar
  25. D. Kaaser, F. Mallmann-Trenn, and E. Natale. Brief Announcement: On the Voting Time of the Deterministic Majority Process. In Proc. DISC ’15, 2015. Google Scholar
  26. D. Kaaser, F. Mallmann-Trenn, and E. Natale. On the Voting Time of the Deterministic Majority Process. CoRR, abs/1508.03519, 2015. URL: http://arxiv.org/abs/1508.03519.
  27. B. Keller, D. Peleg, and R. Wattenhofer. How Even Tiny Influence Can Have a Big Impact! In Proc. FUN ’14, pages 252-263, 2014. Google Scholar
  28. K. Kothapalli, S. Pemmaraju, and V. Sardeshmukh. On the Analysis of a Label Propagation Algorithm for Community Detection. In Proc. ICDCN ’13, pages 255-269, 2013. Google Scholar
  29. 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
  30. T. Liggett. Interacting Particle Systems. Springer, 1985. Google Scholar
  31. F. Mallmann-Trenn. Bounds on the voting time in terms of the conductance. Master’s thesis, Simon Fraser University, 2014. Master’s thesis. URL: http://summit.sfu.ca/item/14502.
  32. E. Mossel and O. Tamuz. Opinion Exchange Dynamics. CoRR, abs/1401.4770, 2014. URL: http://arxiv.org/abs/1401.4770.
  33. R. Oliveira. On the coalescence time of reversible random walks. Transactions of the American Mathematical Society, 364(4):2109-2128, 2012. Google Scholar
  34. D. Peleg. Local majorities, coalitions and monopolies in graphs: a review. Theoretical Computer Science, 282(2):231-257, 2002. Google Scholar
  35. D. Peleg. Immunity against Local Influence. In Language, Culture, Computation. Computing - Theory and Technology, volume 8001 of LNCS, pages 168-179. Springer, 2014. Google Scholar
  36. S. Poljak and M. Sůra. On periodical behaviour in societies with symmetric influences. Combinatorica, 3(1):119-121, 1983. Google Scholar
  37. S. Poljak and D. Turzík. On an application of convexity to discrete systems. Discrete Applied Mathematics, 13(1):27-32, 1986. Google Scholar
  38. U. Raghavan, R. Albert, and S. Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3):036106, 2007. Google Scholar
  39. A. Sarıyüce, E. Saule, K. Kaya, and U. Çatalyürek. Shattering and Compressing Networks for Betweenness Centrality. In Proc. SDM ’13, pages 686-694, 2013. Google Scholar
  40. O. Tamuz and R. J. Tessler. Majority Dynamics and the Retention of Information. Israel Journal of Mathematics, 206(1):483-507, 2015. Google Scholar
  41. P. Winkler. Puzzled: Delightful Graph Theory. Communications of the ACM, 51(8):104, 2008. Google Scholar
  42. P. Winkler. Puzzled: Solutions and Sources. Communications of the ACM, 51(9):103, 2008. Google Scholar
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