January 9, 2023
We present analytical results for the distribution of the number of cycles in directed and undirected random 2-regular graphs (2-RRGs) consisting of $N$ nodes. In directed 2-RRGs each node has one inbound link and one outbound link, while in undirected 2-RRGs each node has two undirected links. Since all the nodes are of degree $k=2$, the resulting networks consist of cycles. These cycles exhibit a broad spectrum of lengths, where the average length of the shortest cycle in a random network instance scales with $\ln N$, while the length of the longest cycle scales with $N$. The number of cycles varies between different network instances in the ensemble, where the mean number of cycles $\langle S \rangle$ scales with $\ln N$. Here we present exact analytical results for the distribution $P_N(S=s)$ of the number of cycles $s$ in ensembles of directed and undirected 2-RRGs, expressed in terms of the Stirling numbers of the first kind. In both cases the distributions converge to a Poisson distribution in the large $N$ limit. The moments and cumulants of $P_N(S=s)$ are also calculated. The statistical properties of directed 2-RRGs are equivalent to the combinatorics of cycles in random permutations of $N$ objects. In this context our results recover and extend known results. In contrast, the statistical properties of cycles in undirected 2-RRGs have not been studied before.
Similar papers 1
November 30, 2017
We present analytical results for the distribution of shortest cycle lengths (DSCL) in random networks. The approach is based on the relation between the DSCL and the distribution of shortest path lengths (DSPL). We apply this approach to configuration model networks, for which analytical results for the DSPL were obtained before. We first calculate the fraction of nodes in the network which reside on at least one cycle. Conditioning on being on a cycle, we provide the DSCL o...
September 18, 2003
We study directed random graphs (random graphs whose edges are directed), and present new results on the so-called strong components of those graphs. We provide analytic and simulation results on two special classes of strong component, called cycle components and knots, which are important in random networks that represent certain computational systems.
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...
March 21, 2004
We study the distribution of cycles of length h in large networks (of size N>>1) and find it to be an excellent ergodic estimator, even in the extreme inhomogeneous case of scale-free networks. The distribution is sharply peaked around a characteristic cycle length, h* ~ N^a. Our results suggest that h* and the exponent a might usefully characterize broad families of networks. In addition to an exact counting of cycles in hierarchical nets, we present a Monte-Carlo sampling a...
August 31, 2020
We study the set ${\cal L}(G)$ of lengths of all cycles that appear in a random $d$-regular $G$ on $n$ vertices for a fixed $d\geq 3$, as well as in Erd\H{o}s--R\'enyi random graphs on $n$ vertices with a fixed average degree $c>1$. Fundamental results on the distribution of cycle counts in these models were established in the 1980's and early 1990's, with a focus on the extreme lengths: cycles of fixed length, and cycles of length linear in $n$. Here we derive, for a random ...
August 27, 2004
Structural properties of evolving random graphs are investigated. Treating linking as a dynamic aggregation process, rate equations for the distribution of node to node distances (paths) and of cycles are formulated and solved analytically. At the gelation point, the typical length of paths and cycles, l, scales with the component size k as l ~ k^{1/2}. Dynamic and finite-size scaling laws for the behavior at and near the gelation point are obtained. Finite-size scaling laws ...
March 7, 2020
Let $L$ be subset of $\{3,4,\dots\}$ and let $X_{n,M}^{(L)}$ be the number of cycles belonging to unicyclic components whose length is in $L$ in the random graph $G(n,M)$. We find the limiting distribution of $X_{n,M}^{(L)}$ in the subcritical regime $M=cn$ with $c<1/2$ and the critical regime $M=\frac{n}{2}\left(1+\mu n^{-1/3}\right)$ with $\mu=O(1)$. Depending on the regime and a condition involving the series $\sum_{l \in L} \frac{z^l}{2l}$, we obtain in the limit either a...
March 7, 2010
Following the derivation of the trace formulae in the first paper in this series, we establish here a connection between the spectral statistics of random regular graphs and the predictions of Random Matrix Theory (RMT). This follows from the known Poisson distribution of cycle counts in regular graphs, in the limit that the cycle periods are kept constant and the number of vertices increases indefinitely. The result is analogous to the so called "diagonal approximation" in Q...
December 18, 2003
We discuss various aspects of the statistical formulation of the theory of random graphs, with emphasis on results obtained in a series of our recent publications.
March 24, 2006
We apply in this article (non rigorous) statistical mechanics methods to the problem of counting long circuits in graphs. The outcomes of this approach have two complementary flavours. On the algorithmic side, we propose an approximate counting procedure, valid in principle for a large class of graphs. On a more theoretical side, we study the typical number of long circuits in random graph ensembles, reproducing rigorously known results and stating new conjectures.