# Spectral partitioning in equitable graphs

*Physical Review E* 95, 62310 (2017)

#graphtheory#communitydetection#spectraltheory

Eigenvectors' statistics can help us identify community structures in complex systems.

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.

#### A phase transition creates the geometry of the continuum from discrete space

R. Farr, T. Fink

Sub. to *Physical Review E*

#### The statistical physics of real-world networks

G. Cimini, T. Squartini, F. Saracco, D. Garlaschelli, A. Gabrielli, G. Caldarelli

*Nature Reviews Physics*

#### On defining the Hamiltonian beyond quantum theory

D. Branford, O. Dahlsten, A. Garner

*Foundations of Physics*

#### Reconstructing grain-shape statistics from electron back-scatter diffraction microscopy

R. Farr, Z. Vukmanovic, M. Holness, E. Griffiths

*Physical Review Materials*

#### Tackling information asymmetry in networks: a new entropy-based ranking index

P. Barucca, G. Caldarelli, T. Squartini

*Journal of Statistical Physics*

#### Eigenvalues of subgraphs of the cube

B. Bollobás, J. Lee, S. Letzter

*European Journal of Combinatorics*

#### Maximum one-shot dissipated work from Rényi divergences

N. Halpern, A. Garner, O. Dahlsten, V. Vedral

*Physical Review E *

123 / 123 papers