Document Open Access Logo

Opinion Forming in Erdös-Rényi Random Graph and Expanders

Author Ahad N. Zehmakan

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.4.pdf
  • Filesize: 452 kB
  • 13 pages

Document Identifiers

Author Details

Ahad N. Zehmakan
  • ETH Zurich, Switzerland

Cite AsGet BibTex

Ahad N. Zehmakan. Opinion Forming in Erdös-Rényi Random Graph and Expanders. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.4

Abstract

Assume for a graph G=(V,E) and an initial configuration, where each node is blue or red, in each discrete-time round all nodes simultaneously update their color to the most frequent color in their neighborhood and a node keeps its color in case of a tie. We study the behavior of this basic process, which is called majority model, on the Erdös-Rényi random graph G_{n,p} and regular expanders. First we consider the behavior of the majority model on G_{n,p} with an initial random configuration, where each node is blue independently with probability p_b and red otherwise. It is shown that in this setting the process goes through a phase transition at the connectivity threshold, namely (log n)/n. Furthermore, we say a graph G is lambda-expander if the second-largest absolute eigenvalue of its adjacency matrix is lambda. We prove that for a Delta-regular lambda-expander graph if lambda/Delta is sufficiently small, then the majority model by starting from (1/2-delta)n blue nodes (for an arbitrarily small constant delta>0) results in fully red configuration in sub-logarithmically many rounds. Roughly speaking, this means the majority model is an "efficient" and "fast" density classifier on regular expanders. As a by-product of our results, we show regular Ramanujan graphs are asymptotically optimally immune, that is for an n-node Delta-regular Ramanujan graph if the initial number of blue nodes is s <= beta n, the number of blue nodes in the next round is at most cs/Delta for some constants c,beta>0. This settles an open problem by Peleg [Peleg, 2014].

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • majority model
  • random graph
  • expander graphs
  • dynamic monopoly
  • bootstrap percolation

Metrics

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

Related Versions

References

  1. Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83-96, 1986. Google Scholar
  2. Paul Balister, Béla Bollobás, J Robert Johnson, and Mark Walters. Random majority percolation. Random Structures &Algorithms, 36(3):315-340, 2010. Google Scholar
  3. József Balogh and Gábor Pete. Random disease on the square grid. Random Structures &Algorithms, 13(3-4):409-422, 1998. Google Scholar
  4. József Balogh and Boris G Pittel. Bootstrap percolation on the random regular graph. Random Structures &Algorithms, 30(1-2):257-286, 2007. Google Scholar
  5. Eli Berger. Dynamic monopolies of constant size. Journal of Combinatorial Theory, Series B, 83(2):191-200, 2001. Google Scholar
  6. Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. Rumour spreading and graph conductance. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1657-1663. SIAM, 2010. Google Scholar
  7. Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, and Daniel Reichman. Contagious sets in expanders. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, pages 1953-1987. Society for Industrial and Applied Mathematics, 2015. Google Scholar
  8. Willliam Feller. An introduction to probability theory and its applications, volume 2. John Wiley &Sons, 2008. Google Scholar
  9. Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagli, and Nicola Santoro. Dynamic monopolies in tori. Discrete applied mathematics, 137(2):197-212, 2004. Google Scholar
  10. Luiz Renato Fontes, RH Schonmann, and Vladas Sidoravicius. Stretched exponential fixation in stochastic Ising models at zero temperature. Communications in mathematical physics, 228(3):495-518, 2002. Google Scholar
  11. Nikolaos Fountoulakis, Anna Huber, and Konstantinos Panagiotou. Reliable broadcasting in random networks and the effect of density. In INFOCOM, 2010 Proceedings IEEE, pages 1-9. IEEE, 2010. Google Scholar
  12. Joel Friedman. A proof of alon’s second eigenvalue conjecture. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 720-724. ACM, 2003. Google Scholar
  13. Silvio Frischknecht, Barbara Keller, and Roger Wattenhofer. Convergence in (social) influence networks. In International Symposium on Distributed Computing, pages 433-446. Springer, 2013. Google Scholar
  14. Péter Gács, Georgy L Kurdyumov, and Leonid Anatolevich Levin. One-dimensional uniform arrays that wash out finite islands. Problemy Peredachi Informatsii, 14(3):92-96, 1978. Google Scholar
  15. Bernd Gärtner and Ahad N Zehmakan. (Biased) Majority Rule Cellular Automata. arXiv preprint arXiv:1711.10920, 2017. Google Scholar
  16. Bernd Gärtner and Ahad N Zehmakan. Color war: Cellular automata with majority-rule. In International Conference on Language and Automata Theory and Applications, pages 393-404. Springer, 2017. Google Scholar
  17. Bernd Gärtner and Ahad N Zehmakan. Majority Model on Random Regular Graphs. In Latin American Symposium on Theoretical Informatics, pages 572-583. Springer, 2018. Google Scholar
  18. Eric Goles and J Olivos. Comportement périodique des fonctions à seuil binaires et applications. Discrete Applied Mathematics, 3(2):93-105, 1981. Google Scholar
  19. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. Google Scholar
  20. Svante Janson, Tomasz Luczak, and Andrzej Rucinski. Random graphs, volume 45. John Wiley &Sons, 2011. Google Scholar
  21. Clemens Jeger and Ahad N Zehmakan. Dynamic Monopolies in Reversible Bootstrap Percolation. arXiv preprint arXiv:1805.07392, 2018. Google Scholar
  22. Yashodhan Kanoria, Andrea Montanari, et al. Majority dynamics on trees and the dynamic cavity method. The Annals of Applied Probability, 21(5):1694-1748, 2011. Google Scholar
  23. David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146. ACM, 2003. Google Scholar
  24. Mark Land and Richard K Belew. No perfect two-state cellular automata for density classification exists. Physical review letters, 74(25):5148, 1995. Google Scholar
  25. FWS Lima, AO Sousa, and MA Sumuor. Majority-vote on directed Erdős-Rényi random graphs. Physica A: Statistical Mechanics and its Applications, 387(14):3503-3510, 2008. Google Scholar
  26. Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988. Google Scholar
  27. Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava. Interlacing families iv: Bipartite ramanujan graphs of all sizes. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 1358-1377. IEEE, 2015. Google Scholar
  28. Moshe Morgenstern. Existence and explicit constructions of q+ 1 regular Ramanujan graphs for every prime power q. Journal of Combinatorial Theory, Series B, 62(1):44-62, 1994. Google Scholar
  29. Nabil H Mustafa and Aleksandar Pekec. Majority consensus and the local majority rule. In International Colloquium on Automata, Languages, and Programming, pages 530-542. Springer, 2001. Google Scholar
  30. Nabil H Mustafa and Aleksandar Pekec. Listen to your neighbors: How (not) to reach a consensus. SIAM Journal on Discrete Mathematics, 17(4):634-660, 2004. Google Scholar
  31. David Peleg. Size bounds for dynamic monopolies. Discrete Applied Mathematics, 86(2-3):263-273, 1998. Google Scholar
  32. David Peleg. Local majorities, coalitions and monopolies in graphs: a review. Theoretical Computer Science, 282(2):231-257, 2002. Google Scholar
  33. David Peleg. Immunity against local influence. In Language, Culture, Computation. Computing-Theory and Technology, pages 168-179. Springer, 2014. Google Scholar
  34. Svatopluk Poljak and Daniel Turzík. On pre-periods of discrete influence systems. Discrete Applied Mathematics, 13(1):33-39, 1986. Google Scholar
  35. Grant Schoenebeck and Fang-Yi Yu. Consensus of Interacting Particle Systems on Erdös-Rényi Graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1945-1964. SIAM, 2018. Google Scholar
  36. Roberto H Schonmann. Finite size scaling behavior of a biased majority rule cellular automaton. Physica A: Statistical Mechanics and its Applications, 167(3):619-627, 1990. Google Scholar
  37. Roberto H Schonmann. On the behavior of some cellular automata related to bootstrap percolation. The Annals of Probability, pages 174-193, 1992. Google Scholar
  38. Jia Shao, Shlomo Havlin, and H Eugene Stanley. Dynamic opinion model and invasion percolation. Physical review letters, 103(1):018701, 2009. 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 Imprint Privacy Contact