← 研踪 PaperTrailarXiv:2302.03569 · v6
Consensus in label propagation on binomial random graphs
首次提交 2023-02-08 00:30
版本更新 2026-11-03 00:12
雷达观测 2026-11-04 23:41
摘要
Understanding how local update rules amplify small random fluctuations into global consensus is a central challenge in the study of network dynamics and decentralized processes. A prominent family of examples is given by label propagation algorithms, widely used heuristics for community detection whose analysis is complicated by the strong dependencies created as the process evolves. Despite the simplicity and practical success of this class of algorithms, a rigorous understanding of their convergence remains limited. In this paper, we study a specific variant, which we refer to as LPA, on the binomial random graph $\mathcal{G}(n,p)$ - a canonical null model with no planted community structure. We show that LPA reaches consensus asymptotically almost surely when $np\ge n^{5/8+\varepsilon}$ for any fixed $\varepsilon>0$, thus breaking the current best $n^{3/4+\varepsilon}$ analytical barrier. More remarkably, we uncover a phase transition governing \emph{which} label survives: when $np\gg n^{2/3}$, the surviving label is asymptotically almost surely the smallest initial label, whereas for $n^{5/8+\varepsilon}\le np\ll n^{2/3}$, the surviving label is asymptotically almost surely not the smallest one. We further show that, in the critical window $np=Θ(n^{2/3})$, both outcomes have probability $Θ(1).$ Our analysis has several important ingredients. We analyze a staged exploration that progressively reveals information about the random graph while preserving some randomness needed to track the amplification of label advantages across multiple rounds. This analysis is complemented by novel coupling and decoupling arguments that control the dependencies inherent to the process. Along the way, we establish a monotonicity result for competing binomial random variables that we believe is of independent interest.
作者备注：68 pages; Extended abstract was accepted at SODA 2027
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v6 · 2026-11-03 00:12 · 最新观测版本
Consensus in label propagation on binomial random graphs
Understanding how local update rules amplify small random fluctuations into global consensus is a central challenge in the study of network dynamics and decentralized processes. A prominent family of examples is given by label propagation algorithms, widely used heuristics for community detection whose analysis is complicated by the strong dependencies created as the process evolves. Despite the simplicity and practical success of this class of algorithms, a rigorous understanding of their convergence remains limited. In this paper, we study a specific variant, which we refer to as LPA, on the binomial random graph $\mathcal{G}(n,p)$ - a canonical null model with no planted community structure. We show that LPA reaches consensus asymptotically almost surely when $np\ge n^{5/8+\varepsilon}$ for any fixed $\varepsilon>0$, thus breaking the current best $n^{3/4+\varepsilon}$ analytical barrier. More remarkably, we uncover a phase transition governing \emph{which} label survives: when $np\gg n^{2/3}$, the surviving label is asymptotically almost surely the smallest initial label, whereas for $n^{5/8+\varepsilon}\le np\ll n^{2/3}$, the surviving label is asymptotically almost surely not the smallest one. We further show that, in the critical window $np=Θ(n^{2/3})$, both outcomes have probability $Θ(1).$ Our analysis has several important ingredients. We analyze a staged exploration that progressively reveals information about the random graph while preserving some randomness needed to track the amplification of label advantages across multiple rounds. This analysis is complemented by novel coupling and decoupling arguments that control the dependencies inherent to the process. Along the way, we establish a monotonicity result for competing binomial random variables that we believe is of independent interest.
查看此版本解读 →查看此版本原文 ↗