DROPS

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}
}

Search Results

Documents authored by Karntikoon, Kritkorn

A Connectivity-Sensitive Approach to Consensus Dynamics

Abstract

Cite as

Thanks for your feedback!

Could not send message