1 Search Results for "Karntikoon, Kritkorn"

Document
DOI: 10.4230/LIPIcs.SAND.2023.10
A Connectivity-Sensitive Approach to Consensus Dynamics

Authors: Bernard Chazelle and Kritkorn Karntikoon

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{chazelle_et_al:LIPIcs.SAND.2023.10,
  author =	{Chazelle, Bernard and Karntikoon, Kritkorn},
  title =	{{A Connectivity-Sensitive Approach to Consensus Dynamics}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.10},
  URN =		{urn:nbn:de:0030-drops-179464},
  doi =		{10.4230/LIPIcs.SAND.2023.10},
  annote =	{Keywords: s-energy, dynamic networks, relaxation time, multiagent systems}
}
  • Refine by Type
  • 1 Document/PDF

  • Refine by Publication Year
  • 1 2023

  • Refine by Author
  • 1 Chazelle, Bernard
  • 1 Karntikoon, Kritkorn

  • Refine by Series/Journal
  • 1 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Theory of computation → Dynamic graph algorithms

  • Refine by Keyword
  • 1 dynamic networks
  • 1 multiagent systems
  • 1 relaxation time
  • 1 s-energy

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact