2026-07-23T07:58:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14523 2024-03-06T10:54:14Z ddc:004 open_access

Stabilization Bounds for Influence Propagation from a Random Initial State Papp, Pál András Wattenhofer, Roger Majority process Minority process Stabilization time Random initialization Asynchronous model 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pál András Papp and Roger Wattenhofer 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.83 urn:nbn:de:0030-drops-145239 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.83 eng https://creativecommons.org/licenses/by/4.0/legalcode