Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models
Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models
复制标题
次数校正随机块模型的非回溯谱
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
L. Massoulié
中科院分区：
文献类型：
--
作者：
Lennart Gulikers;M. Lelarge;L. Massoulié
在社区检测的激励下，我们在度校正随机块模型中表征了非回溯矩阵$B$的频谱。
Motivated by community detection, we characterise the spectrum of the non-backtracking matrix $B$ in the Degree-Corrected Stochastic Block Model.
Specifically, we consider a random graph on $n$ vertices partitioned into two equal-sized clusters. The vertices have i.i.d. weights ${ phi_u }_{u=1}^n$ with second moment $Phi^{(2)}$. The intra-cluster connection probability for vertices $u$ and $v$ is $frac{phi_u phi_v}{n}a$ and the inter-cluster connection probability is $frac{phi_u phi_v}{n}b$.
We show that with high probability, the following holds: The leading eigenvalue of the non-backtracking matrix $B$ is asymptotic to $
ho = frac{a+b}{2} Phi^{(2)}$. The second eigenvalue is asymptotic to $mu_2 = frac{a-b}{2} Phi^{(2)}$ when $mu_2^2 >
ho$, but asymptotically bounded by $sqrt{
ho}$ when $mu_2^2 leq
ho$. All the remaining eigenvalues are asymptotically bounded by $sqrt{
ho}$. As a result, a clustering positively-correlated with the true communities can be obtained based on the second eigenvector of $B$ in the regime where $mu_2^2 >
ho.$
In a previous work we obtained that detection is impossible when $mu_2^2 <
ho,$ meaning that there occurs a phase-transition in the sparse regime of the Degree-Corrected Stochastic Block Model.
As a corollary, we obtain that Degree-Corrected Erdős-Renyi graphs asymptotically satisfy the graph Riemann hypothesis, a quasi-Ramanujan property.
A by-product of our proof is a weak law of large numbers for local-functionals on Degree-Corrected Stochastic Block Models, which could be of independent interest.