Fast community detection by SCORE

Jiashun Jin Carnegie Mellon University

Statistics Theory and Methods mathscidoc:2005.33001

Distinguished Paper Award in 2020

Annals of Statistics , 43, (1), 57-89, 2015.2
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
[ Download ] [ 2020-05-13 09:30:25 uploaded by jiashun ] [ 310 downloads ] [ 0 comments ]
@inproceedings{jiashun2015fast,
  title={Fast community detection by SCORE },
  author={Jiashun Jin},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20200513093025693561678},
  booktitle={Annals of Statistics },
  volume={43},
  number={1},
  pages={57-89},
  year={2015},
}
Jiashun Jin. Fast community detection by SCORE . 2015. Vol. 43. In Annals of Statistics . pp.57-89. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20200513093025693561678.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved