Label propagation on binomial random graphs

MaRDI QIDQ6425736zbMATH OpenFDO

Authors Marcos Kiwi, Lyuben Lichev, D. Mitsche, Paweł Prałat

Publication date 7 February 2023

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05)

Abstract: We study a variant of the widely popular, fast and often used family of community detection procedures referred to as label propagation algorithms. These mechanisms also exhibit many parallels with models of opinion exchange dynamics and consensus mechanisms in distributed computing. Initially, given a network, each vertex starts with a random label in the interval $[0,1]$. Then, 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 investigate the performance of this algorithm on the binomial random graph $mathcalG(n,p)$. We show that for $npge{n}^{5/8+varepsilon}$, the algorithm terminates with a single label a.a.s. (which was previously known only for $npge{n}^{3/4+varepsilon}$). Moreover, we show that if $npgg{n}^{2/3}$, a.a.s. this label is the smallest one, whereas if $n^{5/8+varepsilon}lenpll{n}^{2/3}$, the surviving label is a.a.s. not the smallest one.

This page was built for publication: Label propagation on binomial random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6425736)