Document Open Access Logo

A Connectivity-Sensitive Approach to Consensus Dynamics

Authors Bernard Chazelle , Kritkorn Karntikoon

PDF
Thumbnail PDF

File

LIPIcs.SAND.2023.10.pdf
  • Filesize: 0.78 MB
  • 17 pages

Document Identifiers

Author Details

Bernard Chazelle
  • Department of Computer Science, Princeton University, NJ, USA
Kritkorn Karntikoon
  • Department of Computer Science, Princeton University, NJ, USA

Funding

This work was supported in part by NSF grant CCF-2006125.

Cite AsGet BibTex

Bernard Chazelle and Kritkorn Karntikoon. A Connectivity-Sensitive Approach to Consensus Dynamics. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SAND.2023.10

Abstract

The paper resolves a long-standing open question in network dynamics. Averaging-based consensus has long been known to exhibit an exponential gap in relaxation time between the connected and disconnected cases, but a satisfactory explanation has remained elusive. We provide one by deriving nearly tight bounds on the s-energy of disconnected systems. This in turn allows us to relate the convergence rate of consensus dynamics to the number of connected components. We apply our results to opinion formation in social networks and provide a theoretical validation of the concept of an Overton window as an attracting manifold of "viable" opinions.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
  • Theory of computation → Dynamic graph algorithms
Keywords
  • s-energy
  • dynamic networks
  • relaxation time
  • multiagent systems

Metrics

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

References

  1. Olle Abrahamsson, Danyo Danev, and Erik G. Larsson. Opinion dynamics with random actions and a stubborn agent. In Michael B. Matthews, editor, 53rd Asilomar Conference on Signals, Systems, and Computers, ACSCC 2019, Pacific Grove, CA, USA, November 3-6, 2019, pages 1486-1490. IEEE, 2019. URL: https://doi.org/10.1109/IEEECONF44664.2019.9048901.
  2. Daron Acemoglu, Asuman E. Ozdaglar, and Ali ParandehGheibi. Spread of (mis)information in social networks. Games Econ. Behav., 70(2):194-227, 2010. URL: https://doi.org/10.1016/j.geb.2010.01.005.
  3. Noga Alon. Eigenvalues and expanders. Comb., 6(2):83-96, 1986. URL: https://doi.org/10.1007/BF02579166.
  4. Emmi Bevensee and Alexander Reid Ross. The alt-right and global information warfare. In Naoki Abe, Huan Liu, Calton Pu, Xiaohua Hu, Nesreen K. Ahmed, Mu Qiao, Yang Song, Donald Kossmann, Bing Liu, Kisung Lee, Jiliang Tang, Jingrui He, and Jeffrey S. Saltz, editors, IEEE International Conference on Big Data (IEEE BigData 2018), Seattle, WA, USA, December 10-13, 2018, pages 4393-4402. IEEE, 2018. URL: https://doi.org/10.1109/BigData.2018.8622270.
  5. Vincent D. Blondel, Julien M. Hendrickx, and John N. Tsitsiklis. On krause’s multi-agent consensus model with state-dependent connectivity. IEEE Trans. Autom. Control., 54(11):2586-2597, 2009. URL: https://doi.org/10.1109/TAC.2009.2031211.
  6. George-Daniel Bobric. The overton window: A tool for information warfare. In ICCWS 2021 16th International Conference on Cyber Warfare and Security, pages 20-27. Academic Conferences Limited, 2021. Google Scholar
  7. Francesco Bullo, Jorge Cortés, and Sonia Martinez. Distributed control of robotic networks: a mathematical approach to motion coordination algorithms, volume 27. Princeton University Press, 2009. Google Scholar
  8. Ming Cao, A. Stephen Morse, and Brian D. O. Anderson. Reaching a consensus in a dynamically changing environment: Convergence rates, measurement delays, and asynchronous events. SIAM J. Control. Optim., 47(2):601-623, 2008. URL: https://doi.org/10.1137/060657029.
  9. Claudio Castellano, Santo Fortunato, and Vittorio Loreto. Statistical physics of social dynamics. Reviews of modern physics, 81(2):591-646, 2009. Google Scholar
  10. Bernadette Charron-Bost and Patrick Lambein-Monette. Computing outside the box: Average consensus over dynamic networks. In James Aspnes and Othon Michail, editors, 1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022, March 28-30, 2022, Virtual Conference, volume 221 of LIPIcs, pages 10:1-10:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.SAND.2022.10.
  11. Samprit Chatterjee and Eugene Seneta. Towards consensus: Some convergence theorems on repeated averaging. Journal of Applied Probability, 14(1):89-97, 1977. Google Scholar
  12. Bernard Chazelle. The total s-energy of a multiagent system. SIAM J. Control. Optim., 49(4):1680-1706, 2011. URL: https://doi.org/10.1137/100791671.
  13. Bernard Chazelle. A sharp bound on the s-energy and its applications to averaging systems. IEEE Trans. Autom. Control., 64(10):4385-4390, 2019. URL: https://doi.org/10.1109/TAC.2019.2899509.
  14. Bernard Chazelle. On the periodicity of random walks in dynamic networks. IEEE Trans. Netw. Sci. Eng., 7(3):1337-1343, 2020. URL: https://doi.org/10.1109/TNSE.2019.2924921.
  15. Bernard Chazelle and Kritkorn Karntikoon. Quick relaxation in collective motion. In 61st IEEE Conference on Decision and Control, CDC 2022, Cancun, Mexico, December 6-9, 2022, pages 6472-6477. IEEE, 2022. URL: https://doi.org/10.1109/CDC51059.2022.9992475.
  16. Uthsav Chitra and Christopher Musco. Analyzing the impact of filter bubbles on social network polarization. In James Caverlee, Xia (Ben) Hu, Mounia Lalmas, and Wei Wang, editors, WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining, Houston, TX, USA, February 3-7, 2020, pages 115-123. ACM, 2020. URL: https://doi.org/10.1145/3336191.3371825.
  17. Étienne Coulouma, Emmanuel Godard, and Joseph G. Peters. A characterization of oblivious message adversaries for which consensus is solvable. Theor. Comput. Sci., 584:80-90, 2015. URL: https://doi.org/10.1016/j.tcs.2015.01.024.
  18. Felipe Cucker and Steve Smale. Emergent behavior in flocks. IEEE Trans. Autom. Control., 52(5):852-862, 2007. URL: https://doi.org/10.1109/TAC.2007.895842.
  19. CIH David Dyjack DrPH. The overton window. Journal of Environmental Health, 82(7):54-53, 2020. Google Scholar
  20. Guillaume Deffuant, David Neau, Frédéric Amblard, and Gérard Weisbuch. Mixing beliefs among interacting agents. Adv. Complex Syst., 3(1-4):87-98, 2000. URL: https://doi.org/10.1142/S0219525900000078.
  21. Morris H DeGroot. Reaching a consensus. Journal of the American Statistical association, 69(345):118-121, 1974. Google Scholar
  22. Matthew G Earl and Steven H Strogatz. Synchronization in oscillator networks with delayed coupling: A stability criterion. Physical Review E, 67(3):036204, 2003. Google Scholar
  23. Antoine El-Hayek, Monika Henzinger, and Stefan Schmid. Brief announcement: Broadcasting time in dynamic rooted trees is linear. In Alessia Milani and Philipp Woelfel, editors, PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25-29, 2022, pages 54-56. ACM, 2022. URL: https://doi.org/10.1145/3519270.3538460.
  24. Antoine El-Hayek, Monika Henzinger, and Stefan Schmid. Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 47:1-47:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPIcs.ITCS.2023.47.
  25. Antoine El-Hayek, Monika Henzinger, and Stefan Schmid. Time complexity of broadcast and consensus for randomized oblivious message adversaries. CoRR, abs/2302.11988, 2023. URL: https://doi.org/10.48550/arXiv.2302.11988.
  26. Fabio Fagnani and Paolo Frasca. Introduction to averaging dynamics over networks. Springer, 2018. Google Scholar
  27. Denis N Fedyanin. On control for reaching a consensus in multiagent systems with bounded opinion updates. In 2021 14th International Conference Management of large-scale system development (MLSD), pages 1-5. IEEE, 2021. Google Scholar
  28. Noah E Friedkin and Eugene C Johnsen. Social influence and opinions. Journal of Mathematical Sociology, 15(3-4):193-206, 1990. Google Scholar
  29. Jason Gaitonde, Jon M. Kleinberg, and Éva Tardos. Polarization in geometric opinion dynamics. In Péter Biró, Shuchi Chawla, and Federico Echenique, editors, EC '21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, pages 499-519. ACM, 2021. URL: https://doi.org/10.1145/3465456.3467633.
  30. Javad Ghaderi and R. Srikant. Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate. Autom., 50(12):3209-3215, 2014. URL: https://doi.org/10.1016/j.automatica.2014.10.034.
  31. Rainer Hegselmann and Ulrich Krause. Opinion dynamics and bounded confidence: models, analysis and simulation. J. Artif. Soc. Soc. Simul., 5(3), 2002. URL: http://jasss.soc.surrey.ac.uk/5/3/2.html.
  32. Julien Hendrickx and Vincent Blondel. Convergence of different linear and non-linear vicsek models. In MTNS 2006, pages 1229-1240, 2006. Google Scholar
  33. Julien M. Hendrickx and John N. Tsitsiklis. Convergence of type-symmetric and cut-balanced consensus seeking systems. IEEE Trans. Autom. Control., 58(1):214-218, 2013. URL: https://doi.org/10.1109/TAC.2012.2203214.
  34. Ali Jadbabaie, Jie Lin, and A. Stephen Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Autom. Control., 48(6):988-1001, 2003. URL: https://doi.org/10.1109/TAC.2003.812781.
  35. Jing Jiang, Christo Wilson, Xiao Wang, Wenpeng Sha, Peng Huang, Yafei Dai, and Ben Y. Zhao. Understanding latent interactions in online social networks. ACM Trans. Web, 7(4):18:1-18:39, 2013. URL: https://doi.org/10.1145/2517040.
  36. Fabian Kuhn, Nancy A. Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 513-522. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806760.
  37. Fadel Lashhab. Building Efficiency Control; Dynamic Consensus Networks. LAP Lambert Academic Publishing, 2018. Google Scholar
  38. Kevin Lewis, Marco Gonzalez, and Jason Kaufman. Social selection and peer influence in an online social network. Proceedings of the National Academy of Sciences, 109(1):68-72, 2012. Google Scholar
  39. Jan Lorenz. A stabilization theorem for dynamics of continuous opinions. Physica A: Statistical Mechanics and its Applications, 355(1):217-223, 2005. Google Scholar
  40. Jan Lorenz. Heterogeneous bounds of confidence: Meet, discuss and find consensus! Complex., 15(4):43-52, 2010. URL: https://doi.org/10.1002/cplx.20295.
  41. Anahita Mirtabatabaei and Francesco Bullo. Opinion dynamics in heterogeneous networks: Convergence conjectures and theorems. SIAM J. Control. Optim., 50(5):2763-2785, 2012. URL: https://doi.org/10.1137/11082751X.
  42. Ciamac Cyrus Moallemi and Benjamin Van Roy. Consensus propagation. IEEE Transactions on Information Theory, 52(11):4753-4766, 2006. Google Scholar
  43. Mauro Mobilia. Does a single zealot affect an infinite group of voters? Physical review letters, 91(2):028701, 2003. Google Scholar
  44. Mauro Mobilia, Anna Petersen, and Sidney Redner. On the role of zealotry in the voter model. Journal of Statistical Mechanics: Theory and Experiment, 2007(08):P08029, 2007. Google Scholar
  45. Luc Moreau. Stability of multiagent systems with time-dependent communication links. IEEE Trans. Autom. Control., 50(2):169-182, 2005. URL: https://doi.org/10.1109/TAC.2004.841888.
  46. Daniel J Morgan. The overton window and a less dogmatic approach to antibiotics. Clinical Infectious Diseases, 70(11):2439-2441, 2020. Google Scholar
  47. Angelia Nedic, Alex Olshevsky, Asuman E. Ozdaglar, and John N. Tsitsiklis. On distributed averaging algorithms and quantization effects. IEEE Trans. Autom. Control., 54(11):2506-2517, 2009. URL: https://doi.org/10.1109/TAC.2009.2031203.
  48. Angelia Nedich. Convergence rate of distributed averaging dynamics and optimization in networks. Found. Trends Syst. Control., 2(1):1-100, 2015. URL: https://doi.org/10.1561/2600000004.
  49. Tien T. Nguyen, Pik-Mai Hui, F. Maxwell Harper, Loren G. Terveen, and Joseph A. Konstan. Exploring the filter bubble: the effect of using recommender systems on content diversity. In Chin-Wan Chung, Andrei Z. Broder, Kyuseok Shim, and Torsten Suel, editors, 23rd International World Wide Web Conference, WWW '14, Seoul, Republic of Korea, April 7-11, 2014, pages 677-686. ACM, 2014. URL: https://doi.org/10.1145/2566486.2568012.
  50. Alex Olshevsky and John N. Tsitsiklis. Convergence speed in distributed consensus and averaging. SIAM J. Control. Optim., 48(1):33-55, 2009. URL: https://doi.org/10.1137/060678324.
  51. Alex Olshevsky and John N. Tsitsiklis. Degree fluctuations and the convergence time of consensus algorithms. IEEE Trans. Autom. Control., 58(10):2626-2631, 2013. URL: https://doi.org/10.1109/TAC.2013.2257969.
  52. Alistair Sinclair. Algorithms for random generation and counting - A Markov chain approach. Progress in theoretical computer science. Birkhäuser, 1993. Google Scholar
  53. Ye Tian and Long Wang. Opinion dynamics in social networks with stubborn agents: An issue-based perspective. Autom., 96:213-223, 2018. URL: https://doi.org/10.1016/j.automatica.2018.06.041.
  54. John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions on automatic control, 31(9):803-812, 1986. Google Scholar
  55. Tamás Vicsek, András Czirók, Eshel Ben-Jacob, Inon Cohen, and Ofer Shochet. Novel type of phase transition in a system of self-driven particles. Physical review letters, 75(6):1226-1229, 1995. Google Scholar
  56. Bimal Viswanath, Alan Mislove, Meeyoung Cha, and P. Krishna Gummadi. On the evolution of user interaction in facebook. In Jon Crowcroft and Balachander Krishnamurthy, editors, Proceedings of the 2nd ACM Workshop on Online Social Networks, WOSN 2009, Barcelona, Spain, August 17, 2009, pages 37-42. ACM, 2009. URL: https://doi.org/10.1145/1592665.1592675.
  57. Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, and Ulrich Schmid. The time complexity of consensus under oblivious message adversaries. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 100:1-100:28. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPIcs.ITCS.2023.100.
  58. Nicholas C Wormald et al. Models of random regular graphs. London Mathematical Society Lecture Note Series, pages 239-298, 1999. Google Scholar
  59. Ercan Yildiz, Daron Acemoglu, Asuman E Ozdaglar, Amin Saberi, and Anna Scaglione. Discrete opinion dynamics with stubborn agents. Available at SSRN 1744113, 2011. Google Scholar
  60. Mehmet Ercan Yildiz, Asuman E. Ozdaglar, Daron Acemoglu, Amin Saberi, and Anna Scaglione. Binary opinion dynamics with stubborn agents. ACM Trans. Economics and Comput., 1(4):19:1-19:30, 2013. URL: https://doi.org/10.1145/2538508.
  61. Reza Zafarani, Mohammad Ali Abbasi, and Huan Liu. Social Media Mining: An Introduction. Cambridge University Press, 2014. URL: https://doi.org/10.1017/CBO9781139088510.
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