IEICE TRANS. COMMUN., VOL.E104–B, NO.3 MARCH 2021

251

PAPER

Wigner’s Semicircle Law of Weighted Random Networks
Yusuke SAKUMOTO†a) , Member and Masaki AIDA††b) , Fellow

SUMMARY Spectral graph theory provides an algebraic approach toinvestigate the characteristics of weighted networks using the eigenvalues
and eigenvectors of a matrix (e.g., normalized Laplacian matrix) that represents the structure of the network. However, it is difficult to accurately
represent the structures of large-scale and complex networks (e.g., social
network) as a matrix. This difficulty can be avoided if there is a universality,
such that the eigenvalues are independent of the detailed structure in largescale and complex network. In this paper, we clarify Wigner’s Semicircle
Law for weighted networks as such a universality. The law indicates thatthe eigenvalues of the normalized Laplacian matrix of weighted networks
can be calculated from a few network statistics (the average degree, average
link weight, and square average link weight) when the weighted networks
satisfy a sufficient condition of the node degrees and the link weights.
key words: random matrix theory, Wigner’s semicircle law, spectral graphtheory, Laplacian matrix, network analysis

1.

Introduction

Many networks such as railway networks, social networks,
the Internet, and airport networks are modeled as weighted
networks that are composed of nodes and weighted links [1]–[3]. The weighting of links is important in network modeling, but it is a tedious task in the case of large-scale and complex networks, such as social networks. In a social network,
nodes and links correspond to persons and their relationships, respectively. To assign the correct weight to each linkin the social network, the strength of the relationships amongpeople should be accurately estimated from a huge amountof personal data (e.g., communication histories in mobile
phones and social media). Owing to the risk of breachingprivacy and the associated computational complexity, it isunrealistic to gather such personal data, and calculate thestrength of the relationships accurately.
Spectral graph theory provides an algebraic approach
to investigate the characteristics of weighted networks using the eigenvalues and the eigenvectors of a matrix (e.g.,
normalized Laplacian matrix) that represents the structureof the network [4], [5]. In particular, the eigenvalues areimportant to understand the characteristics related to the entire network on the basis of spectral graph theory. In [6], itManuscript received April 1, 2020.
Manuscript revised August 11, 2020.
Manuscript publicized September 1, 2020.
† The author is with Kwansei Gakuin University, Sanda-shi,
669-1337 Japan.
†† The author is with Tokyo Metropolitan University, Hino-shi,
191-0065 Japan.
a) E-mail: sakumoto@kwansei.ac.jpb) E-mail: aida@tmu.ac.jp
DOI: 10.1587/transcom.2020EBP3051

has been demonstrated that the eigenvalue distribution of thenormalized Laplacian matrix affects the information dissemination speed throughout the social network. In general, theeigenvalues of the matrix are calculated from all the matrix
elements. The elements of the matrix representing the structure of a weighted network are determined by the weights on
the links. Hence, the weighting of the links is required to apply spectral graph theory for weighted networks. This would
deter the application of spectral graph theory for large-scaleand complex networks. However, the weighting of the links
is avoidable if there is a universality that the eigenvalues
are independent of the detailed structure (e.g., the weight ofeach link) of large-scale and complex networks. Therefore,
finding of such a universality of the eigenvalues expands theapplicable region of spectral graph theory.
Random matrix theory discusses a universality of theeigenvalues if the elements of the matrix are given by random variables [7]–[9]. In [9], Chung et al. analyzed therandom matrix corresponding to the normalized Laplacianmatrices of unweighted networks, and have confirmed theuniversality (Wigner’s semicircle law) that the eigenvaluesof the normalized Laplacian matrix follow the semicircle
distribution. In [6], it was investigated whether Wigner’s
semicircle law [9] of unweighted networks is satisfied forweighted networks, through numerical experiments. However, the condition of weighted networks satisfying Wigner’s
semicircle law was not explicitly furnished, and the width ofthe eigenvalue distribution (spectral radius) was not found.
Hence, the universality for weighted networks is not fully
understood. Given the available literature, no study has
elucidated the universality of the eigenvalues for weighted
networks.
In this paper, the universality (Wigner’s semicircle law)of the eigenvalues is presented for weighted networks on thebasis of the discussion of [9]. Our findings include (a) a sufficient condition for weighted networks to satisfy Wigner’s
semicircle law and (b) an expression of the spectral radiusof the eigenvalue distribution. According to the derived
expression, the spectral radius determines the eigenvalue
distribution of the normalized Laplacian matrix of weighted
networks, and is calculated from a few network statistics (theaverage degree, average link weight, and square average linkweight). Hence, the eigenvalues can be obtained from a few
network statistics when the weighted networks satisfy thesufficient condition of the node degrees and the link weights.
Using some numerical examples, the validity of the sufficientcondition is confirmed.

Copyright © 2021 The Institute of Electronics, Information and Communication Engineers

IEICE TRANS. COMMUN., VOL.E104–B, NO.3 MARCH 2021

252

This paper is organized as follows. In Sect. 2, spectral
graph theory and the random matrix theory for weighted
networks is described. In Sect. 3, Wigner’s semicircle law
for weighted networks is proved on the basis of the randommatrix theory. Section 4 shows some numerical examples.
Finally, in Sect. 6, we conclude this paper and discuss the
future work.
2.

Preliminary

spectral radius r by r := max2≤l ≤n |1 − λ l |. Spectral radiusr satisfies 0 < r < 1 because 0 < λ l < 2 for 2 ≤ l ≤ n.
Eigenvector q1 of minimum eigenvalue λ 1 is given by
q1 = √p p
p T1( d 1, d 2, ..., d n ) ,Vol(G)

where Vol(G) is defined by
X
Vol(G) :=
di .

(6)

(7)

i ∈G

2.1

Spectral Graph Theory

In spectral graph theory, the structure of a network is represented by a matrix, and the characteristics of the network
are investigated using its eigenvalues and eigenvectors. In
this section, we describe spectral graph theory for weighted
networks.
We denote a weighted network by G = (V, E, w) where
V and E are the sets of nodes and links, respectively. Letn be the number of nodes in G. The link between nodes iand j is denoted by (i, j). Link (i, j) has the weight w (i, j)
where w (i, j) = w ( j, i) and w (i, j) > 0. Let ∂i be the set ofadjacent nodes of node i. The weighted degree d i of nodes
i is defined byX
d i :=w (i, j).
(1)
j ∈∂i

To represent the structure of links and nodes in G, there
are adjacency and degree matrices, A and D, respectively.
The (i, j)-th element A(i, j) of adjacency matrix A is definedby w (i, j)
A(i, j) := 0
if (i, j) ∈ E.
otherwise(2)

Degree matrix D is defined by
D := diag(d i )1≤i ≤n .

(3)

To represent both the structure of nodes and links in G, a normalized Laplacian matrix N is often used. The normalized
Laplacian matrix N is defined by
N := I − D−1/2 AD−1/2,(4)where I is the identity matrix.
Since a normalized Laplacian matrix N is symmetric (N = NT ), its eigenvalues λ l (l = 1, ..., n) are real numbers. Let ql be the eigenvector of eigenvalue λ l where
qlT ql = 1. We assign a number to λ l in ascending order, andhence λ l refers to the l-th minimum eigenvalue of N . The
range of the eigenvalues is given by
0 = λ 1 < λ 2 ≤ ... ≤ λ n < 2.

(5)

If λ 2 > 0, the weighted network G is connected (i.e., there is
at least one path between every pair of nodes). The weighted
network G is not a bipartite graph, if λ 2 < 2. We define theSince the eigenvectors ql is an orthonormal basis, matrix
Q = (ql )1≤k ≤n is the orthogonal matrix (Q−1 = QT ).
Using Q and Λ = diag(λ l )1≤k ≤n , the normalized Laplacian matrix N is given by
N = QΛQT =nX

λ l ql qTl .

(8)

l=1

From the above equation, N is determined by eigenvalues(λ l )1≤l ≤n and eigenvectors (ql )1≤l ≤n . Hence, the weighted
network G can be analyzed not only with N but also with
its eigenvalues and eigenvectors. Spectral graph theory provides an algebraic method for analyzing G with eigenvalues
λ l and eigenvectors ql of N . In particular, the eigenvalues
λ l are important to understand the statistical characteristics
related to the entirety of the weighted network G. In orderto calculate eigenvalues λ l , in general, all elements N (i, j)
must be given accurately. However, if there is a useful universality of eigenvalues λ l , we can investigate the statisticalcharacteristics of the weighted network G without all elements N (i, j).
2.2

Random Matrix Theory

Random matrix theory focuses on random matrices whose
the elements are given by random variables, and clarifies thata universality of the eigenvalues appears if the matrix size
approaches infinity. When the links and their weights in theweighted network G are randomly given with a stochastic
rule, elements N (i, j) of the normalized Laplacian matrix N
become random variables, and N can be treated as a randommatrix. Note that the universality of eigenvalues λ l of N
corresponds to a characteristic of the statistical ensembleof the random networks generated with the same stochastic
rule. Hence, clarifying such a universality contributes to thegrowth of the statistical mechanics on networks.
In [9], the link between nodes i and j in an unweighted
network is randomly generated using the stochastic rule withrandom variable L i j . If L i j = 0, there is no link between
nodes i and j. On the other hand, if L i j = 1, a linkf existsg
between nodes i and j. We denote probability P L i j = 1
by pi j , which is given bypi j = ρ σi σ j ,(9)where σi > 0 and ρ = 1/ i ∈V σi . Using Eq. (9), the expectation of the node i’s degree is given by σi . Let σavg ,P

SAKUMOTO and AIDA: WIGNER’S SEMICIRCLE LAW OF WEIGHTED RANDOM NETWORKS

253

σmin , and σmax be the average degree, the minimum degree,and P
the maximum degree. These are defined by σavg :=1/n i ∈V σi , σmin := inf i ∈V σi , and σmax := supi ∈V σi ,respectively. We can write ρ as ρ = 1/(n σavg ). Similar2
to [9], it is assumed that σmax
< 1/ρ, so that pi j ≤ 1. Using
the above stochastic rule, special networks (e.g., networks
with no links) are rarely generated. The probability of generating such special networks is very small, and therefore,
this stochastic rule poses no problem in the discussion of auniversality appearing when n → ∞.
In the weighted network G, the weight of the link (i, j) is
randomly set using the stochastic rule with random variable
W . In the stochastic rule, the random variable W follows
the conditional probability density function f W |Li j (w | l),which is defined byfg
f W |Li j (w | l) dw := P w ≤ W ≤ w + dw | L i j = l .
(10)
If L i j = 0 (i.e., link (i, j) does not exist), W is always 0, andhence f W |Li j (w | 0) = δ(w) where δ(x) is the Dirac delta
function. On the contrary, if L i j = 1, then W > 0. Since linkweights in actual networks cannot be infinity, it is assumed
that W is bounded. Using a finite value wmax , W ≤ wmax .
For convenience, we writepW (w) := f W |Li j (w | 1).
(11)
Let E pW W m  be the m-th moment of W with the condition
L i j = 1. E pW W m is defined by
Z wmax
w m pW (w) dw.
(12)
E pW W m :=0

Even if the weights of all links in G are divided by wmax , thenormalized Laplacian matrix N remains invariant. Hence,
without loss of generality, m  we assume wmax = 1. With
this assumption,
E
has the following properties:pW W (a) E pW Wl ≤ E fW W m for l > m, and (b) E pW W m ≤ 1
0since E pW W = 1.
Following the above stochastic rules, not only elements
N (i, j) but also the eigenvalues λ l (l = 2, ..., n) of the normalized Laplacian matrix N for the weighted network G
become random variables depending on the set of randomvariables Γ = (L, W ) where L = (L i j )(i, j) ∈V 2 . Let Λ be therandom variable for eigenvalue λ of N . We denote the conditional eigenvalue density of eigenvalues λ l (l = 2, ..., n) of(n)N by f Λ|Γ
(λ | γ), which is defined by
(n)
f Λ|Γ
(λ | γ) :=n1 Xδ (λ − λ l ) ,n − 1 l=2(13)where λ l is the function of γ. Since eigenvalues λ l vary(n)stochastically, conditional eigenvalue density f Λ|Γ
(λ | γ)(n)is also a random variable. Note that f Λ|Γ
(λ | γ) can betreated as a conditional probability density function because
R λn (n)f Λ|Γ (λ | γ) dλ = 1. Using probability P Γ = γ ,λ2eigenvalue density f Λ(n) (λ) of N is given by (n)(λ | γ)f Λ(n) (λ) = EP[Γ] f Λ|Γ
=

n
X
1 X 
P Γ=γ
δ (λ − λ l ) .
n−1 γ
l=2

(14)

Rλ
Since λ n f Λ(n) (λ) dλ = 1, f Λ(n) (λ) can be also treated as
2
a probability density function. Then, we denote the m-th
moment for 1 − Λ using f Λ(n) (λ) by E f (n) (1 − Λ) m , whichΛ
is defined byZ λnE f (n) (1 − Λ) m :=(1 − λ) m f Λ(n) (λ) dλ
Λ

λ2

"X
#
n
1
m
EP[Γ]
(1 − λ l ) .
=
n−1
l=2

(15)

Using the approach of the random matrix theory, theprevious work [9] has established the universality (Wigner’s
semicircle law) that the eigenvalue density f Λ(n) (λ) for unweighted networks follows a certain distribution (i.e., semicircle distribution). If such a universality exists even for
the weighted network G, eigenvalue density f Λ(n) (λ) can beobtained without giving link weights w (i, j) correctly. This
allows the analysis of G based on spectral graph theory even
if G is a large-scale and complex network, such as social
network.
3.

Wigner’s Semicircle Law of Weighted Network G

In this section, we probe Wigner’s semicircle law for aweighted network G on the basis of the discussion in [9].
Wigner’s semicircle law for G is as follows:
Theorem. If the weighted network G satisfies the degree
condition
σavg
2
(16)
σmin

 ,
E pW W 2f Λ(n) (λ) of the normalized Laplacian matrix N converges toa semicircle distribution f˜Λ (λ) as n → ∞. A semicircle
distribution f˜Λ (λ) is given by
q

2


r̃ 2 − (1 − λ) 2 1 − r̃ < λ < 1 + r̃2f˜Λ (λ) = 
,
π
r̃


0
otherwise
(17)
where r̃ is the limit value of spectral radius r as n → ∞, andis given byq 
E pW W 22r̃ = √(18)  .
σavg E pW W
Remark. When the links in G are not weighted,
  W is always 1 if L i j = 1, and hence E pW W = E pW W 2 = 1. By

IEICE TRANS. COMMUN., VOL.E104–B, NO.3 MARCH 2021

254

substituting them into Eqs. (16) and (18), we obtain Wigner’s
semicircle law for unweighted networks shown in [9]. Therefore, it can be generalized to a weighted network G.
The degree condition (16) means that σmin is sufficiently
large in a weighted network G, and is necessary to satisfy
Eqs. (45) and (58) in the proof. How easily Eq. (16) holds,
depends on the value of σmin . If σmin is large, it is easy tosatisfy Eq. (16).
According to the degree distribution of the Facebook
friend network reported in [10], the minimum and the average degrees
 of Facebook users are 1 and 190, respectively.
Since E pW W 2 is smaller than 1, Eq. (16) is not satisfied forthe friend network of Facebook users. Note that the survey in[10] targeted all Facebook users who logged in May 2011,
and includes not only frequent Facebook users but also infrequent ones. According to [11], frequent users of Facebook
tend to have many friends. Hence, the induced subgraphof the frequent Facebook users would have a minimum degree large enough to satisfy Eq. (16). Since the frequent
users mainly disseminate information in social networks, theanalysis of such an induced subgraph is important to understand the characteristics of the information dissemination.
Analysis of the induced subgraph of frequent users in actualSNSs will be done as part of a future study. In this analysis,
we obtain the degrees of SNS users with the node sampling
method [12], and use the obtained degree as σi .
Equation (17) implies that the width of the eigenvalue distribution of the normalized Laplacian matrix N
becomes large as r̃ increases. From Eq. (18), r̃ is determined  by the network statistics (σavg , E pW W 2 , and E pW W 2 ).
  
In particular, if relative variance E pW W 2 /E pW W 2 increases, r̃ increases. Hence, there is the relationship between the width of the eigenvalue distribution and rela  tive variance E pW W 2 /E pW W 2 . According to the analysis in [7], r̃ of the semicircle distribution increases, as
the variance of the non-diagonal elements of the matrix
considering Wigner’s semicircle law increases. As rela  tive variance E pW W 2 /E pW W 2 increases, the varianceof the non-diagonal elements of the normalized Laplacianmatrix N also increases. Thus, the relationship between
the width of the eigenvalue distribution and relative vari  ance E pW W 2 /E pW W 2 expressed in Eqs. (17) and (18) is
derived.

 
Since E f˜Λ Λ = 1, the above moments for 1 − Λ correspondto the central moments of Λ. The following are equivalent:
1. As n → ∞, eigenvalue density f Λ(n) (λ) converges tosemicircle distribution f˜Λ (λ).

2. As n → ∞, even moment E f˜Λ (1 − Λ) 2m and odd
moment E f˜Λ (1 − Λ) 2m+1 converge to Eqs. (19) and(20), respectively.
To prove Wigner’s semicircle law for a weighted network G,
we show that 2. is fulfilled if the degree condition (16) issatisfied.
For convenience, we use matrix M after removing theeffect of minimum eigenvalue λ 1 from normalized Laplacianmatrix N . Matrix M is defined by
M :=

n
X

(1 − λ l ) ql qTl = I − N − q1 qT1

l=2= D−1/2 AD−1/2 −1
D1/2 K D1/2,
Vol(G)(21)

where K is the matrix with all elements given by 1, andcorresponds to the adjacency matrix for the complete graphincluding self-loops at all nodes. Matrix M has n−1 nonzero
eigenvalues, and the l-th largest eigenvalue is given by 1− λ l .
Hence
n

 X

(1 − λ l ) m .
Tr M m =

(22)

l=2

By substituting the above equation into Eq. (15), we obtain
E f (n) (1 − Λ) m =
Λ


 
1
EP[Γ] Tr M m .
n−1

(23)

 
Since E pW W is finite, the weighted degree  d i of thenode i converges
toits
expectedvalue
EP[Γ] d i as n → ∞.
EP[Γ] d i is given by  X
EP[Γ] d i =pi j E fW | L i j W | L i j = 1
j ∈V



+(1 − pi j )E fW | L i j W | L i j = 0X =pi j E pW W
j ∈V

Proof. If eigenvalue density f Λ(n) (λ) is given by a semicircle
distribution f˜Λ (λ), even moment E f˜Λ (1 − Λ) 2m and odd
moment E f˜Λ (1 − Λ) 2m+1 for 1 − Λ are given by
E f˜Λ (1 − Λ) 2m =Z 1+r̃

(1 − λ) 2m f˜Λ (λ) dλ1−r̃

 r̃  2m(2 m)!
,(19)
2
m! (m + 1)!
Z 1+r̃
(1 − λ) 2m+1 f˜Λ (λ) dλE f˜Λ (1 − Λ) 2m+1 =
=

1−r̃

= 0.

(20)

 X
= E pW W
ρ σi σ jj ∈V = E pW W σi .

(24)

Note that pi j = ρ σi σj was used to derive the above equation.
By substituting EP[Γ] d i into Eq. (21), we obtain matrix C,
which is given byC=1  σ −1/2 Aσ −1/2 − ρ σ 1/2 K σ 1/2,
E pW W(25)

where σ = diag(σi )1≤i ≤n . As
 n → ∞, matrix M converges
to matrix C, since d i = EP[Γ] d i . Since Wigner’s semicircle

SAKUMOTO and AIDA: WIGNER’S SEMICIRCLE LAW OF WEIGHTED RANDOM NETWORKS255

law discusses the limit theorem where n → ∞, the proof isvalid if C is used instead of M.
Element C(i, j) of matrix C is a random variable, andis given by
wi j
√


− ρ σi σ j
 √


E
W
σ
σ
i j
C(i, j) =  pW
 −ρ√σ σi jif L i j = 1.
otherwise(26)


Let EP[Γ] C m (i, j) be the m-th
momentof C(i, j). Specifi
cally, the 1st moment EP[Γ] C(i, j) is given byEP[Γ] C(i, j)#"W√= pi j E fW | L i j− ρ σi σ j L i j = 1 √
E pW W σi σ j"#√+ (1 − pi j )E fW | L i j ρ σi σ j L i j = 0
= 0.

(27)



For m ≥ 2, the m-th moment EP[Γ] C(i, j) m is bounded byEP[Γ] C m (i, j)
!m
#
"
W
√
= pi j E fW | L i j
Li j = 1− ρ σi σ j √E pW W σi σ j
#
"
m
√
+ (1 − pi j )E fW | L i j ρ σi σ j L i j = 0
m−2
X



!
m (−pi j ) l E pW W m−ll E pW W  m−l (σi σ j ) m/2
l=0


m−2
X m!
(−ρ) l E pW W m−l=ρl E pW W  m−l (σi σ j ) m/2−l−1l=0ρ E pW W m=(1 + o(1))
 E pW W m (σi σ j ) m/2−1
ρ E pW W m≤(1 + o(1)) .
 m−2
E pW W m σmin

= pi j(28)

lim f (n) = 0.

(29)

(30)

v m ∈Φ n, m

X

h(v
m)
Y

C(el ) ml ,of disjoint links, el is the l-th link, and ml is the occurrence
number of link el . In particular, ml satisfies
h(v
m)
X

ml = m.

(31)v m ∈Φ n, m l=1

where vm = (v1, v2, v3, ..., vm ) represents a cycle of length min the complete graph with n nodes, and Φn,m is the set ofthe cycles with length m. In cycle vm , h(vm ) is the number

(32)

l=1

where (i, j) and ( j, i) are treated as the same link in a cycle
when counting ml since C is a symmetric matrix.
Figure 1 shows the example of the complete graph with
4 nodes. For example, Φ4,6 includes v6 = (1, 2, 3, 1, 2, 3). In
cycle v6 , h(v6 ) = 3, e2 = (2, 3) and m2 = 2.
From Eq. (23) and M ≈ C, the m-th moment E f (n) (1 −ΛΛ) m is approximated by
E f (n) (1 − Λ) m ≈Λ  
1EP[Γ] Tr C m .
n−1

(33)

As n → ∞, the error of the approximation
approaches to 0.
m ] in order to prove that
Hence,
we
investigate
E
Tr[C
P[Γ]


E f (n) (1 − Λ) m converges to Eqs. (19) and (20) as n → ∞.
ΛTo show the convergence of even moments E f (n) (1 −
Λ
f
g



Λ) 2m , we investigate EP[Γ] Tr C 2m . Using the indepeng fdence of C(i, j), an even moment EP[Γ] Tr C 2m is bounded
by
X

h(v
m)
Y



EP[Γ] C(el ) mlv m ∈Φ n,2m l=1 E pW W 2 l E pW W 2(m−l) ρl(1 + o(1))
 
2m−2l
E pW W 2m σmin
l=0
 
m
X
E pW W 2 l ρl≤
| Zl,m |(1 + o(1)) ,
(34)
 
2m−2l
E pW W 2m σmin
l=0≤

The m-th moment Tr[C m ] is given byX 
Tr C m =C(v1, v2 )C(v2, v3 ) ... C(vm, v1 )=The complete graph with 4 nodes.

g fEP[Γ] Tr C 2m =To derive the above equation, the term with l = 0 in the sum
since ρ = 1/(n σavg ) = 1/σ(n) = o(1) was retained. Notethat σ( f (n)) is a function that increases faster than or equal
to f (n) as n → ∞. Then, we use f (n) = o(1) asn→∞Fig. 1m
X| Zl,m |where Zl,m is a set of cycles (v1, v2, ..., v2m ) with length 2mand disjoint l + 1 nodes. Note that Zl,m ⊂ Φn,2m . For example, (1, 2, 3, 1, 2, 3) is included in Z2,3 . The cycles includedin Zl,m are composed of at least l disjoint links. To derive
the second right-hand side of the above equation, we firstdivide all cycles in Φn,2m into the sets Zl,m of the cycles thatthe number of disjoint links is l. Each set has | Zl,m | cycles.
Using Eq. (29), for vm ∈ Zl,m , we obtain
h(v
m)
Y

 l



 E p W 2 E pW W 2(m−l) ρl,
EP[Γ] C(el ) ml ≤ W
 
2m−2l
E pW W 2m σmin
l=1
(35)

IEICE TRANS. COMMUN., VOL.E104–B, NO.3 MARCH 2021

256

 
since that E pW W 2 is the largest in the m-th moments
E pW W m for m ≥ 2. In the first right-hand side ofEq. (34), the reason why the cycles longer than  m are
not considered, is as follows. First, EP[Γ] C(i, j) = 0.
Qh(v m )Hence, l=1
EP[Γ] C(el ) ml is 0 except if ml ≥ 2 for1 ≤ l ≤ h(vm ). Since ml ≥ 2 for 1 ≤ l ≤ h(vm ), thenumber of links l in the cycle is at most fm. gTo extract the main term of EP[Γ] Tr C 2m , we rewrote
Eq. (34) with
m
m
X
g X
η l,m
 f
η l,m = η m,mEP[Γ] Tr C 2m ≤,η
l=1
l=1 m,m(36)

where η l,m is 
E pW W 2 l ρl
η l,m = | Zl,m |
.
 
2m−2l
E pW W 2m σmin(37)

| Zl,m | = | Z a (l, m)| | Zb (l, m)| | Zc (l, m)|
!
!
2m
1 2l
n!
(l + 1) 4 (m−l),=(n − l − 1)! 2l
l+1 l
(38)
where Z a (l, m) is the number of permutations (i k )1≤k ≤l+1
by selecting l + 1 nodes from n nodes, and is given byn!
.
(n − l − 1)!

!
η l,m(n − m − 1)! 2m(l + 1) 4(m−l)=η m,m(n − l − 1!) 2l
2l 
 l


m + 1 l E pW W 2 E pW W 2m−2l ρl
2m 2 m m
2m−2l E
l+1
σmin
ρ
pW W
m
! l−m
2m n (l + 1) 4(m−l) 4l−m≤
2l σ 2(m−l) E pW W 2  m−l ρm−lminnl−m 2 m2(m−l) m4(m−l) 4l−m 2(m−l)σmin
E pW W 2 m−l ρm−l
 m−l
σavg m6
.
≤2
 2  2 E
 4 σminpW W 

≤

(43)

η

l, m
To obtain the upper bound of ηm,, the Stirling’s approxim
mation was used, and is given by√
2 πnn+1/2 e−n ≤ n! ≤ nn+1/2 e−n+1 .
(44)

In the above equation, | Zl,m | is given by| Z a (l, m)| =ηl, mThen, ηm,in (36) is bounded bym(39)Then, | Zb (l, m)| is the number of combinations such thateach i k appears more than once in the cycle with length 2mand is given by
!
!

2m 
2m
2 2(m−l)| Zb (l, m)| =(l + 1)=(l + 1) 4(m−l) .
2l
2l
(40)

According to the following discussion, if the degree condition is satisfied, the right-hand side of Eq. (43) for m > lbecomes o(1). First, for m > l, we derive m−l
σavg m6= o(1).
 2  2 E
 4 σminpW W 

(45)

To prove the above equation, we should show
σavg m6 2  = o(1).
2 E
4 σminpW W(46)Similarly for [9], using m = log n, we obtain the condition
2σmin= σ((log n) 6 )

σavg
 ,
E pW W 2(47)

In the above equation, since there is no restriction exceptthat each i k must appear at least twice, it is multiplied by(l + 1) 4(m−l) . Moreover, Zc (l, m) is the number of the second appearance positions for i k and is given by
!
1 2l
.
(41)
| Zc (l, m)| =l+1 l

to satisfy Eqs. (45) and (46). The condition (47) is the sameas the degree condition (16).
Therefore, if the degree condition (16) is satisfied, form > l, we obtain

Note that the right side of the above equation is the Catalan
number.
By substituting Eq. (38) into Eq. (37), η l,m is given by 
E pW W 2 l ρl
η l,m = | Zl,m |
 
2m−2l
E pW W 2m σmin
!
n!
2m
=
(l + 1) 4(m−l)(n − l − 1)! 2l !
E pW W 2 l ρl
1 2l
. (42)
l + 1 l E pW W  2m σ 2m−2lmin

By substituting theabove
g  equation into Eq. (36), the upper fbound of EP[Γ] Tr C 2m is given byη l,m= o(1).
η m,m

(48)

g
 f
EP[Γ] Tr C 2m ≤ (1 + o(1)) η m,m .

(49)

g
 f
On the other hand, the lower bound of EP[Γ] Tr C 2m
is given byg fEP[Γ] Tr C 2m =

X

h(v
m)
Y



EP[Γ] C(el ) mlv m ∈Φ n, m h=1≥ | Zm,m |EP[Γ] C(i, j) 2 m

SAKUMOTO and AIDA: WIGNER’S SEMICIRCLE LAW OF WEIGHTED RANDOM NETWORKS

257≥ | Zm,m | ρm

 
E pW W 2 m  (1 − o(1))
E pW W 2m= (1 − o(1)) η m,m .

where

0
η l,m
= | Zl,m |(50)Note that the second right-hand side of the above equation
was obtained by only using the cycles with disjoint m links.
To derive the third right-hand side, we used 
Ep W 2EP[Γ] C(i, j) 2 ≥ ρ W   2 (1 − o(1)).
(51)
E pW W
This can be derived from Eq. (28).
g f
According to Eqs. (36) and (50), EP[Γ] Tr C 2m isbounded byg fη m,m (1 − o(1)) ≤ EP[Γ] Tr C 2m ≤ η m,m (1 + o(1)).
(52)
As n → ∞, the even moment E f (n) (1 − λ) 2m converges to
lim E f (n) (1 − λ)

n→∞

2m 

Λ

g
 f
1
EP[Γ] Tr C 2m
= lim
n→∞ n − 1

1 ± o(1)
= lim
η m,m
n→∞ n − 1
 m!
1 2m E pW W 2 ρm
n!
= lim
 
n→∞ (n − 1)(n − m − 1)! m + 1 m
E pW W 2m
 !
E pW W 2 m
12m= lim g(n)  2m m + 1 m
m E
n→∞
σavg
pW W
 
!
E pW W 2 m
12m=
  2m m + 1 m
m E
σavg
pW W
 r̃  2m (2 m)!
=
,
(53)
2
m! (m + 1)!

 
E pW W 2 l−1 ρl(1 + o(1)) .
 
2m−2l
E pW W 2m+1 σmin

(56)

Using a method analogous to the one for the even moment,
0 /(σ
0
η l,m
min η m,m ) is bounded byq  m−l+1/2
4 E pW W 2 σavg m6


≤
q


0
2
2 
σmin η m,m
σavg m3  4 σmin E pW W 0
η l,m m−l+1/2
q
σavg m6 2  .
≤ 4 E pW W 
 2  2 E
 4 σminpW W 
(57)
If the degree condition (16) is satisfied, for m ≥ l, we obtain m−l+1/2
σavg m6= o(1).
 2  2 E
 4 σminpW W 

Λ

0
h=1 mh = 2m + 1, and η l,m is given by

Pl

(58)

g
 f
Hence, the upper bound of 1/(n − 1)EP[Γ] Tr C 2m+1 isgiven byg f
1o(1) 0EP[Γ] Tr C 2m+1 ≤η.
n−1
n − 1 m,m(59)

As n → ∞, the right-hand side of the above equation converges too(1) 0lim
η=0n→∞ n − 1 m,m

(60)



Hence, as n → ∞, the odd moment E f (n) (1 − Λ) 2m+1 isΛgiven by
o(1) 0lim E f (n) (1 − Λ) 2m+1 = lim
ηn→∞ n − 1 m,mΛ= 0.

where g(n) is defined byn→∞g(n) :=n!
.
(n−1)(n−m−1)! nm(54)

Note that limn→∞ g(n) = 1.
Therefore, if a weighted network G satisfiesg  the degree
 fcondition (16), the even moment EP[Γ] Tr C 2m converges
to E f˜Λ (1 − λ) 2m as n → ∞.
g f
Next, we investigate the odd moment EP[Γ] Tr C 2m+1 .
g f
Similar to the even moment EP[Γ] Tr C 2m ,g fEP[Γ] Tr C 2m+1 is bounded byg fEP[Γ] Tr C 2m+1 =

X

h(v
m)
Y



EP[Γ] C(el ) mlv m ∈Φ n,2m+1 l=1

 
E pW W 2 l−1 ρl(1 + o(1))
 
2m−2l+1
E pW W 2m+1 σmin
l=0
0
m
m η0
X
X
η l,m
l,m
0
*
+,
≤
= η m,m
(55)
0
σ
σ
η
min
min
m,m
l=0 ,
l=0

≤

m
X

(61)

Therefore, if a weighted network G satisfies the degreecondition (16), the odd moment also converges to E f˜Λ (1 −Λ) 2m+1 as n → ∞.
4.

Numerical Example

We confirm the validity of the degree condition (16) andEq. (18) in Wigner’s semicircle law for a weighted network
G derived in Sect. 3. For brevity, we only show the results
using the BA model [13], which is a well-known random
network generation model.
Similar to [6], we generate a weighted network G withthe following procedures, based on the BA model.

| Zl,m |1. Generate an unweighted network with n nodes and avBA , according to the BA model.
erage degree σavg
2. Randomly cut the links of the unweighted network until

IEICE TRANS. COMMUN., VOL.E104–B, NO.3 MARCH 2021

258
Table 1

Parameter configuration.

(B A)
Average degree of unweighted BA network, σavg
Number of nodes of the weighted network G, nAverage degree of the weighted network G, σavg
Pareto index of the Pareto distribution, αNumber of bins, nh

40
1,000
20
3
50

the average degree is σavg . This procedure prevents
minimum degree σmin from being fixed, and does not
lose the scale-free property of the BA network [6].
3. Randomly assign the weight of each link
 using theparPareto distribution pW (w) with E pW W = 1. Noteparthat pW (w) ∝ α w −α−1 .
Fig. 2

4. Divide the weight of each link by the maximum linkweight wmax . By performing this procedure, the linkweight is lesser than or equal to 1, and its distribution satisfies the condition of pW (w) used in Sect. 3.
Note that this procedure does not change the normalized Laplacian matrix N .

2 .
Average degree σavg vs. the square of the minimum degree, σmin

In order to confirm the validity of the degree condition (16) in Wigner’s semicircle law for a weighted network
G, we compare eigenvalue density f Λ(n) (λ) of the normalized
Laplacian matrix N and semicircle distribution f˜Λ (λ). To
evaluate their difference, we use the relative error  d , which
is defined byn d :=h1 X|Fn (θ i ) − F ∗ (θ i )|,nh i=1
F (θ i )(62)

where θ i = (i − 1/2)hb + λ 2 and hb = (λ n − λ 2 )/nh . In (62),Fn (θ i ) is the value obtained by dividing the number of eigenvalues of N in the interval [θ i − hb /2, θ i + hb /2] by n − 1.
On the contrary, F ∗ (θ i ) is the value of the integral of f˜Λ (λ)
within [θ i − hb /2, θ i + hb /2].
To confirm the validity of Eq. (18), we compare thespectral radius r of the normalized Laplacian matrix N andr̃ calculated by Eq. (18). For these comparisons, we use
relative error  r , which is defined by r :=|r̃ − r |
.
r

(63)

In the numerical example, the parameter configuration
shown in Table 1 is used as a default parameter configuration.
First, we confirm the relationship between the characteristics of the weighted network G generated in the above
procedure and the degree condition (16). Figure 2 shows the2square of the minimum degree, σminfor varying values of
average degree σavg . Additionally, in this figure, we plot theresults with the average order σavg on the y axis for comparison. From these results, as σavg increases, the difference
2 and σbetween σminavg increases, and hence the degree condition (16) isreadily satisfied. Figure 3 shows the second
moment E pW W 2 of link weights for varying values of the
Pareto index α. From this figure, as α increases, E pW W 2
increases, and hence the degree condition (16) is also readily

Fig. 3Second moment E pW W 2 for different pareto indices α.

satisfied.
Figures 4(a) and (b) show eigenvalue density f Λ(n) (λ)
of the normalized Laplacian matrix N (i.e, Fn (θ)) and semicircle distribution f˜Λ (λ). For reference, we show the resultsof all link weights w (i, j) = 1 in Fig. 4(c). According to
the results, eigenvalue density f Λ(n) (λ) for α = 5 is closer
to semicircle distribution f˜Λ (λ) than that for α = 3. Thisis consistent with the result of E pW W 2 shown in Fig. 3.
Hence, we visually confirm the validity of the degree condition (16).
Figure 5 shows the relative error  d of eigenvalue density f Λ(n) (λ) for different average degrees σavg . In this figure,
we also show the result for all link weights w (i, j) = 1 forreference. Since n is finite, relative error  d is not 0. We assume that if the relative error  d is almost equal to the result
for w (i, j) = 1, f Λ(n) (λ) converges to f˜Λ (λ) as n → ∞. From
the results in Fig. 5, the relative error  d decreases as average
degree σavg increases, or as the Pareto index α increases.
The result is consistent with the results shown in Figs. 2 and3. Hence, the degree condition (16) is valid. Moreover, therelative error  d for α = 5 is almost the same as the thatfor w (i, j) = 1. Hence, if α ≥ 5, f Λ(n) (λ) follows Wigner’s
semicircle law.

SAKUMOTO and AIDA: WIGNER’S SEMICIRCLE LAW OF WEIGHTED RANDOM NETWORKS

259

Fig. 5 Relative error d of eigenvalue density fΛ(n) (λ) for different valuesof average degree σavg .

Fig. 6 Spectral radius r and r̃ calculated from Eq. (18) for different average degrees σavg .

Fig. 4 Eigenvalue density fΛ(n) (λ) of the normalized Laplacian matrix
N (i.e, Fn (θ)) and semicircle distribution f˜Λ (λ).

Figure 6 shows spectral radius r and r̃ calculated from
Eq. (18) for different average degree σavg . In this figure, we
also plot the result for all link weights w (i, j) = 1 for reference. From Fig. 6, the spectral radius r almost coincides
with r̃ except for α = 3. Hence, spectral radius r can be calculated accurately using Eq. (18) if the degree condition (16)Fig. 7 Relative error r of r̃ calculated from Eq. (18) for different average
degrees σavg .

is satisfied.
Figure 7 shows the relative error  r of r̃ calculated from
Eq. (18) for different average degrees σavg . In this figure,the result of all link weights w (i, j) = 1 is also plotted forreference. According to Fig. 7, it is clear that relative error

IEICE TRANS. COMMUN., VOL.E104–B, NO.3 MARCH 2021

260

 r is small when the degree condition (16) is met, as withthe result shown in Fig. 5. Hence, Eq. (18) is valid as theapproximate expression of the spectral radius r.
From the above results, we conclude that the degree
condition (16) and Eq. (18) derived in Sect. 3 are valid.

spectral radius r increases. From the results shown in thispaper and [6], the relationship between the power law in thelink weight distribution and the information dissemination
time can be understood.
6.

5.

Conclusion and Future Work

Related Work and Discussion

In [14], [15], weighted spectral distribution (WSD) was used
to analyze a network G with the eigenvalue distribution of
the normalized Laplacian matrix N . In [16], a method was
proposed to accelerate the calculation of WSD. WSD is given
by a set of nd elements calculated from the eigenvalues of
N , and it is specifically defined by(1 − θ i ) m FG (λ = θ i ) θ i ∈ Ωi, 1 ≤ i ≤ K ,(64)
where FG (λ) is the number of the eigenvalues in the interval
including λ among nd intervals equally spaced in (0, 2]. In
the above equation, m is a positive integer, and Ωi is thei-th interval (2(i − 1)/nd, 2i/nd for 1 ≤ i ≤ nd . In [14],[15], on the basis of WSD, distance δ m (G1, G2 ) between two
networks G1 and G2 is given byδ m (G1, G2 ) =KX(1−θ i ) m FG1(λ = θ i )−FG2(λ = θ i ) 2 .

i=1

In this paper, we clarified Wigner’s semicircle law for aweighted network G on the basis of random matrix theory.
This law indicates that if G with n nodes satisfies the degree condition (16), the eigenvalue density of the normalized
Laplacian matrix N converges to the semicircle distribution
determined by the approximated spectral radius r̃, as n → ∞.
Using Eq. (18), we can calculate r̃ from a few network statistics (the average degree, average link weight, and square
average link weight). Hence, the eigenvalue distribution of
N can be obtained from these network statistics without giving all the matrix elements N (i, j) accurately. Our results
provide a new method to analyze a weighted network G using
spectral graph theory and random graph theory.
Analyzing and designing actual networks using
Wigner’s semicircle law, as clarified in this paper, is aninteresting future study. In particular, the characteristics of
the information dissemination on social networks will be investigated, and they can aid the design of the social media tocontrol the speed of the information dissemination.

(65)
Acknowledgments
In [15], the characteristics of the Internet topology were clarified using the distance δ m (G1, G2 ). In this paper, we expounded upon the universality, that the eigenvalue distribution of N follows the semicircle distribution if the weighted
network G satisfies the degree condition (16). The universality supplied in this paper can be applied to the analysisof WSD. For example, the semicircle distribution is used as
the standard eigenvalue distribution, and we define the measure using the distance between the eigenvalue distributionof the weighted network G and the semicircle distribution asin Eq. (65). Such a measure would be useful to analyze thespecialty of the weighted network G.
A power law is a property that appears in various actual
networks. In many studies (e.g., [17], [18]), the relationship between the power law and network characteristics has
been analyzed. In [17], the first passage time of a random walk was investigated in weighted scale-free networks,
where node degrees, link weights and weight degree follow
a power-law distribution. The analysis result showed that theeffect of the power law on the first passage time of a random
walk. In [18], the first meeting time of two random walks
was analyzed. It was shown that the first meeting time issmall when node degrees follow the power-law distribution.
In Sect. 4, a numerical example was shown using a weighted
BA network where link weights follow the power-law distribution (Pareto distribution). According to the results shownin Fig. 6, spectral radius r decreases as index α of the powerlaw distribution increases. In [6], the information dissemination time in social networks was shown to increase as theThis work was supported by JSPS KAKENHI Grant Number
17H01737.
References[1] C. Shi, Y. Li, J. Zhang, Y. Sun, and S.Y. Philip, “A survey of heterogeneous information network analysis,” IEEE Trans. Knowl. Data
Eng., vol.29, no.1, pp.17–37, Aug. 2016.
[2] J. Feng, X. Li, B. Mao, Q. Xu, and Y. Bai, “Weighted complex
network analysis of the Beijing subway system: Train and passenger flows,” Physica A: Statistical Mechanics and its Applications,vol.474, pp.213–223, Jan. 2017.
[3] X. Sun, V. Gollnick, and S. Wandelt, “Robustness analysis metrics
for worldwide airport network: A comprehensive study,” Chinese
Journal of Aeronautics, vol.30, no.2, pp.500–512, Feb. 2017.
[4] F.R. Chung and F.C. Graham, Spectral Graph Theory, American
Mathematical Soc., no.92, May 1997.
[5] D.A. Spielman, “Spectral graph theory and its applications,” Proc.
48th Annual IEEE Symposium on Foundations of Computer Science(FOCS’07), pp.29–38, Oct. 2007.
[6] Y. Sakumoto, T. Kameyama, C. Takano, and M. Aida, “Information propagation analysis of social network using the universality of
random matrix,” IEICE Trans. Commun., vol.E102-B, no.2, pp.391–
399, Feb. 2019.
[7] E.P. Wigner, “On the distribution of the roots of certain symmetricmatrices,” Annals of Mathematics, vol.67, no.2, pp.325–327, 1958.
[Online]. Available: http://www.jstor.org/stable/1970008[8] V. Plerou, P. Gopikrishnan, B. Rosenow, L.A. N. Amaral, T. Guhr,and H.E. Stanley, “Random matrix approach to cross correlations in financial data,” Phycal Review E, vol.65, p.066126,
June 2002. [Online]. Available: https://link.aps.org/doi/10.1103/
PhysRevE.65.066126

SAKUMOTO and AIDA: WIGNER’S SEMICIRCLE LAW OF WEIGHTED RANDOM NETWORKS

261[9] F. Chung, L. Lu, and V. Vu, “Spectra of random graphs with given expected degrees,” the National Academy of Sciences, vol.100, no.11,
pp.6313–6318, Feb. 2003.
[10] J. Ugander, B. Karrer, L. Backstrom, and C. Marlow, “The anatomyof the Facebook social graph,” arXiv preprint arXiv:1111.4503, Nov.
2011.
[11] E.J. Vanman, R. Baker, and S.J. Tobin, “The burden of online friends:
The effects of giving up Facebook on stress and well-being,” J. Soc.
Psychol., vol.158, no.4, pp.496–508, April 2018.
[12] M. Gjoka, M. Kurant, C.T. Butts, and A. Markopoulou, “Practical
recommendations on crawling online social networks,” IEEE J. Sel.
Areas Commun., vol.29, no.9, pp.1872–1892, Sept. 2011.
[13] A.L. Bárabasi and R. Albert, “Emergence of scaling in random networks,” Science, vol.286, no.5439, pp.509–512, Oct. 1999.
[14] D. Fay, H. Haddadi, S. Uhlig, A.W. Moore, R. Mortier, and A. Jamakovic, “Weighted spectral distribution,” University of Cambridge,
Computer Laboratory, Technical Report, UCAM-CL-TR-729, Sept.
2008. [Online]. Available: https://www.cl.cam.ac.uk/techreports/
UCAM-CL-TR-729.pdf[15] D. Fay, H. Haddadi, A. Thomason, A.W. Moore, R. Mortier, A. Jamakovic, S. Uhlig, and M. Rio, “Weighted spectral distribution forinternet topology analysis: Theory and applications,” IEEE/ACM
Trans. Netw., vol.18, no.1, pp.164–176, Feb. 2010.
[16] B. Jiao, Y.-p. Nie, J.-m. Shi, G. Lu, Y. Zhou, and J. Du, “Accurately and quickly calculating the weighted spectral distribution,”
Telecommun. Syst., vol.62, no.1, pp.231–243, May 2016.
[17] Z. Zhang, X. Guo, and Y. Yi, “Spectra of weighted scale-free networks,” Scientific Reports, vol.5, p.17469, Dec. 2015.
[18] Y. Sakumoto and H. Ohsaki, “Graph degree heterogeneity facilitates
random walker meetings,” arXiv preprint arXiv:2005.11161, May
2020.

Yusuke Sakumotoreceived M.E. and Ph.D.
degrees in the Information and Computer Sciences from Osaka University in 2008 and 2010,
respectively. From 2010 to 2019, he was a associate professor of Tokyo Metropolitan University. He is currently an associate professor at
Kwansei Gakuin University. His research work
is in the area of communication network, electricity network, and social network. He is amember of the IEEE, IEICE and IPSJ.

Masaki Aida
received his B.S. degree inPhysics and M.S. degree in Atomic Physics from
St. Paul’s University, Tokyo, Japan, in 1987 and1989, respectively, and his Ph.D. in Telecommunications Engineering from the University ofTokyo, Japan, in 1999. In April 1989, he joined
NTT Laboratories. From April 2005 to March
2007, he was an Associate Professor at Tokyo
Metropolitan University. He has been a Professor of the Graduate School of Systems Design,
Tokyo Metropolitan University since April 2007.
His current interests include analysis of social network dynamics and distributed control of computer communication networks. He received the Best
Tutorial Paper Award and the Best Paper Award of IEICE Communications
Society in 2013 and 2016, respectively, and IEICE 100-Year Memorial Paper Award in 2017. He is a fellow of IEICE and a member of the IEEE,
ACM and ORSJ.