Convergence in (Social) Influence Networks

Silvio Frischknecht, Barbara Keller, and Roger Wattenhofer

Abstract:
We study the convergence of influence networks, where each node changes its state according to the majority of its neighbors. Our main result is a new bound on the convergence time in the synchronous model, solving the classic “Democrats and Republicans” problem. Furthermore, we give a bound for the sequential model in which the sequence of steps is given by an adversary and a bound for the sequential model in which the sequence of steps is given by a benevolent process.

Guest: Barbara Keller

Host: Shantanu Das