Exactly Solvable Random Graph Ensemble with Extensively Many Short Cycles

Abstract

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.

References in corpus (17)

• Random graphs with arbitrary degree distributions and their applications
• Growing Scale-Free Networks with Tunable Clustering
• Generation of uncorrelated random scale-free networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Random graphs with clustering
• Emergence of a small world from local interactions: Modeling acquaintance networks
• Triadic closure as a basic generating mechanism of communities in complex networks
• Estimating and understanding exponential random graph models
• A Model for Social Networks
• Duplication-divergence model of protein interaction network
• Log-Networks
• Network Transitivity and Matrix Models
• Eigenvalue tunnelling and decay of quenched random networks
• Constrained Markovian dynamics of random graphs
• Sparse random graphs with clustering
• Replica methods for loopy sparse random graphs
• A detailed investigation into near degenerate exponential random graphs

Cited by in corpus (5)

• Universal hypotrochoidic law for random matrices with cyclic correlations
• Self-avoiding walks and connective constants in clustered scale-free networks
• Imaginary replica analysis of loopy regular random graphs
• Entropy of microcanonical finite-graph ensembles
• Free-energy density functional for Strauss's model of transitive networks