Spectral Algorithms for Community Detection in Directed Networks
This work addresses community detection in directed social networks, offering incremental improvements with theoretical backing for practitioners in network analysis.
The paper tackled the problem of community detection in directed networks affected by degree heterogeneity by providing theoretical guarantees for the D-SCORE algorithm and its variants under the Directed-DCBM model, and improved the algorithm by better handling nodes outside community cores, achieving meaningful results in a citation network.
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.