@inproceedings{f4473bca648b4b21b4e5ec9a23ba523f,
title = "A Connectivity-Sensitive Approach to Consensus Dynamics",
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.",
keywords = "dynamic networks, multiagent systems, relaxation time, s-energy",
author = "Bernard Chazelle and Kritkorn Karntikoon",
note = "Publisher Copyright: {\textcopyright} Bernard Chazelle and Kritkorn Karntikoon; licensed under Creative Commons License CC-BY 4.0.; 2nd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2023 ; Conference date: 19-06-2023 Through 21-06-2023",
year = "2023",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.SAND.2023.10",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "David Doty and Paul Spirakis",
booktitle = "2nd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2023",
address = "Germany",
}