Fast Network Community Detection by Score

• Activity Number: 209
• Type: Invited
• Date/Time: Monday, August 5, 2013 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Jiashun Jin*+
• Companies: Carnegie Mellon University
• Keywords: Social network ; community detection ; spectral method ; modularity ; Random matrix theory ; weblog data

Abstract

We consider the problem of network community detection with the Degree Corrected Block Model (DCBM). The main challenge of the problem lies in the degree heterogeneity.

We propose Spectral Clustering On Ratios-of-Eigenvectors (SCORE) as a new approach to community detection. Compared to classical spectral methods, the main innovation is to use the entry-wise ratios between the first leading eigenvector and each of the other leading eigenvectors. The central surprise is, the effect of degree heterogeneity is largely ancillary, and can be effectively removed by SCORE.

The method is successfully applied to the web blogs data and the karate club data, with error rates of 58/1222 and 1/34, respectively. These results are much more satisfactory than that by the classical spectral methods. Also, compared to modularity methods, SCORE is computationally much faster and has smaller error rates.

We develop a theoretic framework where we show that under mild conditions, the SCORE stably yields successful community detection. In the core of the analysis is the recent development on Random Matrix Theory (RMT), where the matrix-form Bernstein inequality is especially helpful.