Modularity and community structure in networks
arXiv:physics/0602124 · doi:10.1073/pnas.0601602103
Abstract
Many networks of interest in the sciences, including a variety of social and biological networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure has attracted considerable recent attention. One of the most sensitive detection methods is optimization of the quality function known as "modularity" over the possible divisions of a network, but direct application of this method using, for instance, simulated annealing is computationally costly. Here we show that the modularity can be reformulated in terms of the eigenvectors of a new characteristic matrix for the network, which we call the modularity matrix, and that this reformulation leads to a spectral algorithm for community detection that returns results of better quality than competing methods in noticeably shorter running times. We demonstrate the algorithm with applications to several network data sets.
7 pages, 3 figures
References in corpus (3)
Cited by in corpus (65)
- Fast unfolding of communities in large networks
- Finding community structure in networks using the eigenvectors of matrices
- Synchronization in complex networks
- Community structure in directed networks
- An information-theoretic framework for resolving community structure in complex networks
- Communicability in complex networks
- Detect overlapping and hierarchical community structure in networks
- Extracting the hierarchical organization of complex systems
- Community detection in networks with positive and negative links
- Analysis of the structure of complex networks at different resolution levels
- Robustness of community structure in networks
- Extending the definition of modularity to directed graphs with overlapping communities
- Modularity-Maximizing Network Communities via Mathematical Programming
- Size reduction of complex networks preserving modularity
- Analysis of community structure in networks of correlated data
- Modularity clustering is force-directed layout
- Evaluating Local Community Methods in Networks
- Identifying network communities with a high resolution
- Maximizing Modularity is hard
- Exploring the Free Energy Landscape: From Dynamics to Networks and Back
- Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
- Community Structure in Congressional Cosponsorship Networks
- Synchronization processes in complex networks
- Communities, Knowledge Creation, and Information Diffusion
- Large-scale structure of time evolving citation networks
- Spectral coarse-graining of complex networks
- Quantifying and identifying the overlapping community structure in networks
- Motif-based communities in complex networks
- Bi-clique Communities
- Directed network modules
- Cascading Dynamics in Modular Networks
- Spectral tripartitioning of networks
- A New Comparative Definition of Community and Corresponding Identifying Algorithm
- Random matrix analysis of complex networks
- Synchronization and modularity in complex networks
- Identification of network modules by optimization of ratio association
- Divide and Conquer: Partitioning Online Social Networks
- Maximizing Influence Propagation in Networks with Community Structure
- Deterministic Modularity Optimization
- Detection of node group membership in networks with group overlap
- Inversion method for content-based networks
- Community Detection in Complex Networks by Dynamical Simplex Evolution
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- Centralized Modularity of N-Linked Glycosylation Pathways in Mammalian Cells
- Random matrix analysis of network Laplacians
- Model validation of simple-graph representations of metabolism
- Overlapping Community Detection in Bipartite Networks
- Component models for large networks
- Finding Community Structure Based on Subgraph Similarity
- Characterization of Subgraphs Relationships and Distribution in Complex Networks
- Natural clustering: the modularity approach
- Dynamic Computation of Network Statistics via Updating Schema
- Quality functions in community detection
- Detecting groups of similar components in complex networks
- Community Detection using a Measure of Global Influence
- Multi-level algorithms for modularity clustering
- The art of community detection
- Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q
- Signatures of currency vertices
- Generating Hierarchically Modular Networks via Link Switching
- Incorporating uncertainty into the study of animal social networks
- Analysis of Social Voting Patterns on Digg
- Inference of higher order substitution dynamics by Markov chain lumping
- Network as a computer: ranking paths to find flows
- Three faces of metabolites: Pathways, localizations and network positions