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 (178)
- Fast unfolding of communities in large networks
- Finding community structure in networks using the eigenvectors of matrices
- Synchronization in complex networks
- Finding statistically significant communities in networks
- Community structure in directed networks
- Consensus clustering in complex networks
- An information-theoretic framework for resolving community structure in complex networks
- Communicability in complex networks
- Detect overlapping and hierarchical community structure in networks
- Hierarchical modularity in human brain functional networks
- Extracting the hierarchical organization of complex systems
- Sustaining the Internet with Hyperbolic Mapping
- Robust Detection of Dynamic Community Structure in Networks
- Community detection in networks with positive and negative links
- Analysis of the structure of complex networks at different resolution levels
- Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
- 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
- Graph spectra and the detectability of community structure in networks
- A Classification for Community Discovery Methods in Complex Networks
- Analysis of community structure in networks of correlated data
- Modularity clustering is force-directed layout
- Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
- 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
- Preferential Detachment During Human Brain Development: Age- and Sex-Specific Structural Connectivity in Diffusion Tensor Imaging (DTI) Data
- Large-scale structure of time evolving citation networks
- Spectral coarse-graining of complex networks
- Extraction of Force-Chain Network Architecture in Granular Materials Using Community Detection
- Quantifying and identifying the overlapping community structure in networks
- Bi-clique Communities
- Motif-based communities in complex networks
- Prediction and Clustering in Signed Networks: A Local to Global Perspective
- Social significance of community structure: Statistical view
- Directed network modules
- Event detection, tracking, and visualization in Twitter: a mention-anomaly-based approach
- Alignment and integration of complex networks by hypergraph-based spectral clustering
- Model selection and hypothesis testing for large-scale network models with overlapping groups
- Cascading Dynamics in Modular Networks
- Empirical Comparison of Algorithms for Network Community Detection
- Spectral methods for the detection of network community structure: a comparative analysis
- Spectra of random graphs with arbitrary expected degrees
- Ideological and Temporal Components of Network Polarization in Online Political Participatory Media
- Spectral tripartitioning of networks
- A New Comparative Definition of Community and Corresponding Identifying Algorithm
- Random matrix analysis of complex networks
- Structure of local interactions in complex financial dynamics
- Graph-based Anomaly Detection and Description: A Survey
- Propagation dynamics on networks featuring complex topologies
- Synchronization and modularity in complex networks
- Identification of network modules by optimization of ratio association
- Community Structure Detection in Complex Networks with Partial Background Information
- Multilayer weighted social network model
- Comparison of Communities Detection Algorithms for Multiplex
- Community structure and the evolution of interdisciplinarity in Slovenia's scientific collaboration network
- Potts model based on a Markov process computation solves the community structure problem effectively
- Covariance, correlation matrix and the multi-scale community structure of networks
- Markov random walk under constraint for discovering overlapping communities in complex networks
- Multi-scale Modularity in Complex Networks
- Using Triangles to Improve Community Detection in Directed Networks
- Divide and Conquer: Partitioning Online Social Networks
- Maximizing Influence Propagation in Networks with Community Structure
- A Case Study in Text Mining: Interpreting Twitter Data From World Cup Tweets
- Detecting communities of triangles in complex networks using spectral optimization
- Detection of node group membership in networks with group overlap
- DEMON: a Local-First Discovery Method for Overlapping Communities
- Deterministic Modularity Optimization
- Inversion method for content-based networks
- Community Detection in Complex Networks by Dynamical Simplex Evolution
- Development of modularity in the neural activity of children's brains
- Uncovering allosteric pathways in caspase-1 with Markov transient analysis and multiscale community detection
- Fast and accurate determination of modularity and its effect size
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- Community structure benefits the fixation of cooperation under strong selection
- Centralized Modularity of N-Linked Glycosylation Pathways in Mammalian Cells
- Random matrix analysis of network Laplacians
- Climatic seasonality may affect ecological network structure: Food webs and mutualistic networks
- Optimizing an Organized Modularity Measure for Topographic Graph Clustering: a Deterministic Annealing Approach
- Genetic Algorithm with a Local Search Strategy for Discovering Communities in Complex Networks
- Analysis of stability of community structure across multiple hierarchical levels
- Revealing Multiple Layers of Hidden Community Structure in Networks
- Model validation of simple-graph representations of metabolism
- Universal Phase Transition in Community Detectability under a Stochastic Block Model
- Detecting Overlapping Temporal Community Structure in Time-Evolving Networks
- Community detection in bipartite networks using weighted symmetric binary matrix factorization
- Overlapping Community Detection in Bipartite Networks
- Integrating temporal and spatial scales: Human structural network motifs across age and region-of-interest size
- Identifying overlapping communities in social networks using multi-scale local information expansion
- Component models for large networks
- Genetic flow directionality and geographical segregation in a Cymodocea nodosa genetic diversity network
- Mesoscopic analysis of networks: applications to exploratory analysis and data clustering
- Simulated evolution of protein-protein interaction networks with realistic topology
- Ant Colony Optimization with a New Random Walk Model for Community Detection in Complex Networks
- Evolution of Coordination in Social Networks: A Numerical Study
- Discovering link communities in complex networks by exploiting link dynamics
- Metabolic network modularity arising from simple growth processes
- Finding Community Structure Based on Subgraph Similarity
- Characterization of Subgraphs Relationships and Distribution in Complex Networks
- Natural clustering: the modularity approach
- Community structure revealed by phase locking
- Spectral coarse graining for random walk in bipartite networks
- Resampling effects on significance analysis of network clustering and ranking
- Network Cross-Validation for Determining the Number of Communities in Network Data
- Quality functions in community detection
- Dynamic Computation of Network Statistics via Updating Schema
- On the Permanence of Vertices in Network Communities
- Communities and classes in symmetric fractals
- Mathematical and Algorithmic Analysis of Network and Biological Data
- Detecting groups of similar components in complex networks
- Learning-Induced Autonomy of Sensorimotor Systems
- Community Detection via Local Dynamic Interaction
- Efficient Bayesian Community Detection using Non-negative Matrix Factorisation
- Discovering Social Circles in Ego Networks
- Emergence of Clustering in an Acquaintance Model without Homophily
- Community Detection using a Measure of Global Influence
- Emergence and persistence of communities in coevolutionary networks
- Multi-level algorithms for modularity clustering
- Organizational structure and communication networks in a university environment
- Node-Context Network Clustering using PARAFAC Tensor Decomposition
- Defining and Evaluating Network Communities based on Ground-truth
- The architecture of innovation: Tracking face-to-face interactions with ubicomp technologies
- An upper bound on community size in scalable community detection
- Topics in social network analysis and network science
- Extending modularity by capturing the similarity attraction feature in the null model
- Benchmarking community detection methods on social media data
- Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q
- The art of community detection
- A Modular Multiscale Approach to Overlapping Community Detection
- Compressive Network Analysis
- Transition from the self-organized to the driven dynamical clusters
- On weakly optimal partitions in modular networks
- Signatures of currency vertices
- Generating Hierarchically Modular Networks via Link Switching
- Incorporating uncertainty into the study of animal social networks
- Toward Emerging Topic Detection for Business Intelligence: Predictive Analysis of `Meme' Dynamics
- BiMAT: a MATLAB(R) package to facilitate the analysis and visualization of bipartite networks
- Shaping Communities out of Triangles
- How to Measure Significance of Community Structure in Complex Networks
- Locally Boosted Graph Aggregation for Community Detection
- Modules of human micro-RNA co-target network
- Fixed-Points of Social Choice: An Axiomatic Approach to Network Communities
- Leveraging Sociological Models for Predictive Analytics
- A Feasible Graph Partition Framework for Random Walks Implemented by Parallel Computing in Big Graph
- Phase Transitions in Spectral Community Detection of Large Noisy Networks
- Maps of Computer Science
- Web Analytics for Security Informatics
- Cooperation on Social Networks and Its Robustness
- A New Analysis Method for Simulations Using Node Categorizations
- Controlled Label Propagation: Preventing Over-Propagation through Gradual Expansion
- Clustering evolving data using kernel-based methods
- Link Analysis for Communities Detection on Facebook
- A rough-and-ready cluster-based approach for extracting finite-time coherent sets from sparse and incomplete trajectory data
- Knowledge discovery via multidimensional science maps: the case of the Species Problem
- Overlapping Communities in Complex Networks
- Ground state energy of -state Potts model: the minimum modularity
- Reconstruction in the Labeled Stochastic Block Model
- Analysis of Social Voting Patterns on Digg
- The Concentration and Stability of the Community Detecting Functions on Random Networks
- Early Warning Analysis for Social Diffusion Events
- Three faces of metabolites: Pathways, localizations and network positions
- Model Selection in Overlapping Stochastic Block Models
- Conan: a platform for complex network analysis
- Bio-inspired Methods for Dynamic Network Analysis in Science Mapping
- Computing an Aggregate Edge-Weight Function for Clustering Graphs with Multiple Edge Types
- Node, Node-Link, and Node-Link-Group Diagrams: An Evaluation
- Emergence of communities on a coevolutive model of wealth interchange
- Interactive Overlays: A New Method for Generating Global Journal Maps from Web-of-Science Data
- Inference of higher order substitution dynamics by Markov chain lumping
- Network as a computer: ranking paths to find flows
- Continuous-time random walk model of relaxation of two-state systems