MathSciDoc: An Archive for Mathematician ∫

Community detection is a fundamental problem in social network analysis. It is desirable to have fast community detection algorithm that applicable to large-scale networks we see today and also have reliable community detection results. This paper proposes Spectral Clustering On Ratios-of-eigenvectors (SCORE) as such an algorithm. The algorithm is fast in computation, is applicable to real large networks, and is competitive in real data performance when applied to some representative data sets in this area. We study the algorithm with the Degree-Corrected Block Model (DCBM). Compare to most works in this area that focus on the much narrower Block Models, our analysis is more difficult and requires new techniques. The novelty of our algorithm lies in that it uses entry-wise ratios between leading eigenvectors of the adjacency to reduce a seemingly hard problem to a problem that is very much tractable.

sparsity, social network, spectral analysis, community detection