# 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

### Transitions in loopy graphs

The generation of large graphs with a controllable number of short loops paves the way for building more realistic random networks.

### Bursting dynamic networks

A mathematical model captures the temporal and steady state behaviour of networks whose two sets of nodes either generate or destroy links.

### 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.