Improved spectral community detection in large heterogeneous networks

Hafiz TIOMOKO ALI; Romain COUILLET

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.

Improved spectral community detection in large heterogeneous networks

Abstract