{'fraction_non_alphanumeric': 0.03165195460277428, 'fraction_numerical': 0.006809583858764187, 'mean_word_length': 4.26593625498008, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Eigenvalues of random graphs with cycles

Networks and graphs are often studied using the eigenvalues of their adjacency matrix, a powerful mathematical tool with applications on fields as diverse as systems engineering, ecology, machine learning and neuroscience. As in those applications the exact graph structure is not known, researchers resort to random graphs to obtain eigenvalue properties from known structural features. However, this theory is not intuitive and only few results are known. In this paper we tackle this problem through the cycles in a graph. We start by deriving a simple relation between eigenvalues and cycle weights, and we apply it to two types of random graphs: Circulant graphs, where we give a bound for the eigenvalue moduli, and random graphs with cyclic motifs, where we give axes of symmetry. During this study we empirically uncover to surprising phenomena: First, circulant directed networks have eigenvalues distributed in concentric circles around the origin. Second, the eigenvalues of a network with abundance of short cycles are confined to the interior of a k-ellipse –an ellipse with k foci– in the complex plane, where k is the length of the cycles. We conclude by showing that this framework is still valid for networks with connection delays. Our approach offers an intuitive way to study eigenvalues on graphs and in doing so reveals surprising connections between random matrix theory and planar geometry. Networks and graphs are a very flexible modeling tool that has been successfully applied to fields as diverse as engineering[12], neuroscience[13], biology[8] or social sciences [7]. Of particular importance in those studies are the spectral methods, a family of tools that use the eigenvalues of the adjacency matrix of the graph. In the case of complex systems with many interacting elements, the actual graph is not known, and therefore we must estimate those eigenvalues in order to use spectral methods. Researchers in that area usually resort to spectral random matrix theory, a mathematical field where the distribution of eigenvalues is studied from the characteristics of their entries [4]. However, this approach often requires a deep understanding of probability theory [14]. In this work we argue that using the structure of the graph can yield interesting results without need for complex mathematical techniques. Specifically, we focus on the cycles embedded in the network structure. Our intuition is that an eigenvalues represent, as the etymology of the term suggests, a connection from every node to itself.

Networks and graphs are a very flexible modeling tool that has been successfully applied to fields as diverse as engineering [12], neuroscience [13], biology [8] or social sciences [7]. Of particular importance in those studies are the spectral methods, a family of tools that use the eigenvalues of the adjacency matrix of the graph. In the case of complex systems with many interacting elements, the actual graph is not known, and therefore we must estimate those eigenvalues in order to use spectral methods. Researchers in that area usually resort to spectral random matrix theory, a mathematical field where the distribution of eigenvalues is studied from the characteristics of their entries [4]. However, this approach often requires a deep understanding of probability theory [14]. In this work we argue that using the structure of the graph can yield interesting results without need for complex mathematical techniques. Specifically, we focus on the cycles embedded in the network structure. Our intuition is that an eigenvalues represent, as the etymology of the term suggests, a connection from every node to itself.
The rest of this paper is organized as follows: We derive the connection between cycles in a graph and the eigenvalues of its adjacency matrix. Then we use it to compute a bound on the largest eigenvalue of circulant directed graphs. Afterwards we study random graphs with circular motifs. Finally we propose a potential extension to networks with delays.
For a given weighted directed graph G(N, E) with N nodes and E edges we define the normalized weight of the cycles of length L where P L (n 1 , n 2 ) is the set of paths from node n 1 to node n 1 , and w p = ∏ e∈p w(e), the multiplication of weights of the edges e in path p. Since the value ∑ p∈P L (i,i) w p is given by the entries of the power of the graphs' adjacency matrix M, we can obtain c L from the adjacency matrix M, where tr [·] is the trace operator. Since the trace of a matrix is the sum of its eigenvalues, c L can be written as, where λ n is the nth eigenvalue of the adjacency matrix M.
We will now look at two examples applications of this equation. For simplicity, we will consider graphs where the absolute value of the weights of the edges is constant but the edges are signed. We start by studying directed circulant graphs [6], where every node n is connected to d subsequent nodes n + 1, n + 2, ... n + d for n ∈ Z/NZ, as shown in Fig. 1.
In its simplest case, this corresponds to a directed network with a single cycle. We can see that c k = 0 for all k < N, and c N = ∏ N n=1 w n,n+1 . The solutions for this set of equations are the Nth roots of c N . In the case c L > 0, where i is the imaginary unit, and in our case | N √ c N | = 1. If c L < 0 the phase is shifted by π N .
For d > 1, we can study the value of the largest eigenvalues by a combinatorial argument. Consider the limit L → ∞, where the eigenvalue with the largest modulus, the so-called spectral radius, dominates the rest. The right hand side of Eq. 3 then becomes, where a is a constant and comes from the fact that more than one eigenvalue may have the largest possible moduli. On the right hand side of Eq. 3, we can use Eq. 1 to write c L as a binomial distribution where w p are picked from {−1, 1} with equal probability. This means that c L can be approximated by a normal distribution N (0, σ 2 L ) where where the values of P L (n, n) can be obtained recursively, Notice that when L becomes large, P L (n, n) ∼ P L (n − 1, n), therefore, P L (n, n) ∼ P L (n − 1, n) ⇒ P L (n, n) ∼ dP L−1 (n, n).
Furthermore, in a normal distribution the maximum value sampled is on the order of magnitude of the standard deviation σ L , and for any finite number of samples (here, N), where b is a constant. By putting together Eq. 5 and 6, which gives us the bound In Fig 2 we observe that this the value that we obtained is indeed close to the actual distribution. However, the results presented are more interesting than what this combinatorial argument suggest; it seems that the eigenvalues of the adjacency matrix of a directed circulant graph are distributed in concentric circles around the origin whose number increases with the degree as ⌈ d 2 ⌉. Furthermore, we observe that for degree two there is a particular shape within the concentric circle. Since a circulant graph can be used to model a wave propagating through a onedimensional lattice with periodic boundary conditions [2] and the scattering and propagation properties of waves are studied with spectral tools [1], this result might be interesting for physicists working on wave propagation in random media.
The second interesting case concerns the eigenvalue distribution of random directed graphs where short cycles of certain length are overrepresented. This feature is usually studied under the umbrella of network motifs [9].
Before doing that, however, we must present some known results on random matrix theory.
Consider an N × N matrix with random entries sampled from a given probability distribution, but with a variance that is constant for all values of N. As the number of dimensions N goes to infinity, the eigenvalues of that matrix can be considered as random variables sampled from a probability distribution in the complex plane. We focus on random matrix W where the entries W mn of the matrix are drawn from a probability distribution with the following properties: nm is finite • There is a non-zero correlation between symmetric entries E [W nm W mn ] = ρ 2 = 0 By the elliptic law of random matrices [11,5] the corresponding distribution of eigenvalues in the complex plane is given by where x r stands for the real part of x and x i for the imaginary part. That law simply means that the eigenvalues are uniformly distributed on an ellipse parametrized by ρ 2 .
Ellipse Foci Ellipse axis Figure 3: Regular 2-ellipse and 3-ellipse: For the 2 and three ellipse, the sum of the distance of every point (red) to the foci (blue) is constant. In regular τ-ellipses, the foci are at a constant distance from the center and have inclinations 2πk τ , ∀0 ≤ k < τ with respect to the horizontal line. As as a simple consequence of the symmetries between foci, there are axis of symmetry (dotted lines) passing though the center and with inclinations πk τ , ∀0 ≤ k < τ. In all k-ellipses the closest and furthest points to the center correspond to the intersects of the axis with the curve.
Consider now large random graphs with d edges per node with a fraction of edges α being in cycles of length τ with weight sign s, which we can construct in the following way: • Begin with a graph with N nodes and no edges.
• Independently select sets of τ distinct nodes n 1 , n 2 , ..., n τ with probability proportional to d − d(n k ) where d(n k ) is the degree of node n k (note that at this stage the in and out degrees are equal). Create edges n k → n k+1 and n τ → n 1 until a dNα edges are created.
• For every set, associate signs {−1, 1} with equal probability to the first τ − 1 edges, and pick the last sign such that the multiplication of signs is s • Independently select pairs of nodes n in and n out with probability proportional to their in-and out-degree respectively and create edges n in → n out until the graph has dN edges.
• Associate a weights {− 1 √ d , 1 √ d } to each edge according to its sign. For τ = 2, those graphs fulfill all the conditions for the elliptic law to hold (see Fig.4). This corresponds to a random graph where cycles of length τ = 2 with positive feedback are overrepresented. Furthermore, in the limit where the number of entries grows to infinity, This formulation of the elliptic law of random matrices in terms of cycles raises a question: what if we consider cycles of length τ > 2? The first thing to notice is that there would be a correlation between sets of τ entries in the adjacency matrix, ρ τ = E W n 1 n 2 ...W n k n k+1 ...W n τ n 1 which can, analogously, be given by As we see in Fig.4, those eigenvalues have a very regular distribution. Specifically, for cycles of length τ they seem to be uniformly distributed in a region delimited by a regular τ-ellipse, a curve where the sum of the distances to τ foci is constant. We can describe it by where D is the sum of the distances to the foci and v is the distance from the center to the foci. Those are the only two parameters for the curve, so we only need two non-symmetric points in the curve to determine them. In the case τ = 2, we know from Eq.9 that the ellipse intercepts its axis of symmetry at distances 1 + ρ 2 and 1 − ρ 2 from the center which correspond to the furthest and closest point (see Fig. 3). We hypothesize that this can be generalized in regular τ-ellipses by saying that the curve intercepts its axis of symmetry at distances 1 + ρ τ and 1 − ρ τ . This allows us to recover the parameters D, v and obtain the complete curve, which matches with the empirical eigenvalue distribution (see Fig. 4). From the construction of a τ ellipse (see Fig. 3) we see that τ-elliptic distributions contain symmetries, and we proceed now to explain them using Eq.3. As the values of c L converge to their expectations, Conversely, as the number of edges goes to infinity, the average value of the eigenvalues to the power of k also converges to its expected value, which we can write in an integral form where µ k stands for the kth moment of the probability density function p τ,ρ (λ ) of eigenvalues for a random graph with parameters τ, ρ. By Eq. 3, and from Eq. 11, we know that only the moments multiple of τ are non-zero. Furthermore, all moments converge, therefore the moment generating function is well defined. Consider now the probability density function which is nothing else than a rotation of the original probability in the complex plane by an angle of θ . Naturally, the associated moments µ θ k can be calculated as a function of the original µ k , therefore, when θ = 2π τ k, then µ k = µ θ k . This means that p θ τ,ρ (λ ) and p τ,ρ (λ ) have the same moments and are, therefore, are the same (note that this is valid as long as all moments are finite). This corresponds to k rotational symmetries Furthermore, all the entries of the adjacency matrix are real, and this means that p θ τ,ρ (λ ) is symmetric with respect to the real line. Combine that with the symmetries from Eq. 13 and we conclude that the distribution of eigenvalues has τ axis of symmetry.
This result has an easy interpretation in terms of control engineering. The cycles in the graph correspond to feedback loops with a delay of τ, meaning that they enhance or dampen the response of the system -represented by the adjacency matrix of a graphafter τ iterations [3]. In the space of eigenvalues, this is reflected by the dominant eigenvalues which have phases θ = 2π τ k ∀k ∈ N, if the feedback is positive and θ = 2π τ k + π τ if the feedback is negative.
We can also use the relationship between cycles and spectra to study networks with heterogeneous connection delays, a common problem encountered in real world systems [3]. When the edges of a network have delays on top of their weight, the adjacency matrix is not defined, and thus we cannot obtain their eigenvalues and eigenvectors directly. However, by interpreting delays as lengths, the cycles in the graph are still defined and therefore Eq. 3 holds. This is analogous to creating an equivalent network where all delays are one by adding extra nodes in the middle of the edges. Consider the simple example in Fig.5, where both networks have eigenvalues This simple example will be familiar to electrical engineers, as this is analogous to the Figure 5: A network with a heterogeneous delays labeled by d, and its equivalent graph with a virtual node represented by a circle with a dashed line.
conceptual description of an Infinite Impulse Response (IIR) filter where the poles of the transfer function correspond to the eigenvectors of the graph [10].
To summarize, in this work we show that the notion of cycle in a graph is fundamentally connected to the eigenvalues of its adjacency matrix. This leads us to a two main results for large networks: First, the spectrum of a random signed circulant directed graph has most of its eigenvalues concentrated in concentric circles around the origin but within a circle of radius √ d where d is the degree. Second, that the eigenvalues of a matrix with abundance of short cycles has its eigenvalues uniformly distributed in τ-ellipses in the complex plane where τ is the length of the overrepresented cycle. Finally, that the use of cycles can extend the notion of eigenvalue to networks with delays.
Our results, albeit mathematical in nature, are empirical, so we expect that they will inspire further theoretical research by mathematicians and physicists. Conversely, graph spectra are of critical importance to study many real world systems, and therefore this is interesting for applied scientists working on fields where networks are used. Finally, we want to emphasize that, besides the direct extensions or continuations of or work, in this study we show that graph spectra can be studied through their cycles in a simple and intuitive way, and it can make spectral graph theory more accessible.