Home Page

Papers

Submissions

News

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Statistics

Login

Contact Us



RSS Feed

Improved spectral community detection in large heterogeneous networks

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

Abstract

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.

[abs][pdf][bib]       
© JMLR 2018. (edit)