Scalable Spectral Algorithms for Community Detection in Directed Networks
arXiv:1211.6807
Abstract
Community detection has been one of the central problems in network studies and directed network is particularly challenging due to asymmetry among its links. In this paper, we found that incorporating the direction of links reveals new perspectives on communities regarding to two different roles, source and terminal, that a node plays in each community. Intriguingly, such communities appear to be connected with unique spectral property of the graph Laplacian of the adjacency matrix and we exploit this connection by using regularized SVD methods. We propose harvesting algorithms, coupled with regularized SVDs, that are linearly scalable for efficient identification of communities in huge directed networks. The proposed algorithm shows great performance and scalability on benchmark networks in simulations and successfully recovers communities in real network applications.
arXiv commentSingle column, 40 pages, 6 figures and 7 tables
References in corpus (16)
- Modularity and community structure in networks
- Community detection in graphs
- Benchmark graphs for testing community detection algorithms
- Community detection algorithms: a comparative analysis
- Detecting the overlapping and hierarchical community structure of complex networks
- Community structure in directed networks
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- The map equation
- Finding local community structure in networks
- Mixture models and exploratory analysis in networks
- Size reduction of complex networks preserving modularity
- Detecting communities in large networks
- Optimal Solutions for Sparse Principal Component Analysis
- Community extraction for social networks
- Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
- A Sparse SVD Method for High-dimensional Data