UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Spectral partitioning in equitable graphs

Barucca, P; (2017) Spectral partitioning in equitable graphs. Physical Review E , 95 , Article 062310. 10.1103/PhysRevE.95.062310. Green open access

[img]
Preview
Text
PhysRevE.95.062310.pdf - Published version

Download (517kB) | Preview

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. An 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. A 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.

Type: Article
Title: Spectral partitioning in equitable graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1103/PhysRevE.95.062310
Publisher version: http://dx.doi.org/10.1103/PhysRevE.95.062310
Language: English
Additional information: This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Science & Technology, Physical Sciences, Physics, Fluids & Plasmas, Physics, Mathematical, Physics, EIGENVECTORS, NETWORKS
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10045587
Downloads since deposit
119Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item