Document Open Access Logo

Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion

Authors Tung Mai, Ioannis Panageas, Vijay V. Vazirani

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.140.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Tung Mai
Ioannis Panageas
Vijay V. Vazirani

Cite As Get BibTex

Tung Mai, Ioannis Panageas, and Vijay V. Vazirani. Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 140:1-140:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.140

Abstract

Inspired by the work of Kempe et al. [Kempe, Kleinberg, Oren, Slivkins, EC 2013], we introduce and analyze a model on opinion formation; the update rule of our dynamics is a simplified version of that of [Kempe, Kleinberg, Oren, Slivkins, EC 2013]. We assume that the population is partitioned into types whose interaction pattern is specified by a graph. Interaction leads to population mass moving from types of smaller mass to those of bigger mass. We show that starting uniformly at random over all population vectors on the simplex, our dynamics converges point-wise with probability one to an independent set. This settles an open problem of [Kempe, Kleinberg, Oren, Slivkins, EC 2013], as applicable to our dynamics. We believe that our techniques can be used to settle the open problem for the Kempe et al. dynamics as well.

Next, we extend the model of Kempe et al. by introducing the notion of birth and death of types, with the interaction graph evolving appropriately. Birth of types is determined by a Bernoulli process and types die when their population mass is less than epsilon (a parameter). We show that if the births are infrequent, then there are long periods of "stability" in which there is no population mass that moves. Finally we show that even if births are frequent and "stability" is not attained, the total number of types does not explode: it remains logarithmic in 1/epsilon.

Subject Classification

Keywords
  • Opinion Dynamics
  • Convergence
  • Jacobian
  • Center-stable Manifold

Metrics

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

References

  1. A. Anagnostopoulos, R. Kumar, and M. Mahdian. Influence and correlation in social networks. 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 7-15, 2008. Google Scholar
  2. S. Aral, L. Muchnik, and A. Sundararajan. Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks. Proceedings of the National Academy of Sciences (PNAS), 2009. Google Scholar
  3. S. Arora, Y. Rabani, and U. Vazirani. Simulating quadratic dynamical systems is pspace-complete (preliminary version). Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing (STOC), pages 459-467, 1994. Google Scholar
  4. R. Axelrod. The dissemination of culture. Journal of Conflict Resolution, pages 203-226, 1997. Google Scholar
  5. E. Bakshy, I. Rosenn, C. A. Marlow, and L. A. Adamic. The role of social networks in information diffusion. 21st International World Wide Web Conference, pages 203-226, 2012. Google Scholar
  6. A. Bhattacharyya and K. Shiragur. How friends and non-determinism affect opinion dynamics. In 54th IEEE Conference on Decision and Control (CDC), pages 6466-6471, 2015. Google Scholar
  7. J. M. Cohen. Sources of peer group homogeneity. Sociology in Education, pages 227-241, 1977. Google Scholar
  8. G. Deffuant, D. Neau, F. Amblard, and G. Weisbuch. Mixing beliefs among interacting agents. Journal of Conflict Resolution, pages 87-98, 2000. Google Scholar
  9. M. Feldman, N. Immorlica, B. Lucier, and S. M. Weinberg. Reaching consensus via non-bayesian asynchronous learning in social networks. In APPROX/RANDOM, pages 192-208, 2014. Google Scholar
  10. S. Galam. Sociophysics: a review of Galam models. International Journal of Modern Physics C, 2008. Google Scholar
  11. R. Hegselmann and U. Krause. Opinion dynamics and bounded confidence: models, analysis and simulation. Journal of Artificial Societies and Social Simulation, 2002. Google Scholar
  12. R. A. Holley and T. M. Liggett. Ergodic theorems for weakly interacting infinite systems and the voter model. Annals of Probability, 1975. Google Scholar
  13. M. O. Jackson. Social and economic networks. Princeton University Press, 2008. Google Scholar
  14. D. B. Kandel. Homophily, selection, and socialization in adolescent friendships. American Journal of Sociology, pages 427-436, 1978. Google Scholar
  15. D. Kempe, J. M. Kleinberg, S. Oren, and A. Slivkins. Selection and influence in cultural dynamics. In ACM Conference on Electronic Commerce (EC), pages 585-586, 2013. Google Scholar
  16. G. E. Kreindlera and H. P. Young. The spread of innovations in social networks. Proceedings of the National Academy of Sciences (PNAS), 2014. Google Scholar
  17. T. LaFond and J. Neville. Randomization tests for distinguishing social influence and homophily effects. 19th International World Wide Web Conference, pages 601-610, 2010. Google Scholar
  18. J. D. Lee, M. Simchowitz, M. I. Jordan, and B. Recht. Gradient descent only converges to minimizers. Conference on Learning Theory (COLT), 2016. Google Scholar
  19. R. Mehta, I. Panageas, and G. Piliouras. Natural selection as an inhibitor of genetic diversity: Multiplicative weights updates algorithm and a conjecture of haploid genetics. Innovations in Theoretical Computer Science (ITCS), 2015. Google Scholar
  20. R. Mehta, I. Panageas, G. Piliouras, P. Tetali, and V. V. Vazirani. Mutation, sexual reproduction and survival in dynamic environments. Innovations in Theoretical Computer Science (ITCS), 2017. Google Scholar
  21. A. Montanari and A. Saberi. The spread of innovations in social networks. Proceedings of the National Academy of Sciences (PNAS), 2010. Google Scholar
  22. E. Mossel, J. Neeman, and O. Tamuz. Majority dynamics and aggregation of information in social networks. In Autonomous Agents and Multi-Agent Systems (AAMAS), 2013. Google Scholar
  23. I. Panageas and G. Piliouras. Average case performance of replicator dynamics in potential games via computing regions of attraction. ACM Conference on Economics and Computation (EC), 2016. Google Scholar
  24. I. Panageas and G. Piliouras. Gradient descent only converges to minimizers: Non-isolated critical points and invariant regions. Innovations in Theoretical Computer Science (ITCS), 2017. Google Scholar
  25. L. Perko. Differential Equations and Dynamical Systems. Springer, 3nd. edition, 1991. Google Scholar
  26. K. Poole and H. Rosenthall. Patterns of congressional voting. American Journal of Political Science, pages 228-278, 1978. Google Scholar
  27. Y. Rabinovich, A. Sinclair, and A. Widgerson. Quadratic dynamical systems. Proc 23rd IEEE Symp Foundations of Computer Science, pages 304-313, 1992. Google Scholar
  28. M. Shub. Global Stability of Dynamical Systems. Springer-Verlag, 1987. Google Scholar
  29. A. Sîrbu, V. Loreto, V. Domenico P. Servedio, and F. Tria. Opinion dynamics: models, extensions and external effects. CoRR, abs/1605.06326, 2016. 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