Paper Info
Title
Spectral partitioning in random regular blockmodels.
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 random graphs with regular block structure is introduced, for which analytical results can be obtained. In particular, the spectral density of such random regular blockmodels is computed exactly for a modular, bipartite and core-periphery structure. McKayu0027s law for random regular graphs is found analytically to apply also for regular modular and bipartite structures when blocks are homogeneous. In core-periphery structures, where blocks are intrinsically heterogeneous, a new law is found to apply for the spectral density. Exact solution to the inference problem is provided for the models discussed. All analytical results show perfect agreement with numerical experiments. Final discussion summarizes results and outlines the relevance of the results for the solution of graph partitioning problems in other graph ensembles, in particular for the study of detectability thresholds and resolution limits.
Year
Venue
Field
2016
arXiv: Social and Information Networks
Random graph,Computer science,Theoretical computer science,Voltage graph
DocType
Volume
Citations 
Journal
abs/1610.02668
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Paolo Barucca1113.76