Home Page




Editorial Board


Open Source Software




Frequently Asked Questions

Contact Us

RSS Feed

Improved spectral community detection in large heterogeneous networks

Hafiz TIOMOKO ALI, Romain COUILLET; 18(225):1−49, 2018.


In this article, we propose and study the performance of spectral community detection for a family of “$\alpha$-normalized” adjacency matrices $\bf A$, of the type $ {\bf D}^{-\alpha}{\bf A}{\bf D}^{-\alpha}$ with $\bf D$ the degree matrix, in heterogeneous dense graph models. We show that the previously used normalization methods based on ${\bf A}$ or $ {\bf D}^{-1}{\bf A}{\bf D}^{-1} $ are in general suboptimal in terms of correct recovery rates and, relying on advanced random matrix methods, we prove instead the existence of an optimal value $ \alpha_{\rm opt} $ of the parameter $ \alpha $ in our generic model; we further provide an online estimation of $ \alpha_{\rm opt} $ only based on the node degrees in the graph. Numerical simulations show that the proposed method outperforms state-of-the-art spectral approaches on moderately dense to dense heterogeneous graphs.

© JMLR 2018. (edit, beta)