Document Open Access Logo

Stabilization Bounds for Influence Propagation from a Random Initial State

Authors Pál András Papp, Roger Wattenhofer

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.83.pdf
  • Filesize: 0.69 MB
  • 15 pages

Document Identifiers

Author Details

Pál András Papp
  • ETH Zürich, Switzerland
Roger Wattenhofer
  • ETH Zürich, Switzerland

Cite As Get BibTex

Pál András Papp and Roger Wattenhofer. Stabilization Bounds for Influence Propagation from a Random Initial State. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 83:1-83:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.83

Abstract

We study the stabilization time of two common types of influence propagation. In majority processes, nodes in a graph want to switch to the most frequent state in their neighborhood, while in minority processes, nodes want to switch to the least frequent state in their neighborhood. We consider the sequential model of these processes, and assume that every node starts out from a uniform random state.
We first show that if nodes change their state for any small improvement in the process, then stabilization can last for up to Θ(n²) steps in both cases. Furthermore, we also study the proportional switching case, when nodes only decide to change their state if they are in conflict with a (1+λ)/2 fraction of their neighbors, for some parameter λ ∈ (0,1). In this case, we show that if λ < 1/3, then there is a construction where stabilization can indeed last for Ω(n^{1+c}) steps for some constant c > 0. On the other hand, if λ > 1/2, we prove that the stabilization time of the processes is upper-bounded by O(n ⋅ log n).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
  • Theory of computation → Distributed computing models
  • Theory of computation → Self-organization
Keywords
  • Majority process
  • Minority process
  • Stabilization time
  • Random initialization
  • Asynchronous model

Metrics

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

Related Versions

References

  1. Victor Amelkin, Francesco Bullo, and Ambuj K Singh. Polar opinion dynamics in social networks. IEEE Transactions on Automatic Control, 62(11):5650-5665, 2017. Google Scholar
  2. Vincenzo Auletta, Ioannis Caragiannis, Diodato Ferraioli, Clemente Galdi, and Giuseppe Persiano. Generalized discrete preference games. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI’16, page 53–59. AAAI Press, 2016. Google Scholar
  3. Vincenzo Auletta, Diodato Ferraioli, and Gianluigi Greco. On the complexity of reasoning about opinion diffusion under majority dynamics. Artificial Intelligence, 284:103288, 2020. Google Scholar
  4. Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. Complexity and approximation of satisfactory partition problems. In International Computing and Combinatorics Conference, pages 829-838. Springer, 2005. Google Scholar
  5. Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. Satisfactory graph partition, variants, and generalizations. European Journal of Operational Research, 206(2):271-280, 2010. Google Scholar
  6. Zhigang Cao and Xiaoguang Yang. The fashion game: Network extension of matching pennies. Theoretical Computer Science, 540:169-181, 2014. Google Scholar
  7. Luca Cardelli and Attila Csikász-Nagy. The cell cycle switch computes approximate majority. Scientific reports, 2:656, 2012. Google Scholar
  8. Carmen C Centeno, Mitre C Dourado, Lucia Draque Penso, Dieter Rautenbach, and Jayme L Szwarcfiter. Irreversible conversion of graphs. Theoretical Computer Science, 412(29):3693-3700, 2011. Google Scholar
  9. Jacques Demongeot, Julio Aracena, Florence Thuderoz, Thierry-Pascal Baum, and Olivier Cohen. Genetic regulation networks: circuits, regulons and attractors. Comptes Rendus Biologies, 326(2):171-188, 2003. Google Scholar
  10. Michal Feldman, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg. Reaching Consensus via Non-Bayesian Asynchronous Learning in Social Networks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), volume 28 of Leibniz International Proceedings in Informatics (LIPIcs), pages 192-208, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. Google Scholar
  11. Françoise Fogelman, Eric Goles, and Gérard Weisbuch. Transient length in sequential iteration of threshold functions. Discrete Applied Mathematics, 6(1):95-98, 1983. Google Scholar
  12. 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
  13. 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
  14. 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
  15. Eric Goles and Jorge Olivos. Periodic behaviour of generalized threshold functions. Discrete Mathematics, 30(2):187-189, 1980. Google Scholar
  16. Mark Granovetter. Threshold models of collective behavior. American Journal of Sociology, 83(6):1420-1443, 1978. Google Scholar
  17. Sandra M Hedetniemi, Stephen T Hedetniemi, KE Kennedy, and Alice A Mcrae. Self-stabilizing algorithms for unfriendly partitions into two disjoint dominating sets. Parallel Processing Letters, 23(01):1350001, 2013. Google Scholar
  18. 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), 2016. Google Scholar
  19. Barbara Keller, David Peleg, and Roger Wattenhofer. How even tiny influence can have a big impact! In International Conference on Fun with Algorithms, pages 252-263. Springer, 2014. Google Scholar
  20. 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
  21. Jeremy Kun, Brian Powers, and Lev Reyzin. Anti-coordination games and stable graph colorings. In International Symposium on Algorithmic Game Theory, pages 122-133. Springer, 2013. Google Scholar
  22. Thomas M Liggett. Stochastic interacting systems: contact, voter and exclusion processes, volume 324. Springer Science & Business Media, 2013. Google Scholar
  23. Barry M McCoy and Tai Tsun Wu. The two-dimensional Ising model. Courier Corporation, 2014. Google Scholar
  24. Elchanan Mossel, Joe Neeman, and Omer Tamuz. Majority dynamics and aggregation of information in social networks. Autonomous Agents and Multi-Agent Systems, 28(3):408-429, 2014. Google Scholar
  25. Arpan Mukhopadhyay, Ravi R Mazumdar, and Rahul Roy. Voter and majority dynamics with biased and stubborn agents. Journal of Statistical Physics, 181(4):1239-1265, 2020. Google Scholar
  26. Ahad N Zehmakan. Opinion forming in Erdös-Rényi random graph and expanders. In 29th International Symposium on Algorithms and Computations. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, 2018. Google Scholar
  27. Pál András Papp and Roger Wattenhofer. Stabilization Time in Minority Processes. In 30th International Symposium on Algorithms and Computation (ISAAC 2019), volume 149 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1-43:19, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. Google Scholar
  28. Pál András Papp and Roger Wattenhofer. Stabilization Time in Weighted Minority Processes. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1-54:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. Google Scholar
  29. Pál András Papp and Roger Wattenhofer. A General Stabilization Bound for Influence Propagation in Graphs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 90:1-90:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. Google Scholar
  30. Damien Regnault, Nicolas Schabanel, and Éric Thierry. Progresses in the analysis of stochastic 2d cellular automata: A study of asynchronous 2d minority. In Luděk Kučera and Antonín Kučera, editors, Mathematical Foundations of Computer Science 2007, pages 320-332. Springer Berlin Heidelberg, 2007. Google Scholar
  31. Damien Regnault, Nicolas Schabanel, and Éric Thierry. On the analysis of “simple” 2d stochastic cellular automata. In International Conference on Language and Automata Theory and Applications, pages 452-463. Springer, 2008. Google Scholar
  32. Jean-Baptiste Rouquier, Damien Regnault, and Éric Thierry. Stochastic minority on graphs. Theoretical Computer Science, 412(30):3947-3963, 2011. Google Scholar
  33. 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
  34. Ahad N Zehmakan. Target set in threshold models. Acta Mathematica Universitatis Comenianae, 88(3), 2019. Google Scholar
  35. Ahad N Zehmakan. Tight bounds on the minimum size of a dynamic monopoly. In International Conference on Language and Automata Theory and Applications, pages 381-393. Springer, 2019. 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