Label propagation on Erdös-Rényi random graphs

Vienna Probability Seminar

In this talk, we will consider one instance of the popular class of unsupervised learning algorithms for finding communities in complex networks called label propagation algorithms. It is described as follows: we are given a network on n vertices carring labels 1,2,...,n. In each round of the algorithm, every vertex switches its label to the majority label in its neighborhood (including its own label). At the first round, ties are broken towards smaller labels, while at each of the next rounds, ties are broken uniformly at random.

We will focus on the action of the algorithm on the Erdös-Rényi random graph G(n,p). More precisely, we will see that for all sufficiently large p = p(n), the algorithm typically terminates with a unique label as n →∞, and will try to understand how this label behaves as a function of p. In particular, we will see why there is a phase transition around p = n^−1/3. The talk is based on a joint work with Marcos Kiwi, Dieter Mitsche and Pawel Pralat.