Spectral tripartitioning of networks
arXiv:0812.2852 · doi:10.1103/PhysRevE.80.036111
Abstract
We formulate a spectral graph-partitioning algorithm that uses the two leading eigenvectors of the matrix corresponding to a selected quality function to split a network into three communities in a single step. In so doing, we extend the recursive bipartitioning methods developed by Newman [Proc. Nat. Acad. Sci. 103, 8577 (2006); Phys. Rev. E 74, 036104 (2006)] to allow one to consider the best available two-way and three-way divisions at each recursive step. We illustrate the method using simple "bucket brigade" examples and then apply the algorithm to examine the community structures of the coauthorship graph of network scientists and of U. S. Congressional networks inferred from roll-call voting similarities.
12 pages with 4 figures, resubmitted version accepted for publication in Physical Review E
References in corpus (25)
- Fast unfolding of communities in large networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Fast algorithm for detecting community structure in networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Finding community structure in networks using the eigenvectors of matrices
- Functional cartography of complex metabolic networks
- Resolution limit in community detection
- Comparing community structure identification
- Critical phenomena in complex networks
- Hierarchical structure and the prediction of missing links in networks
- Statistical Mechanics of Community Detection
- Detecting the overlapping and hierarchical community structure of complex networks
- Quantifying social group evolution
- Community structure in directed networks
- Finding local community structure in networks
- Analysis of the structure of complex networks at different resolution levels
- Detecting Network Communities: a new systematic and efficient algorithm
- Detecting communities in large networks
- A Bayesian Approach to Network Modularity
- A Local Method for Detecting Communities
- Community Structure in Congressional Cosponsorship Networks
- Community Structure in the United States House of Representatives
Cited by in corpus (23)
- Community detection in graphs
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Dynamic reconfiguration of human brain networks during learning
- The performance of modularity maximization in practical contexts
- Social Structure of Facebook Networks
- Robust Detection of Dynamic Community Structure in Networks
- Uncovering space-independent communities in spatial networks
- Community Detection via Maximization of Modularity and Its Variants
- Z-score-based modularity for community detection in networks
- Detection of Core-Periphery Structure in Networks Using Spectral Methods and Geodesic Paths
- Multiway spectral community detection in networks
- Network Community Detection: A Review and Visual Survey
- Community Structure in the United Nations General Assembly
- A New Metric for Quality of Network Community Structure
- Adaptive Modularity Maximization via Edge Weighting Scheme
- Community detection in networks via nonlinear modularity eigenvectors
- A Study on Modularity Density Maximization: Column Generation Acceleration and Computational Complexity Analysis
- Additive Approximation Algorithms for Modularity Maximization
- A Spectral Representation of Power Systems with Applications to Adaptive Grid Partitioning and Cascading Failure Localization
- A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme
- Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
- Block-corrected Modularity for Community Detection
- Understanding Vulnerability of Communities in Complex Networks