Spectral Algorithms for Community Detection in Directed Networks
arXiv:2008.03820
Abstract
Community detection in large social networks is affected by degree heterogeneity of nodes. The D-SCORE algorithm for directed networks was introduced to reduce this effect by taking the element-wise ratios of the singular vectors of the adjacency matrix before clustering. Meaningful results were obtained for the statistician citation network, but rigorous analysis on its performance was missing. First, this paper establishes theoretical guarantee for this algorithm and its variants for the directed degree-corrected block model (Directed-DCBM). Second, this paper provides significant improvements for the original D-SCORE algorithms by attaching the nodes outside of the community cores using the information of the original network instead of the singular vectors.
arXiv commentJournal of Machine Learning Research 2020, to appear
References in corpus (8)
- Finding and evaluating community structure in networks
- Stochastic blockmodels and community structure in networks
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Fast community detection by SCORE
- Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
- Community extraction for social networks
- Coauthorship and Citation Networks for Statisticians
- Role models for complex networks