Spectral partitioning in equitable graphs
arXiv:1610.02668 · doi:10.1103/PhysRevE.95.062310
Abstract
Graph partitioning problems emerge in a wide variety of complex systems, ranging from biology to finance, but can be rigorously analyzed and solved only for a few graph ensembles. Here, an ensemble of equitable graphs, i.e. random graphs with a block-regular structure, is studied, for which analytical results can be obtained. In particular, the spectral density of this ensemble is computed exactly for a modular and bipartite structure. Kesten-McKay's law for random regular graphs is found analytically to apply also for modular and bipartite structures when blocks are homogeneous. Exact solution to graph partitioning for two equal-sized communities is proposed and verified numerically, and a conjecture on the absence of an efficient recovery detectability transition in equitable graphs is suggested. Final discussion summarizes results and outlines their relevance for the solution of graph partitioning problems in other graph ensembles, in particular for the study of detectability thresholds and resolution limits in stochastic block models.
arXiv comment8 pages, 8 figures
References in corpus (19)
- Fast unfolding of communities in large networks
- Community detection in graphs
- Resolution limit in community detection
- Stochastic blockmodels and community structure in networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
- Phase transition in the detection of modules in sparse networks
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Graph spectra and the detectability of community structure in networks
- Parsimonious module inference in large networks
- Nonparametric Bayesian inference of the microcanonical stochastic block model
- Spectral statistics of Erdős-Rényi graphs I: Local semicircle law
- Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
- Detectability of communities in heterogeneous networks
- Sparse regular random graphs: Spectral density and eigenvectors
- Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
- A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
- Equitable random graphs
Cited by in corpus (5)
- -Spread and Restricted Isometry Properties of Sparse Random Matrices
- Spectral gap in random bipartite biregular graphs and applications
- Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
- Spectral density of equitable core-periphery graphs
- Uniqueness of communities in regular stochastic block models