Upcoming Talks

Ista white

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

Vienna Probability Seminar

Date: Wednesday, May 10, 2023 16:45 - 18:00
Speaker: Lyuben Lichev (Jean Monnet University)
Location: Mondi 2 (I01.01.008), Central Building
Series: Mathematics and CS Seminar
Host: M. Beiglböck, N. Berestycki, L. Erdös, J. Maas, F. Toninelli, E. Schertzer
Central building mondi1

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.

Qr image
Download ICS Download invitation
Back to eventlist