Performance Analysis of Spectral Community Detection in Realistic Graph Models

Publication Type:

Conference Paper

Source:

41st IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2016), Shanghai, China (2016)

Abstract:

This article proposes a spectral analysis of dense random graphs generated by (a modified version of) the degree-corrected stochastic block model, for a setting where the inter block probabilities differ by $\mathcal{O}(n^{-\frac{1}{2}})$ with n the number of nodes. We study a normalized ver- sion of the graph modularity matrix which is shown to be asymptoti- cally well approximated by an analytically tractable (spiked) random matrix. The analysis of the latter allows for the precise evaluation of (i) the transition phase where clustering becomes asymptotically fea- sible and (ii) the alignment between the dominant eigenvectors and the block-wise canonical basis, thus enabling the estimation of mis- classification rates (prior to post-processing) in simple scenarios.