Spectral partitioning in equitable graphs

P. Barucca

Physical Review E 95, 62310 (2017)

#graphtheory#communitydetection#spectraltheory

Download the PDF

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

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.

LQ placeholder

Imaginary replica analysis of loopy regular random graphs

F. Lopez, T. Coolen

Sub. to Journal of Physics A

LQ placeholder

Taming complexity

M. Reeves, S. Levin, T. Fink, A. Levina

Harvard Business Review

LQ placeholder

Degree-correlations in a bursting dynamic network model

F. Vanni, P. Barucca

Journal of Economic Interaction and Coordination

LQ placeholder

Scale of non-locality for a system of n particles

S. Talaganis, I. Teimouri

Sub. to Physical Review D

LQ placeholder

How much can we influence the rate of innovation?

T. Fink, M. Reeves

Science Advances

123 / 123 papers