Document Open Access Logo

A General Stabilization Bound for Influence Propagation in Graphs

Authors Pál András Papp, Roger Wattenhofer

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.90.pdf
  • Filesize: 490 kB
  • 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. A General Stabilization Bound for Influence Propagation in Graphs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 90:1-90:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.90

Abstract

We study the stabilization time of a wide class of processes on graphs, in which each node can only switch its state if it is motivated to do so by at least a (1+λ)/2 fraction of its neighbors, for some 0 < λ < 1. Two examples of such processes are well-studied dynamically changing colorings in graphs: in majority processes, nodes switch to the most frequent color in their neighborhood, while in minority processes, nodes switch to the least frequent color in their neighborhood. We describe a non-elementary function f(λ), and we show that in the sequential model, the worst-case stabilization time of these processes can completely be characterized by f(λ). More precisely, we prove that for any ε > 0, O(n^(1+f(λ)+ε)) is an upper bound on the stabilization time of any proportional majority/minority process, and we also show that there are graph constructions where stabilization indeed takes Ω(n^(1+f(λ)-ε)) steps.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
  • Theory of computation → Distributed computing models
  • Theory of computation → Self-organization
Keywords
  • Minority process
  • Majority process

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. 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
  4. Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. The satisfactory partition problem. Discrete applied mathematics, 154(8):1236-1245, 2006. 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. Olivier Bodini, Thomas Fernique, and Damien Regnault. Crystallization by stochastic flips. In Journal of Physics: Conference Series, volume 226, page 012022. IOP Publishing, 2010. Google Scholar
  7. Olivier Bodini, Thomas Fernique, and Damien Regnault. Stochastic flips on two-letter words. In 2010 Proceedings of the Seventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pages 48-55. SIAM, 2010. Google Scholar
  8. Zhigang Cao and Xiaoguang Yang. The fashion game: Network extension of matching pennies. Theoretical Computer Science, 540:169-181, 2014. Google Scholar
  9. Luca Cardelli and Attila Csikász-Nagy. The cell cycle switch computes approximate majority. Scientific reports, 2:656, 2012. Google Scholar
  10. Ning Chen. On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics, 23(3):1400-1415, 2009. Google Scholar
  11. 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
  12. MohammadAmin Fazli, Mohammad Ghodsi, Jafar Habibi, Pooya Jalaly, Vahab Mirrokni, and Sina Sadeghian. On non-progressive spread of influence through social networks. Theoretical Computer Science, 550:36-50, 2014. 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. 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
  15. 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
  16. Michael U Gerber and Daniel Kobler. Algorithmic approach to the satisfactory graph partitioning problem. European Journal of Operational Research, 125(2):283-291, 2000. Google Scholar
  17. Eric Goles and Jorge Olivos. Periodic behaviour of generalized threshold functions. Discrete Mathematics, 30(2):187-189, 1980. Google Scholar
  18. Mark Granovetter. Threshold models of collective behavior. American Journal of Sociology, 83(6):1420-1443, 1978. Google Scholar
  19. 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
  20. Clemens Jeger and Ahad N Zehmakan. Dynamic monopolies in reversible bootstrap percolation. arXiv preprint arXiv:1805.07392, 2018. Google Scholar
  21. 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
  22. 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
  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. 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
  25. Yuezhou Lv and Thomas Moscibroda. Local information in influence networks. In International Symposium on Distributed Computing, pages 292-308. Springer, 2015. 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 fuer 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 fuer Informatik. Google Scholar
  29. David Peleg. Local majorities, coalitions and monopolies in graphs: a review. Theoretical Computer Science, 282(2):231-257, 2002. 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. Khurram H Shafique and Ronald D Dutton. On satisfactory partitioning of graphs. Congressus Numerantium, pages 183-194, 2002. Google Scholar
  34. Saharon Shelah and Eric C Milner. Graphs with no unfriendly partitions. A tribute to Paul Erdös, pages 373-384, 1990. Google Scholar
  35. Ariel Webster, Bruce Kapron, and Valerie King. Stability of certainty and opinion in influence networks. In Advances in Social Networks Analysis and Mining (ASONAM), 2016 IEEE/ACM International Conference on, pages 1309-1320. IEEE, 2016. Google Scholar
  36. Peter Winkler. Puzzled: Delightful graph theory. Commun. ACM, 51(8):104-104, August 2008. Google Scholar
  37. Ahad N Zehmakan. Target set in threshold models. Acta Mathematica Universitatis Comenianae, 88(3), 2019. Google Scholar
  38. 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