Walk modularity and community structure in networks
arXiv:1401.6733 · doi:10.1017/nws.2015.20
Abstract
Modularity maximization has been one of the most widely used approaches in the last decade for discovering community structure in networks of practical interest in biology, computing, social science, statistical mechanics, and more. Modularity is a quality function that measures the difference between the number of edges found within clusters minus the number of edges one would statistically expect to find based on random chance. We present a natural generalization of modularity based on the difference between the actual and expected number of walks within clusters, which we call walk-modularity. Walk-modularity can be expressed in matrix form, and community detection can be performed by finding leading eigenvectors of the walk-modularity matrix. We demonstrate community detection on both synthetic and real-world networks and find that walk-modularity maximization returns significantly improved results compared to traditional modularity maximization.
13 pages, 6 figures, 1 table
References in corpus (17)
- Fast unfolding of communities in large networks
- Modularity and community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Statistical Mechanics of Community Detection
- Modularity and community detection in bipartite networks
- Communicability in complex networks
- Phase transition in the detection of modules in sparse networks
- Extending the definition of modularity to directed graphs with overlapping communities
- Modularity-Maximizing Network Communities via Mathematical Programming
- Graph spectra and the detectability of community structure in networks
- Motif-based communities in complex networks
- Communicability Graph and Community Structures in Complex Networks
- A paradox in community detection
- Driving interconnected networks to supercriticality