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.
arXiv comment13 pages, 6 figures, 1 table
References in corpus (27)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large 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
- Community detection in complex networks using Extremal Optimization
- The performance of modularity maximization in practical contexts
- Modularity and community detection in bipartite networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Communicability in complex networks
- Fuzzy communities and the concept of bridgeness in complex networks
- Phase transition in the detection of modules in sparse networks
- The Physics of Communicability in Complex 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
- Tolerating the Community Detection Resolution Limit with Edge Weighting
- Motif-based communities in complex networks
- Communicability Graph and Community Structures in Complex Networks
- Detectability of communities in heterogeneous networks
- A paradox in community detection
- Driving interconnected networks to supercriticality