Finding community structure in networks using the eigenvectors of matrices

Abstract

We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a new centrality measure that identifies those vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks.

22 pages, 8 figures, minor corrections in this version

References in corpus (9)

• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Subnetwork hierarchies of biochemical pathways
• Community Detection as an Inference Problem
• Identifying "communities" within energy landscapes
• On network bipartivity
• Preferential attachment of communities: the same principle, but a higher level

Cited by in corpus (134)

• Fast unfolding of communities in large networks
• Near linear time algorithm to detect community structures in large-scale networks
• Predicting Missing Links via Local Information
• Weight-conserving characterization of complex functional brain networks
• An information-theoretic framework for resolving community structure in complex networks
• Modularity and community detection in bipartite networks
• Communicability in complex networks
• Detect overlapping and hierarchical community structure in networks
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks
• Mixture models and exploratory analysis in networks
• 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
• Ranking spreaders by decomposing complex networks
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Prominence and control: The weighted rich-club effect
• Detecting network communities by propagating labels under constraints
• Extending the definition of modularity to directed graphs with overlapping communities
• Modularity-Maximizing Network Communities via Mathematical Programming
• A Classification for Community Discovery Methods in Complex Networks
• A k-shell decomposition method for weighted networks
• Prediction of Emerging Technologies Based on Analysis of the U.S. Patent Citation Network
• Modularity clustering is force-directed layout
• Partisan Asymmetries in Online Political Activity
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Robust network community detection using balanced propagation
• Identifying network communities with a high resolution
• Defecting or not defecting: how to "read" human behavior during cooperative games by EEG measurements
• Limited resolution in complex network community detection with Potts model approach
• Community Structure in Congressional Cosponsorship Networks
• Communities, Knowledge Creation, and Information Diffusion
• The method of moments and degree distributions for network models
• Extraction of Force-Chain Network Architecture in Granular Materials Using Community Detection
• Motif-based communities in complex networks
• The Naming Game in Social Networks: Community Formation and Consensus Engineering
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Spectral methods for the detection of network community structure: a comparative analysis
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Spectral tripartitioning of networks
• Opinion control in complex networks
• Bicomponents and the robustness of networks to failure
• Throughflow centrality is a global indicator of the functional importance of species in ecosystems
• Communicability Graph and Community Structures in Complex Networks
• Predicting the connectivity of primate cortical networks from topological and spatial node properties
• Note on the equivalence of the label propagation method of community detection and a Potts model approach
• Rich-club vs rich-multipolarization phenomena in weighted networks
• Covariance, correlation matrix and the multi-scale community structure of networks
• Multi-scale Modularity in Complex Networks
• Unveiling community structures in weighted networks
• Detecting communities of triangles in complex networks using spectral optimization
• Deterministic Modularity Optimization
• Detection of node group membership in networks with group overlap
• Detecting Communities in Networks by Merging Cliques
• Identification of Literary Movements Using Complex Networks to Represent Texts
• On time-varying collaboration networks
• Stochastic block model and exploratory analysis in signed networks
• Community structure benefits the fixation of cooperation under strong selection
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Fast and accurate determination of modularity and its effect size
• Complex networks: new trends for the analysis of brain connectivity
• Communicability and multipartite structures in complex networks at negative absolute temperatures
• Statistical properties of agent-based models in markets with continuous double auction mechanism
• Optimizing an Organized Modularity Measure for Topographic Graph Clustering: a Deterministic Annealing Approach
• Topologies and Laplacian spectra of a deterministic uniform recursive tree
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Reinforced communication and social navigation generate groups in model networks
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Overlapping Community Detection in Bipartite Networks
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Panther: Fast Top-k Similarity Search in Large Networks
• Identifying overlapping communities in social networks using multi-scale local information expansion
• A Graph Analysis of the Linked Data Cloud
• Modeling and verifying a broad array of network properties
• Network Topology of an Experimental Futures Exchange
• Local degree blocking model for link prediction in complex networks
• Mesoscale symmetries explain dynamical equivalence of food webs
• Characterization of Subgraphs Relationships and Distribution in Complex Networks
• Node mixing and group structure of complex software networks
• Partition of Networks into Basins of Attraction
• Spectral coarse graining for random walk in bipartite networks
• Oriented and Degree-generated Block Models: Generating and Inferring Communities with Inhomogeneous Degree Distributions
• The Link Prediction Problem in Bipartite Networks
• Detecting groups of similar components in complex networks
• Twitter and Polls: Analyzing and estimating political orientation of Twitter users in India General #Elections2014
• Detecting network communities beyond assortativity-related attributes
• Multi-level algorithms for modularity clustering
• Community Detection using a Measure of Global Influence
• Eigenvector localization as a tool to study small communities in online social networks
• Variability Analysis of Complex Networks Measures based on Stochastic Distances
• Node-Context Network Clustering using PARAFAC Tensor Decomposition
• Exponential Series Approaches for Nonparametric Graphical Models
• Diffusion-Aware Sampling and Estimation in Information Diffusion Networks
• Adaptation to synchronization in phase-oscillator networks
• Supervised Blockmodelling
• Extending modularity by capturing the similarity attraction feature in the null model
• Sampling from Diffusion Networks
• Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q
• Are we there yet? When to stop a Markov chain while generating random graphs
• Network Backbone Discovery Using Edge Clustering
• On the Stability of Community Detection Algorithms on Longitudinal Citation Data
• A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme
• Localized Algorithm of Community Detection on Large-Scale Decentralized Social Networks
• Entropy in Social Networks
• Coarse-Grained Topology Estimation via Graph Sampling
• How to Measure Significance of Community Structure in Complex Networks
• Ensembles related to the rich-club coefficient for non-evolving networks
• Properties of Latent Variable Network Models
• Weblog Clustering in Multilinear Algebra Perspective
• A fast multilevel algorithm for graph clustering and community detection
• Spectral Anomaly Detection in Very Large Graphs: Models, Noise, and Computational Complexity
• Botnet Detection using Social Graph Analysis
• Predicting missing links via correlation between nodes
• A decaying factor accounts for contained activity in neuronal networks with no need of hierarchical or modular organization
• Ensembles based on the Rich-Club and how to use them to build soft-communities
• Reconstructing propagation networks with temporal similarity metrics
• Diffusion and Superposition Distances for Signals Supported on Networks
• Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds
• The emergence of unshared consensus decisions in bottlenose dolphins
• A New Analysis Method for Simulations Using Node Categorizations
• Phase Transitions in Spectral Community Detection of Large Noisy Networks
• The Continuous Node Degree: a New Measure for Complex Networks
• Role of Weak Ties in Link Prediction of Complex Networks
• Overlapping Communities in Complex Networks
• Competitive Dynamics on Complex Networks
• A framework for community detection in heterogeneous multi-relational networks
• Finding Astronomical Communities Through Co-readership Analysis
• Overlapping Community Detection Optimization and Nash Equilibrium
• Multiplex Structures: Patterns of Complexity in Real-World Networks
• Modularity spectra, eigen-subspaces, and structure of weighted graphs
• Interplay between Network Topology and Dynamics in Neural Systems
• MODULAR: Software for the Autonomous Computation of Modularity in Large Network Sets
• Grouping Entities in a Fleet by Community Detection in Network of Regression Models