License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.83
URN: urn:nbn:de:0030-drops-145239
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14523/
Go to the corresponding LIPIcs Volume Portal

Papp, Pál András ; Wattenhofer, Roger

Stabilization Bounds for Influence Propagation from a Random Initial State

pdf-format:
LIPIcs-MFCS-2021-83.pdf (0.7 MB)

Abstract

We study the stabilization time of two common types of influence propagation. In majority processes, nodes in a graph want to switch to the most frequent state in their neighborhood, while in minority processes, nodes want to switch to the least frequent state in their neighborhood. We consider the sequential model of these processes, and assume that every node starts out from a uniform random state.
We first show that if nodes change their state for any small improvement in the process, then stabilization can last for up to Θ(n²) steps in both cases. Furthermore, we also study the proportional switching case, when nodes only decide to change their state if they are in conflict with a (1+λ)/2 fraction of their neighbors, for some parameter λ ∈ (0,1). In this case, we show that if λ < 1/3, then there is a construction where stabilization can indeed last for Ω(n^{1+c}) steps for some constant c > 0. On the other hand, if λ > 1/2, we prove that the stabilization time of the processes is upper-bounded by O(n ⋅ log n).

BibTeX - Entry

@InProceedings{papp_et_al:LIPIcs.MFCS.2021.83,
  author =	{Papp, P\'{a}l Andr\'{a}s and Wattenhofer, Roger},
  title =	{{Stabilization Bounds for Influence Propagation from a Random Initial State}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{83:1--83:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14523},
  URN =		{urn:nbn:de:0030-drops-145239},
  doi =		{10.4230/LIPIcs.MFCS.2021.83},
  annote =	{Keywords: Majority process, Minority process, Stabilization time, Random initialization, Asynchronous model}
}

Keywords: Majority process, Minority process, Stabilization time, Random initialization, Asynchronous model
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI