Home Page




Editorial Board

Special Issues

Open Source Software

Proceedings (PMLR)

Data (DMLR)

Transactions (TMLR)




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)