Spectra of random graphs with given expected degrees

The Random Graph Model

The primary model for classical random graphs is the Erdos–Rényi model , in which each edge is independently chosen with the probability P for some given P > 0 (see ref. 15). In such random graphs the degrees (the number of neighbors) of vertices all have the same expected value. Here we consider the following extended random-graph model for a general degree distribution (also see refs. 16 and 17).

For a sequence w = (w ₁, w ₂,..., w _n), we consider random graphs G(w) in which edges are independently assigned to each pair of vertices (i, j) with probability w _i w _jρ, where Notice that we allow loops in our model (for computational convenience), but their presence does not play any essential role. It is easy to verify that the expected degree of i is w _i.

To this end, we assume that max_i w_i ²<Σ_k such that p_ij ≤ 1 for all i and j. This assumption insures that the sequence w _i is graphical [in the sense that it satisfies the necessary and sufficient condition for a sequence to be realized by a graph (18) except that we do not require the w _i values to be integers]. We will use d _i to denote the actual degree of v _i in a random graph G in G(w), where the weight w _i denotes the expected degree.

For a subset S of vertices, the volume Vol(S) is defined as the sum of weights in S and vol(S) is the sum of the (actual) degrees of vertices in S. That is, Vol(S) = Σ_{i ∈ S} w _i and vol(S) = Σ_{i ∈ S} d _i. In particular, we have Vol(G) = Σ_i w _i, and we denote ρ = 1/Vol(G). The induced subgraph on S is a random graph G(w′), where the weight sequence is given by w_i′=w_i Vol(S)ρ for all i ∈ S. The expected average degree is w̄=w_i/n=1/(nρ). The second-order average degree of is . The maximum expected degree is denoted by m.

The classical random graph can be viewed as a special case of by taking w to be (pn, pn,..., pn). In this special case, we have d̃ = w̄ = m = np. It is well known that the largest eigenvalue of the adjacency matrix of G(n, p) is almost surely [1 + o(1)]np provided that np » log n.

The asymptotic notation is used under the assumption that n, the number of vertices, tends to infinity. All logarithms have the natural base.

Spectra of the Adjacency Matrix of Random Graphs with Given Degree Distribution

For random graphs with given expected degrees (w ₁, w ₂,..., w _n), there are two easy lower bounds for the largest eigenvalue of the adjacency matrix A, namely, and .

It has been proven∥ that the maximum of the above two lower bounds is essentially an upper bound (also see ref. 19).

Theorem 1. If , then the largest eigenvalue of a random graph in G(w) is almost surely .

Theorem 2. If , then almost surely the largest eigenvalue of a random graph in G(w) is . If the kth largest expected degree m_k satisfies , then almost surely the largest k eigenvalues of a random graph in G(w) is .

Theorem 3. The largest eigenvalue of a random graph in G(w) is almost surely at most

We remark that the largest eigenvalue of the adjacency matrix of a random graph is almost surely if is >d̃ by a factor of log² n, and is almost surely [1 + o(1)]d̃ if is <d̃ by a factor of log n. In other words, is (asymptotically) the maximum of and d̃ if the two values of and d̃ are far apart (by a power of log n). One might be tempted to conjecture that This, however, is not true as shown by a counterexample given previously (10).

We also note that with a more careful analysis the factor of log n in Theorem 3 can be replaced by (log(n))^1/2+ε and the factor of log² n can be replaced by (log(n))^3/2+ε for any positive ε provided that n is sufficiently large. We remark that the constant “7” in Theorem 3 can be improved. We made no effort to get the best constant coefficient here.

Eigenvalues of the Adjacency Matrix of Power-Law Graphs

In this section we consider random graphs with power-law degree distribution with exponent β. We want to show that the largest eigenvalue of the adjacency matrix of a random power- law graph is almost surely approximately the square root of the maximum degree m if β > 2.5 and is almost surely approximately cm ^3–β if 2 < β < 2.5. A phase transition occurs at β = 2.5. This result for power-law graphs is an immediate consequence of a general result for eigenvalues of random graphs with arbitrary degree sequences.

We choose the degree sequence w = (w ₁, w ₂,..., w _n) satisfying w _i = ci ^{–1/(β–1)} for i ₀ ≤ i ≤ n + i ₀. Here c is determined by the average degree, and i ₀ depends on the maximum degree m, namely, It is easy to verify that the number of vertices of degree k is proportional to k ^–β.

The second-order average degree d̃ can be computed as follows. We remark that for β > 3, the second-order average degree is independent of the maximum degree. Consequently, the power-law graphs with β > 3 are much easier to deal with. However, many massive graphs are power-law graphs with 2 < β < 3, in particular, Internet graphs (9) have exponents between 2.1 and 2.4, whereas the Hollywood graph (6) has exponent β ≈ 2.3. In these cases, it is d̃ that determines the first eigenvalue. Theorem 4 is a consequence of Theorems 1 and 2. When β > 2.5, the ith largest eigenvalue σ _i is for σ _i sufficiently large. These large eigenvalues follow the power-law distribution with exponent 2β – 1. (The exponent is different from one in Mihail and Papadimitriou's unpublished work, because they use a different definition for power law.)

Theorem 4.

1. For β ≥ 3 and m > d ²log^3+ε n, almost surely the largest eigenvalue of the random power-law graph G is .

2. For 2.5 < β < 3 and m > d ^{(β–2)/(β–2.5)}log^3/(β–2.5) n, almost surely the largest eigenvalue of the random power-law graph G is .

3. For 2 < β < 2.5 and m > log^3/2.5–β n, almost surely the largest eigenvalue is [1 + o(1)]d̃.

4. For k < (d/m log n)^β–1 n and β > 2.5, almost surely the k largest eigenvalues of the random power-law graph G with exponent β have power-law distributions with exponent 2β – 1, provided that m is large enough (satisfying the inequalities in 1 and 2).

Spectrum of the Laplacian

Suppose G is a graph that does not contain any isolated vertices. The Laplacian L is defined to be the matrix L = I – D ^–1/2 AD ^–1/2, where I is the identity matrix, A is the adjacency matrix of G, and D denotes the diagonal degree matrix. The eigenvalues of L are all nonnegative between 0 and 2 (see ref. 20). We denote the eigenvalues of L by 0 = λ₀ ≤ λ₁ ≤... λ_{n - 1}. For each i, let ϕ_i denote an orthonormal eigenvector associated with λ_i. We can write L as L = Σ_i λ_i P _i, where P _i denotes the i projection into the eigenspace associated with eigenvalue λ_i. We consider For any positive integer k, we have Lemma 1. For any positive integer k, we have

The matrix M can be written as where ϕ₀ is regarded as a row vector , ϕ*₀ is the transpose of ϕ₀, and K is the all 1s matrix.

Let W denote the diagonal matrix with the (i, i) entry having value w _i, the expected degree of the ith vertex. We will approximate M by where χ is a row vector . We note that ∥χ*χ ^- ϕ*ϕ∥ is strongly concentrated at 0 for random graphs with given expected degree w _i. C can be seen as the expectation of M, and we shall consider the spectrum of C carefully.

A Sharp Bound for Random Graphs with Relatively Large Minimum Expected Degree

In this section we consider the case when the minimum of the expected degrees is not too small compared to the mean. In this case, we are able to prove a sharp bound on the largest eigenvalue of C.

Theorem 5. For a random graph with given expected degrees w ₁,..., w _n where , we have almost surely

Proof: We rely on the Wigner high-moment method. For any positive integer k and any symmetric matrix C which implies where λ₁ is the eigenvalue with maximum absolute value: |λ₁| = ∥C∥.

If we can bound E(Trace(C ^2k)) from above, then we have an upper bound for E(λ₁(C)^2k). The latter would imply an upper bound (almost surely) on |λ₁(C)| via Markov's inequality provided that k is sufficiently large.

Let us now take a closer look at Trace(C ^2k). This is a sum where a typical term is c _{i 1 i 2} c _{i 2 i 3},..., c _{i 2 k - 1 i 2 k} c _{i 2 k i 1}. In other words, each term corresponds to a closed walk of length 2k (containing 2k, not necessarily different, edges) of the complete graph K _n on {1,..., n} (K _n has a loop at every vertex). On the other hand, the entries c _ij of C are independent random variables with mean zero. Thus, the expectation of a term is nonzero if and only if each edge of K _n appears in the walk at least twice. To this end, we call such a walk a good walk. Consider a closed good walk that uses l different edges e ₁,..., e _l with corresponding multiplicities m ₁,..., m _l (the m _h values are positive integers at least 2 summing up to 2k). The (expected) contribution of the term defined by this walk in E(Trace(C ^2k)) is In order to compute , let us first describe the distribution of with probability p _ij = w _i w _jρ and with probability q _ij = -1 -p _ij. This implies that for any m ≥ 2, Here we used the fact that in the first inequality (the reader can consider this fact an easy exercise) and the definition p _ij = w _i w _jρ in the second equality.

Let W _{l , k} denote the set of closed good walks on K _n of length 2k using exactly l + 1 different vertices. Notice that each walk in W _{l , k} must have at least l different edges. By Eqs. 1 and 2, the contribution of a term corresponding to such a walk toward E(Trace(C ^2k)) is at most

It follows that In order to bound the last sum, we need the following result of Füredi and Komlós (9).

Lemma 2. For all l < n,

In order to prove Theorem 5, it is more convenient to use the following cleaner bound, which is a direct corollary of Eq. 4. Substituting Eq. 5 into 3 yields Now fix k = g(n)log n, where g(n) tends to infinity (with n) arbitrarily slowly. With this k and the assumption about the degree sequence, the last sum in Eq. 6 is dominated by its highest term. To see this, let us consider the ratio s _{k , k}/s _{l , k} for some l ≤ k + 1: where in the first inequality we used the simple fact that With a proper choice of g(n), the assumption guarantees that , where Ω(1) tends to infinity with n, which implies . Consequently, Because E(λ₁(C)^2k) ≤ E(Trace(C ^2k)) and ρn = 1/w̄, we have By Eq. 7 and Markov's equality Because k = Ω(log n), we can find an ε = ε(n) tending to 0 with n such that n/(1 + ε)^2k = o(1), which implies that almost surely as desired. The lower bound on |λ₁(C)| follows from the semicircle law proved in the next section.

The Semicircle Law

We show that if the minimum expected degree is relatively large, then the eigenvalues of C satisfy the semicircle law with respect to the circle of radius centered at 0. Let W be an absolute continuous distribution function with (semicircle) density for |x| ≤ 1 and w(x) = 0 for |x| > 1. For the purpose of normalization, consider . Let N(x) be the number of eigenvalues of C _nor < x and W _n(x) = n^–1 N(x).

Theorem 6. For random graphs with a degree sequence satisfying , W_n(x) tends to W(x) in probability as n tends to infinity.

Remark: The assumption here is weaker than that of Theorem 5 due to the fact that we only need to consider moments of constant order.

Proof: Because convergence in probability is entailed by the convergence of moments, to prove this Theorem 6 we need to show that for any fixed s, the sth moment of W _n(x) (with n tending to infinity) is asymptotically the sth moment of W(x). The sth moment of W _n(x) equals . For s even, s = 2k, the sth moment of W _x is (2k)!/2^{2 k}k!(k + 1)! (see ref. 10). For s odd, the sth moment of W _x is 0 by symmetry.

In order to verify Theorem 6, we need to show that for any fixed k and

We first consider Eq. 8. Let us go back to Eq. 3. Now we need to use the more accurate estimate of |W _{l , k}| given by Eq. 4 instead of the weaker but cleaner one in Eq. 5. Define One can check, with a more tedious computation, that the sum is still dominated by the last term, namely It follows that . On the other hand, E(Trace(C ^2k)) ≥ W _{k , k}|ρ^k. Now comes the important point, for l = k, |W _{l , k}| is not only upper-bounded by but in fact equals the right-hand side of Eq. 4. Therefore, It follows that which implies Eq. 8.

Now we turn to Eq. 9. Consider a term in Trace(C ^2k+1). If the closed walk corresponding to this term has at least k + 1 different edges, then there should be an edge with multiplicity one, and the expectation of the term is 0. Therefore, we only have to look at terms with walks that have at most k different edges (and at most k + 1 different vertices). It is easy to see that the number of closed good walks of length 2k + 1 with exactly l + 1 different vertices is at most O(n ^l+1). The constant in O depends on k and l (recall that now k is a constant), but for the current task we do not need to estimate this constant. The contribution of a term corresponding to a walk with at most l + 1 different edges is bounded by . Thus E(Trace(C ^2k+1)) is upper-bounded by for some constant c. To compute the (2k + 1)th moment of W _n(x), we need to multiply E(Trace(C ^2k+1)) by the normalizing factor

It follows from Eq. 4 that the absolute value of the (2k + 1)th moment of W _n(x) is upper-bounded by Under the assumption of the theorem . Thus, the last sum in Eq. 11 is o(1), completing the proof.

Summary

In this article we prove that the Laplacian spectrum of random graphs with given expected degrees follows the semicircle law, provided some mild conditions are satisfied. We also show that the spectrum of the adjacency matrix is essentially determined by its degree distribution. In particular, the largest k eigenvalues of the adjacency matrix of a random power-law graph follow a power-law distribution, provided that the largest k degrees are large in terms of the second-order average degree. Here we compute the spectra of a subgraph G of a simulated random power-law graph with exponent 2.2. The graph G has 588 vertices with the average degree w̄ = 43.88 and the second average degree d̃ = 61.5804. The largest eigenvalue of its adjacency matrix is 61.78, which is very close to the second-order average degree d̃, as asserted by Theorem 1 (see Fig. 1). All the nontrivial eigenvalues of the Laplacian are within from 1, as predicted by Theorems 5 and 6 (see Fig. 2).