Document Open Access Logo

Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models

Authors Nobutaka Shimizu, Takeharu Shiraga

PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.32.pdf
  • Filesize: 1.38 MB
  • 17 pages

Document Identifiers

Author Details

Nobutaka Shimizu
  • The University of Tokyo, Japan
Takeharu Shiraga
  • Chuo University, Tokyo, Japan

Funding

  • Shimizu, Nobutaka: JST CREST Grant Number JPMJCR14D2 and JSPS KAKENHI Grant Number 19J12876, Japan
  • Shiraga, Takeharu: JSPS KAKENHI Grant Number 17H07116 and 19K20214, Japan

Acknowledgements

We would like to thank Colin Cooper, Nan Kang and Tomasz Radzik for helpful discussions. We also thank the anonymous reviewers for their helpful comments.

Cite AsGet BibTex

Nobutaka Shimizu and Takeharu Shiraga. Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.DISC.2019.32

Abstract

This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the Best-of-two and the Best-of-three. Here at each synchronous and discrete time step, each vertex updates its opinion to match the majority among the opinions of two random neighbors and itself (the Best-of-two) or the opinions of three random neighbors (the Best-of-three). Previous studies have explored these processes on complete graphs and expander graphs, but we understand significantly less about their properties on graphs with more complicated structures. In this paper, we study the Best-of-two and the Best-of-three on the stochastic block model G(2n,p,q), which is a random graph consisting of two distinct Erdős-Rényi graphs G(n,p) joined by random edges with density q <= p. We obtain two main results. First, if p=omega(log n/n) and r=q/p is a constant, we show that there is a phase transition in r with threshold r^* (specifically, r^*=sqrt{5}-2 for the Best-of-two, and r^*=1/7 for the Best-of-three). If r>r^*, the process reaches consensus within O(log log n+log n/log (np)) steps for any initial opinion configuration with a bias of Omega(n). By contrast, if r<r^*, then there exists an initial opinion configuration with a bias of Omega(n) from which the process requires at least 2^{Omega(n)} steps to reach consensus. Second, if p is a constant and r>r^*, we show that, for any initial opinion configuration, the process reaches consensus within O(log n) steps. To the best of our knowledge, this is the first result concerning multiple-choice voting for arbitrary initial opinion configurations on non-complete graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Stochastic processes
  • Mathematics of computing → Random graphs
Keywords
  • Distributed Voting
  • Consensus Problem
  • Random Graph

Metrics

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

Related Versions

References

  1. E. Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18(177):1-86, 2018. Google Scholar
  2. E. Abbe and C. Sandon. Recovering communities in the general stochastic block model without knowing the parameters. In Proceedings of the 28th International Conference on Neural Information Processing Systems (NIPS), 1:676-684, 2015. Google Scholar
  3. M. A. Abdullah and M. Draief. Global majority consensus by local majority polling on graphs of a given degree sequence. Discrete Applied Mathematics, 1(10):1-10, 2015. Google Scholar
  4. Y. Afek, N. Alon, O. Barad, E. Hornstein, N. Barkai, and Z. Bar-Joseph. A biological solution to a fundamental distributed computing problem. Science, 331(6014):183-185, 2011. Google Scholar
  5. P. Barbillon, S. Donnet, E. Lazega, and A. Bar-Hen. Stochastic block models for multiplex networks: an application to a multilevel network of researchers. Journal of the Royal Statistical Society Series A, 180(1):295-314, 2017. Google Scholar
  6. L. Becchetti, A. Clementi, P. Manurangsi, E. Natale, F. Pasquale, P. Raghavendra, and L. Trevisan. Average whenever you meet: Opportunistic protocols for community detection. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA), 7:1-13, 2018. Google Scholar
  7. L. Becchetti, A. Clementi, E. Natale, F. Pasquale, R. Silvestri, and L. Trevisan. Simple dynamics for plurality consensus. Distributed Computing, 30(4):293-306, 2017. Google Scholar
  8. L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and L. Trevisan. Stabilizing consensus with many opinions. In Proceedings of the 27th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 620-635, 2016. Google Scholar
  9. L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and L. Trevisan. Find your place: Simple distributed algorithms for community detection. In Proceedings of the 28th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 940-959, 2017. Google Scholar
  10. P. Berenbrink, A. Clementi, R. Elsässer, P. Kling, F. Mallmann-Trenn, and E. Natale. Ignore or comply? On breaking symmetry in consensus. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 335-344, 2017. Google Scholar
  11. J. Chen and B. Yuan. Detecting functional modules in the yeast protein-protein interaction network. Bioinformatics, 22(18):2283-2290, 2006. Google Scholar
  12. 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
  13. C. Cooper, R. Elsässer, and T. Radzik. The power of two choices in distributed voting. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), 2:435-446, 2014. Google Scholar
  14. C. Cooper, R. Elsässer, T. Radzik, N. Rivera, and T. Shiraga. Fast consensus for voting on general expander graphs. In Proceedings of the 29th International Symposium on Distributed Computing (DISC), pages 248-262, 2015. Google Scholar
  15. C. Cooper, T. Radzik, N. Rivera, and T. Shiraga. Fast plurality consensus in regular expanders. In Proceedings of the 31st International Symposium on Distributed Computing (DISC), 91(13):1-16, 2017. Google Scholar
  16. C. Cooper and N. Rivera. The linear voting model. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), 55(144):1-12, 2016. Google Scholar
  17. E. Cruciani, E. Natale, A. Nusser, and G. Scornavacca. Phase transition of the 2-choices dynamics on core-periphery networks. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 777-785, 2018. Google Scholar
  18. E. Cruciani, E. Natale, and G. Scornavacca. Distributed community detection via metastability of the 2-choices dynamics. In Proceedings of the 33rd AAAI conference on artificial intelligence (AAAI), pages 6046-6053, 2019. Google Scholar
  19. B. Doerr, L. A. Goldberg, L. Minder, T. Sauerwald, and C. Scheideler. Stabilizing consensus with the power of two choices. In Proceedings of the 23rd annual ACM symposium on Parallelism in algorithms and architectures (SPAA), pages 149-158, 2011. Google Scholar
  20. M. Fischer, N. Lynch, and M. Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1(1):26-39, 1986. Google Scholar
  21. A. Frieze and M. Karońsky. Introduction to random graphs. Campridge University Press, 2016. Google Scholar
  22. M. Ghaffari and J. Lengler. Nearly-tight analysis for 2-choice and 3-majority consensus dynamics. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 305-313, 2018. Google Scholar
  23. S. Gilbert and D. Kowalski. Distributed agreement with optimal communication complexity. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 965-977, 2010. Google Scholar
  24. A. Goldenberg, A. X. Zheng, S. E. Fienberg, and E. M. Airoldi. A survey of statistical network models. Foundations and Trends in Machine Learning, 2(2):129-233, 2010. Google Scholar
  25. Y. Hassin and D. Peleg. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248-268, 2001. Google Scholar
  26. M. Hirsch and H. L. Smith. Monotone dynamical systems. In Handbook of Differential Equations: Ordinary Differential Equations, 2(4):239-357, 2005. Google Scholar
  27. V. Kanade, F. Mallmann-Trenn, and T. Sauerwald. On coalescence time in graphs: When is coalescing as fast as meeting? In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 956-965, 2019. Google Scholar
  28. N. Kang and R. Rivera. Best-of-Three voting on dense graphs. In Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 115-121, 2019. Google Scholar
  29. J. H. Kim and V. H. Vu. Concentration of multivariate polynomials and its applications. Combinatorica, 20:417-434, 2000. Google Scholar
  30. T. M. Liggett. Interacting particle systems. Springer-Verlag, 1985. Google Scholar
  31. E. M. Marcotte, M. Pellegrini, H.-L. Ng, D. W. Rice, T. O. Yeates, and D. Eisenberg. Detecting protein function and protein-protein interactions from genome sequences. Science, 285(5428):751-753, 1999. Google Scholar
  32. E. Mossel, J. Neeman, and O. Tamuz. Majority dynamics and aggregation of information in social networks. Autonomous Agents and Multi-Agent Systems, 28(3):408-429, 2014. Google Scholar
  33. T. Nakata, H. Imahayashi, and M. Yamashita. Probabilistic local majority voting for the agreement problem on finite graph. In Proceedings of the 5th Annual International Computing and Combinatorics Conference (COCOON), pages 330-338, 1999. Google Scholar
  34. R. I. Oliveira and Y. Peres. Random walks on graphs: new bounds on hitting, meeting, coalescing and returning. In Proceedings of the 16th Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pages 119-126, 2019. Google Scholar
  35. G. Schoenebeck and F. Yu. Consensus of interacting particle systems on Erdős-Rényi graphs. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1945-1964, 2018. Google Scholar
  36. N. Shimizu and T. Shiraga. Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models. arXiv, 2019. URL: http://arxiv.org/abs/1907.12212.
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 Imprint Privacy Contact