08/07/2020

A General Stabilization Bound for Influence Propagation in Graphs

Pál András Papp, Roger Wattenhofer

Keywords: Minority process, Majority process

Abstract: We study the stabilization time of a wide class of processes on graphs, in which each node can only switch its state if it is motivated to do so by at least a (1+λ)/2 fraction of its neighbors, for some 0 < λ < 1. Two examples of such processes are well-studied dynamically changing colorings in graphs: in majority processes, nodes switch to the most frequent color in their neighborhood, while in minority processes, nodes switch to the least frequent color in their neighborhood. We describe a non-elementary function f(λ), and we show that in the sequential model, the worst-case stabilization time of these processes can completely be characterized by f(λ). More precisely, we prove that for any ε > 0, O(n^(1+f(λ)+ε)) is an upper bound on the stabilization time of any proportional majority/minority process, and we also show that there are graph constructions where stabilization indeed takes Ω(n^(1+f(λ)-ε)) steps.

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at ICALP 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers