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 (54)

• 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
• 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
• Community detection in networks with positive and negative links
• Analysis of the structure of complex networks at different resolution levels
• 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
• Modularity clustering is force-directed layout
• Identifying network communities with a high resolution
• Limited resolution in complex network community detection with Potts model approach
• Community Structure in Congressional Cosponsorship Networks
• Communities, Knowledge Creation, and Information Diffusion
• Motif-based communities in complex networks
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Spectral tripartitioning of networks
• Bicomponents and the robustness of networks to failure
• 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
• Unveiling community structures in weighted networks
• Detection of node group membership in networks with group overlap
• Deterministic Modularity Optimization
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Communicability and multipartite structures in complex networks at negative absolute temperatures
• Topologies and Laplacian spectra of a deterministic uniform recursive tree
• Reinforced communication and social navigation generate groups in model networks
• Overlapping Community Detection in Bipartite Networks
• A Graph Analysis of the Linked Data Cloud
• Modeling and verifying a broad array of network properties
• Network Topology of an Experimental Futures Exchange
• Characterization of Subgraphs Relationships and Distribution in Complex Networks
• Partition of Networks into Basins of Attraction
• Detecting groups of similar components in complex networks
• Multi-level algorithms for modularity clustering
• Community Detection using a Measure of Global Influence
• Adaptation to synchronization in phase-oscillator networks
• Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q
• On the Stability of Community Detection Algorithms on Longitudinal Citation Data
• Ensembles related to the rich-club coefficient for non-evolving networks
• A fast multilevel algorithm for graph clustering and community detection
• Weblog Clustering in Multilinear Algebra Perspective
• The emergence of unshared consensus decisions in bottlenose dolphins
• Role of Weak Ties in Link Prediction of Complex Networks
• Finding Astronomical Communities Through Co-readership Analysis
• The Continuous Node Degree: a New Measure for Complex Networks