Exactly solvable random graph ensemble with extensively many short cycles
An explicit analytical solution reproduces the main features of random graph ensembles with many short cycles under strict degree constraints.
Journal of Physics A 51, 85101 (2018)
F. Lopez, P. Barucca, M. Fekom, A. Coolen
We introduce and analyse ensembles of 2-regular random graphs with a tuneable distribution of short cycles. The phenomenology of these graphs depends critically on the scaling of the ensembles' control parameters relative to the number of nodes. A phase diagram is presented, showing a second order phase transition from a connected to a disconnected phase. We study both the canonical formulation, where the size is large but fixed, and the grand canonical formulation, where the size is sampled from a discrete distribution, and show their equivalence in the thermodynamical limit. We also compute analytically the spectral density, which consists of a discrete set of isolated eigenvalues, representing short cycles, and a continuous part, representing cycles of diverging size.
More in Intelligence of graphs
Tailored random graph ensembles
New mathematical tools quantify the topological structure of large directed networks which describe how genes interact within a cell.
Entropies of graph ensembles
Explicit formulae for the Shannon entropies of random graph ensembles provide measures to compare and reproduce their topological features.
Unbiased randomization
Unbiased randomisation processes generate sophisticated synthetic networks for modelling and testing the properties of real-world networks.
Spin systems on Bethe lattices
Exact equations for the thermodynamic quantities of lattices made of d-dimensional hypercubes are obtainable with the Bethe-Peierls approach.
Random graphs with short loops
The analysis of real networks which contain many short loops requires novel methods, because they break the assumptions of tree-like models.