VOL. E102-B NO. 2
FEBRUARY 2019
The usage of this PDF file must comply with the IEICE Provisions
on Copyright.
The author(s) can distribute this PDF file for research andeducational (nonprofit) purposes only.
Distribution by anyone other than the author(s) is prohibited.

IEICE TRANS. COMMUN., VOL.E102–B, NO.2 FEBRUARY 2019

391

PAPER

Information Propagation Analysis of Social Network Using
the Universality of Random Matrix
Yusuke SAKUMOTO†a) , Member, Tsukasa KAMEYAMA††b) , Nonmember, Chisa TAKANO†††c) ,and Masaki AIDA†d) , Members

SUMMARY Spectral graph theory gives an algebraic approach to theanalysis of the dynamics of a network by using the matrix that represents the
network structure. However, it is not easy for social networks to apply thespectral graph theory because the matrix elements cannot be given exactly torepresent the structure of a social network. The matrix element should be seton the basis of the relationship between persons, but the relationship cannot
be quantified accurately from obtainable data (e.g., call history and chathistory). To get around this problem, we utilize the universality of randommatrices with the feature of social networks. As such a random matrix, we
use the normalized Laplacian matrix for a network where link weights are
randomly given. In this paper, we first clarify that the universality (i.e., theWigner semicircle law) of the normalized Laplacian matrix appears in the
eigenvalue frequency distribution regardless of the link weight distribution.
Then, we analyze the information propagation speed by using the spectral
graph theory and the universality of the normalized Laplacian matrix. As
a result, we show that the worst-case speed of the information propagation
changes up to twice if the structure (i.e., relationship among people) of asocial network changes.
key words: social network, information propagation, random matrix, spectral graph theory, Wigner semicircle law, Laplacian matrix

1.

Introduction

The emergence of social networking services (SNSs) and thewidespread of mobile devices promote people interaction
beyond anticipation in the society. As the results, the peopleinteraction has strong capability to propagate the information
submitted by someone to the whole society. In the recent
years, it is important for the success of a new product anda new spot to propagate its information all over the social
network through not only face-to-face oﬄine conversation
but also online communication via SNS (e.g., Twitter andInstagram). Therefore, the understanding of the information
propagation property on social networks is essential to design
marketing strategy of new products and new spots.
Spectral graph theory [1] is widely used to analyze theManuscript received April 1, 2018.
Manuscript revised July 9, 2018.
Manuscript publicized August 17, 2018.
† The authors are with Tokyo Metropolitan University, Hino-shi,
191-0065 Japan.
†† The author is with Nochu Information System Co., Ltd, Tokyo,
135-0061 Japan.
††† The author is with Hiroshima City University, Hiroshima-shi,
731-3166 Japan.
a) E-mail: sakumoto@tmu.ac.jpb) E-mail: kameyama445@gmail.comc) E-mail: takano@hiroshima-cu.ac.jpd) E-mail: aida@tmu.ac.jp
DOI: 10.1587/transcom.2018EBP3098

properties of network dynamics by using the eigenvalues
and the eigenvectors of a matrix (e.g., Laplacian matrix) that
represents the structure of the network. However, when applying the spectral graph theory to social network analysis,
two problems arise. First, social networks are huge. To
analyze them using spectral graph theory, the eigenvalues
and eigenvectors of the huge matrices must be calculated but
this calculation is impossible because of its computationalcost. Second, the relationship between persons in a social
network is complex. It is hard to quantify the relationshipaccurately from obtainable data (e.g., call history and chathistory). To represent the social network structure by a matrix, the matrix elements must be given exactly on the basisof the relationship but we need to perform the diﬃcult taskof quantifying the relationship. Therefore, before applying
the spectral graph theory to the social network analysis, weshould discuss the way around the above-mentioned problem.
A random matrix is a matrix whose elements are random variables; it is often utilized to analyze large-scale andcomplex structures in quantum mechanics [2], [3]. In quantum mechanics, there is a method to derive the electron
orbital around an atomic nucleus by using a matrix that represents the atom structure. However, for a large atom (e.g.,uranium) having many electrons with complex orbitals, it is
impossible to give the matrix elements exactly. Hence, quantum mechanics gives up representing such large and complex
atom structure exactly, and analyzes electron orbital property
using the universality when the matrix elements are given byrandom variables. The analysis using the universality of therandom matrix has had great success in quantum mechanics.
The circumstance of the large and complex atom analysis inquantum mechanics is like the social network analysis, so therandom matrix is expected to solve the fundamental problem
in the social network analysis.
In this paper, we first investigate the universality of random matrices with the feature of social networks. As such arandom matrix, we use the normalized Laplacian matrix for a
network where link weights are randomly given. We clarify
that the universality (i.e., the Wigner semicircle law) of thenormalized Laplacian matrix appears in the eigenvalue frequency distribution regardless of the link weight distribution
in random networks generated with the popular models (i.e.,
ER (Erdös–Rényi) model [4] and BA (Barabási–Albert) [5]model), which are also used in several studies [4]–[9]. Then,
we analyze the information propagation speed in social net-

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

IEICE TRANS. COMMUN., VOL.E102–B, NO.2 FEBRUARY 2019392

works by using the clarified universality. In this analysis, we
model the information propagation by a random walk in lightof the resemblance between their characteristics. Since random walks are too slower than the information propagation
in a social network, our analysis focuses on the worst-casesituation. As a metric for the information propagation speed,
we use the expected value of first arrival times of the random walker for each node. As the result of our analysis
using spectral graph theory and the clarified universality, weshow that the worst-case speed of the information propagation changes up to twice if the structure (i.e., relationshipamong people) of a social network changes.
This paper is organized as follows. In Sect. 2, we describe the normalized Laplacian matrix and the Wigner semicircle law as the preliminary of our discussion. In Sect. 3, we
generate the random matrix with the social network feature,and investigate its universality. Section 4 analyzes the information propagation property using the universality clarified
in Sect. 3. Finally, in Sect. 5, we conclude this paper anddiscuss future works.
Preliminary

2.1

Normalized Laplacian Matrix

The Wigner semicircle law [3] is the universality that appears
in the eigenvalue density distribution of random matrices.
Let X = (Xi j )i ≤i, j ≤n be a n × n real symmetric matrix where
Xi j is a random variable. Xi j for j ≥ i follows an independent
identical distribution where all odd-order moments are zeroand all even-order moments are finite amounts. We denotek-th eigenvalue for a sample of X by λ k (k = 1, . . . , n). We
look at the eigenvalue density ρn (λ), which is given by((i, j) ∈ E),((i, j) < E)(1)

where wi j > 0 is the weight of link (i, j). Since network
G is undirected, adjacency matrix A is symmetric ( Ai j =A ji ). ∑Let D = diag(d i )1≤i ≤n be the degree matrix whered i = nj=1 wi j is the weighted degree of node i. Using
adjacency matrix A and degree matrix D, Laplacian matrix
L for network G is defined by
L := D − A.

(2)

Laplacian matrix L represents the node and link structure of
network G.
Normalized Laplacian matrix N is also used to represent the network structure. N is defined by
N := D−1/2 L D−1/2 .

n
1 ∑ (
λk )
δ λ−√ ,
n k=1
n

(5)

where δ(x) is the Dirac delta function of x. As the limit of
ρn (λ) with n → ∞, ρ X (λ) follows by

We denote an undirected network with n nodes by G(V, E)
where V and E are the sets of nodes and links, respectively.
Let A = ( Ai j )1≤i, j ≤n be the adjacency matrix, which represents the link structure of network G. Ai j is defined by(3)

Since N is symmetric, N can be always diagonalized.
Hence, N is also given by
N = P Λ P −1,

2.2 Wigner Semicircle Law

ρn (λ) =2.

 wi jAi j := 0

there is a path between every pair of nodes in G. Since N issymmetric,
eigenvector ql is the orthonormal basis. Namely,
∑n
q
(i)
q
k
l (i) = δ kl where δ kl is the Kronecker delta. Aci=1
cording to Eq. (4), the combination of P and Λ also represent
the network structure equivalent to N .
In Sect. 4, we discuss the relation between the random
walk and the information propagation in a social network,and analyze the information propagation based on N .

(4)where Λ = diag(λ l )1≤l ≤n and P = (ql )1≤l ≤n . λ l and ql
are l-th eigenvalue of N and the eigenvector for λ l , respectively. In this paper, we arrange eigenvalue λ l in ascendingorder (i.e., 0 = λ 1 < λ 2 ≤ ... ≤ λ n < 2). Note that weassume λ 2 , 0. This means that G is connected. Namely,ρ X (λ) = lim ρn (λ)
n→∞
1 √ 2



4σ − λ 2
2
=
2
π
σ

0


√
(|λ| < 2 σ 2 ),(6)(otherwise)

where σ is the∫ ∞standard deviation of the distribution of Xi j .
Because of −∞ ρ X (λ) dλ = 1, ρ X (λ) is the density distribution of the eigenvalues. For matrix X, its eigenvalue
density distribution satisfies the Wigner semicircle law if andonly if it is given by Eq. (6).
3. Random Matrix with Social Network Feature
The existing study [10] clarified the universality of the wellknown networks (ER network [4] and BA network [5]) withunweighted links. The clarified universality says that the
eigenvalue frequency distribution of normalized Laplacianmatrix N for an unweighted ER and BA network satisfies
the Wigner semicircle law if the network fulfills the degree
2 ≫ kcondition kmin
ave where k min and k ave are the minimum
and average of degrees (numbers of links from a node),
respectively.
To represent the structure of a social network, links
should be weighted on the basis of the relationship between
persons since people have diverse relationships in the social
network. However, the relationships are complex, so wecannot give the link weights exactly. Hence, the universality
for weighted networks should be needed for social network
analysis.
In this section, we clarify the universality for weighted
random networks to analyze the social network property. We

SAKUMOTO et al.: INFORMATION PROPAGATION ANALYSIS OF SOCIAL NETWORK USING THE UNIVERSALITY OF RANDOM MATRIX

393

first generate normalized Laplacian matrix N for randomlyweighted random networks (ER network and BA network)
as a random matrix, and then investigate the universality ofN.
3.1

Generation Method of Random Matrix

As a random matrix with the feature of social networks, we
use normalized Laplacian matrix N for randomly-weighted
random networks (ER network and BA network) generated
by the following steps. We denote the existing probabilityof links in the ER network by p. Then, let n0 and na be thenumber of initial connected nodes and the number of adding
links from a new node in the BA network, respectively.
1. Input expected average number kave of links of eachnode.
2. Generate an unweighted random network (wi j = 1)
based on the ER model or the BA model.
a. When we generate a ER network, we set existing
probability p by k ave /(n − 1) so that each node has
kave links in average.
b. When we generate a BA network, we set n0 andna so that the BA network has about n k ave /(1 − q)links. After generating the BA network, we cut thelinks randomly with the probability q. Each nodein the cut network has kave in average. We call themodified BA network as cut BA network.
3. Generate random values that follow a probability distribution (e.g., constant distribution, uniform distribution
and exponential distribution), and set link weight wi j
for i > j and (i, j) ∈ E by the random value.
Figure 1 shows the degree (i.e., number of links) distribution of ER and cut BA networks obtained from the above
steps with n = 1, 000, k ave = 20, q = 0.5, and wi j = 1 forall (i, j) ∈ E. As reference, we drew the distribution of theoriginal BA network [5] in Fig. 1. In the ER network andthe cut BA network, each node has 20 links in average. On
the contrary, the average links of the original BA network
is about 40. According to Fig. 1, the degree distribution forlarge degree nodes in the cut BA network has the same scaling exponent (-3) of the original BA network. Hence, thecutting of links in step 2b keeps the scale-free property oforiginal BA networks.
The reason why we cut the links of BA networks randomly in step 2b is described below. According to the BA
model [5], minimum degree kmin and average degree kaveof original BA networks are always the same value when
keeping the configuration of n0 and na . On the contrary,kmin and kave of ER networks are randomly changed when
keeping the configuration of p. By cutting the links of BA
networks randomly, the BA networks have diﬀerent kmin andkave , and we can compare the results for BA networks andER networks under comparable condition.
We summarize the relation between the randomlyweighted random networks (the ER networks and the cut

Fig. 1
work.

Degree distribution of unweighted ER network and cut BA net-

Table 1

Default parameter configuration.

parameter
number of nodes
distribution of link weight wi javerage of link weights
number of bins in fN (λ)

symbolnw
nh

configuration
1,000
uniform distribution
1
50

BA networks) and social networks. Several actual social networks have been confirmed that they have scale-free property
commonly [11]. The original BA model [5] represents thescale-free property, and so this model is widely used in several studies related to social networks [12], [13]. According
to Fig. 1, the cut BA network also has the scale-free property
like the original BA network. Hence, the cut BA network
is associated with social networks in term of the scale-freeproperty. On the other hand, the ER network is the simplest
random network, and does not have the scale-free property.
However, the ER network is useful to clarify the eﬀect of
the scale-free property in social networks by the comparison
between the results with the ER network and the cut BA
network.
3.2 The Universality and Its Applicable Condition
We experimentally investigate the eigenvalue frequency distribution f N (λ) of normalized Laplacian matrix N for the
randomly-weighted random networks, and clarify the universality (the Wigner semicircle law) of f N (λ) and the applicable condition.
In the investigation, we use the constant distribution
with wi j = w, the uniform distribution with the range[w/2, 3 w/2] and exponential distribution with the average
w to set link weight wi j randomly. Note that these distributions have the same average of link weights, but a diﬀerent
variance of link weights. By the comparison of the results
for the diﬀerent distributions, we clarify the universality regardless of link weights in social networks. We repeat thegeneration of N 100 times, and calculate the average of theseresults. We use the parameter configuration shown in Table 1
as default.

IEICE TRANS. COMMUN., VOL.E102–B, NO.2 FEBRUARY 2019394

Fig. 2 The expected average number kave of links vs. the square of theminimum number kmin of links in randomly-weighted ER network and cut
BA network.

We discuss the applicable condition of the universality
2 and kon the basis of kmin
ave like the existing study [10]. In
2
Fig. 2, we first show k min and kave in randomly-weighted ER
and cut BA networks with diﬀerent expected average numberof links, k ave , and the uniform distribution. As kave increases,2
kmin
and kave increases simultaneously, but the increasing
2 is larger than that of k . According to Fig. 2,
speed of kminave
2
in order to fulfill the degree condition kmin
≫ kave in [10],kave ≥ 16 for ER network and kave ≥ 24 for cut BA network
are needed at least, respectively. In this paper, we set the
average of link weight wi j to an amount equal to or greater
22than 1. Hence, if kmin
≫ k ave is fulfilled, d min≫ d ave is2also fulfilled in average. Hence, we use kmin ≫ kave instead2of d min≫ d ave in order to clarify the applicable condition
regardless of link weights.
In Figs. 3 and 4, we show eigenvalue frequency distributions f N (λ) of normalized Laplacian matrix N for
randomly-weighted ER and cut BA networks, respectively.
When we obtained f N (λ), we first counted the numberof eigenvalues of N within [λ − hb /2, λ + hb /2] wherehb = (λ n −∑λ 2 )/nh . Then, we normalized the counted numnh
ber so that i=1
f N (θ i ) = 1 where θ i = λ 2 + (i − 1/2) hb ,and nh is the number of bins in f N (λ). Note that we took
out the minimum eigenvalue λ 1 of N when obtaining f N (λ)
because λ 1 is always 0. In Figs. 3 and 4, we also draw thesemicircle distribution, which is given by
√
2



r 2 − (λ − 1) 2 (λ 2 < λ < λ n )2, (7)ρ N (λ) = πr0(otherwise)
where r is the radius of the semicircle distribution, and isgiven by 1 − λ 2 or λ n − 1. According to the range of λ 2
and λ n , r must be within 0 < r < 1. Equation (7) isessentially equivalent to Eq. (6) in the Wigner semicircle law
because there is just the diﬀerence of the semicircle center.
Hence, we define that the Wigner semicircle law is satisfied
if eigenvalue frequency distribution f N (λ) coincides withthe semicircle distribution given by Eq. (7). According to

Fig. 3 The eigenvalue frequency distributions of N ’s for randomlyweighted ER networks.

Figs. 3 and 4, eigenvalue frequency distribution f N (λ) of
N for the randomly-weighted ER and cut BA networks withk ave = 8 diﬀers from the semicircle distribution (7), but
the distributions for the randomly-weighted ER and cut BA
networks with k ave = 36 almost coincide with it. Hence,
we expect that large k ave is needed to satisfy the Wigner
semicircle law.
In order to clarify whether the eigenvalue frequency
distribution f N (λ) satisfies the Wigner semicircle law, weinvestigate the diﬀerence between f N (λ) and ρ N (λ). As thedefinition of the diﬀerence, we use relative error ϵ. Relative
error ϵ is given byh| f N (θ i ) − P(θ i )|1 ∑,ϵ=nh i=1P(θ i )

n(8)

where θ i = λ 2 + (i − 1/2) hb , and P(θ i ) is the probability
that the eigenvalues of N is within [θ i − hb /2, θ i + hb /2].
Namely, P(θ i ) is defined by∫ θi +hb /2
ρ N (λ) dλ.
P(θ i ) =(9)
θi −h b /2

Note that P(θ i ) should become the true value of f N (θ i ) forSAKUMOTO et al.: INFORMATION PROPAGATION ANALYSIS OF SOCIAL NETWORK USING THE UNIVERSALITY OF RANDOM MATRIX

395

Fig. 5 Relative error ϵ of eigenvalue frequency distribution fN (λ) for
randomly-weighted ER and cut BA networks.

2≫ kave is fulfilled, the eigenvalue frequency
condition kmin
distribution of normalized Laplacian matrix N for randomlyweighted ER and cut BA networks satisfies the Wigner semicircle law given by Eq. (7), which is the semicircle distribution determined by only the second smallest eigenvalue λ 2or the maximum eigenvalue λ n of N . Hence, λ 2 and λ n areimportant to understand the social network property in the acase fulfilling the degree condition.

4. Analysis of the Information Propagation Speed

Fig. 4 The eigenvalue frequency distributions of N ’s for randomlyweighted cut BA networks.

n → ∞ and nh → ∞.
In Fig. 5, we show the results of ϵ for randomlyweighted ER and cut BA networks with the constant distribution, the uniform distribution, and the exponential distribution of link weight wi j . As k ave increases, ϵ decreases
regardless of the link weight distribution and network topology (ER or cut BA). The reason why ϵ does not approachto 0 is that there are discretization error due to the finite
setting of n and nh . Moreover, ϵ for the uniform and exponential distributions approaches to that for the constant
distribution. According to [10], f N (λ) with the constant
distribution (wi j = 1) satisfies the Wigner semicircle law
2when the degree condition kmin
≫ kave is fulfilled. Hence,f N (λ) with the uniform and exponential distributions alsosatisfies the Wigner semicircle law. However, it is ambigu2
ity how k min≫ kave is fulfilled. According to Figs. 2 and25, the range of k min≫ k ave is diﬀerent from the range of2
kmin > k ave . ϵ shown in Fig. 5 helps to understand how
2kmin≫ kave is fulfilled. According to Fig. 5, ϵ is convergent at k ave > 36. Hence, k ave > 36 is needed to fulfill
2 ≫ k
kmin
ave for the example in this section.
From the above results, we can find that if the degree

In this section, we analyze the speed of the information
propagation on social networks fulfilling the degree condi2 ≫ k . If the degree condition is not fulfilled in ation kminavesocial network, there are many persons with too small number of friends. However, such persons would be minority inan actual social network, and contribute less to the information propagation on the entire social network. Therefore, we
ignore such persons, and focus on social networks fulfillingthe degree condition.
4.1 Metric of the Information Propagation Speed
The information propagation in a social network is involved
with the chain of word-of-mouth communications (e.g., faceto-face oﬄine conversation, and online communication via
SNS) between persons. In such a communication chain,
the information is more likely to be propagated to the persons that have many friends. Random walks on a network
have similar characteristic that the probability of the random walker arriving at a node is proportional to its nodedegree [14], which corresponds to the number of friends ina social network. Hence, we model the information propagation on social networks as a random walk. However, theinformation propagation modeled with the random walk may
be too slower than the information propagation in an actualsocial network since the random walker arrives at the samenode multiple times. Therefore, our analysis focuses on theworst-case situation for the information propagation in social
networks.

IEICE TRANS. COMMUN., VOL.E102–B, NO.2 FEBRUARY 2019396

Random walk on network G is formulated by normalized Laplacian matrix N . When node i selects node j withthe probability wi j /d i , arrival probability x a:i (t) of the random walker starting from node a to node i at time t is givenby∑ w jix a:i (t) =(10)
x a:j (t − 1),djj ∈∂iwhere ∂i = { j | Ai j > 0, 1 ≤ j ≤ n}. With arrival probability vector x a (t) = (x a:i (t))1≤i ≤n , we obtainx a (t) = x a (t − 1)D−1 A
x a (t)D−1/2 = x a (t − 1)D−1 A D−1/2
ya (t) = ya (t − 1)(I − N ),(11)

where ya (t) = x a (t)D−1/2 .
A fundamental metric to evaluate of the information
propagation speed in a social network is a first arrival time,
which is the time required until the information is first propagated to a person. Such a first arrival time of the information
corresponds to the time until the random walker first arrives
at a node in the random walk. The existing study [14] derived first arrival time f a:i of the random walker startingfrom node a to node i as
f a:i = 2 |E|n∑1q2 (i) ql (a) ql (i)
* l
+,
− √
λ
d
d
d
l
i
a
i
,
l=2

When
we derived the above equation, we used q1 (i) =√d i /(2 |E|) and the property that ql is the orthonormal basis.
From the above equation, we find that m can be calculatedwith only eigenvalue λ l of normalized Laplacian matrix N ,and does not depend on starting node a. In our analysis, we
use m as the information propagation metric of the social
network.
Equation (13) is also derived as Eq. (3.3) in [14]. However, Eq. (3.3) is slightly diﬀerent from Eq. (13) because λ kin [14] is defined as the k-th eigenvalue of D−1/2 AD−1/2 . In
this paper, λ k is the k-th eigenvalue of N = I −D−1/2 AD−1/2 .
Hence, λ k in this paper corresponds to 1 − λ k in [14]. According to the diﬀerence between these definitions, Eq. (13)is equivalent to Eq. (3.3) in [14].

(12)

where ql (i) is the i-th element of eigenvector∑n ql of normalized Laplacian matrix N , and |E| = 1/2 i=1
d i . Then, we
define the metric of the information propagation speed byusing first arrival time f a:i . For diﬀerent nodes i and j, f a:i
is diﬀerent from f a:j . Hence, we use expected time m† offirst arrival time f a:i in order to define the metric for theentire network. In the random walk starting from node a,
the steady-state probability arriving at node i is given by
d i /(2 |E|). We assume that the first arrival event of node i
occurs with the probability d i /(2 |E|), and expected time mof first arrival time f a:i is given by
n
∑
di
f a:i
2
|E|
i=1
(
)
n ∑
n
∑
1
ql (a) ql (i) √2=
ql (i) −di√λdai=1 l=2 l

m=

n
n
n
∑
√
1 *∑ 2ql (a) ∑ql (i) d i +ql (i) − √λd a i=1l=2 l , i=1
√
n
n
n
∑
∑ 1 ∑
2 |E| ql (a)*ql (i) q1 (i) +=ql2 (i) −
√
λ
da
l
, i=1
i=1
l=2
n
∑
1
.
(13)
=
λ
l=2 l

=

† Note that “expected value” does not mean “arithmetically average”. The expected value of a variable is defined by the weighted
average using the probability of its occurrence as the weight.

4.2 The Information Propagation Speed with the Universality of Normalized Laplacian Matrix N
Using the universality shown in Sect. 3, we analyze the information propagation speed. According to the universality,
eigenvalue frequency distribution f N (λ) of N for randomlyweighted networks is approximated by ρ N (λ), which given
by Eq. (7). We first derive m̃ that is the approximated valueof m with the assumption that f N (λ) ≃ ρ N (λ). Then, we
discuss the information propagation speed on the basis of m̃.
If f N (λ) ≃ ρ N (λ), expected value m of first arrival
time f a:i is approximated by
m=

n
∑
1
l=2

λl

≃ (n − 1)
∫ λn

nh
∑
1
i=1

θi

f N (θ i )1
ρ N (λ) dλλ2 λ∫ λn √
1 2
2 (n − 1)=r − (λ − 1) 2 dλ
λ
π r2
λ2
)
√
2 (n − 1) (2 = m̃,
=
1
−
r
1
−
r2
≃ (n − 1)(14)

where θ i = λ 2 + (i − 1/2) hb and hb = (λ n − λ 2 )/2. The
detailed deviation process of Eq. (14) is provided in the appendix. According to Eq. (14), m̃ is only determined by the
number n of nodes, and radius r of the semicircle distribution.
On the basis of Eq. (14), we analyze the worst-case
speed of the information propagation in a social network.
Figure 6 shows m̃ given by Eq. (14) as the function of radius r.
Note that r is within the range (0, 1) because 0 < λ 2, λ n < 2.
From this figure, m̃ is the monotonically increasing functionof r because of d m̃/d r > 0 for 0 < r < 1. Hence, if m isable to be approximated by m̃, the worst-case speed of theinformation propagation in a social network becomes slower
as r increases. Moreover, since the range of r is 0 < r < 1,
the lower bound and upper bound of m̃ are given by n − 1
and 2 (n − 1), respectively. Hence, if the structure (i.e.,
relationship among people) of a social network changes, theworst-case speed of the information propagation changes up
to twice.

SAKUMOTO et al.: INFORMATION PROPAGATION ANALYSIS OF SOCIAL NETWORK USING THE UNIVERSALITY OF RANDOM MATRIX

397

Fig. 6

4.3

Fig. 7 Relative error ϵ m of expected value of first-arrival time fa:i for
randomly-weighted ER and cut BA networks.

Radius r vs. m̃.

The Validity of Our Analysis

Our analysis is valid if the diﬀerence between m and m̃is suﬃciently small. To investigate the diﬀerence, we use
relative error ϵ m , which is defined byϵm =| m̃ − m|
.
m

(15)

In the investigation, we repeat the generation of N 100
times, and calculate the average of related error ϵ m . Like
Sect. 3, we use the the parameter configuration shown in
Table 1 as default, and randomly-weighted ER or cut BA
networks. These networks have no clusters that are the setof densely-connected nodes, and are often observed in an
actual social network. A network with no clusters can beobtained from a network with clusters by replacing clusters
to nodes. Hence, our investigation of the information propagation using ER and cut BA networks corresponds to theinvestigation ignoring the information propagation time ineach cluster. In general, the information propagation in acluster is very fast. Hence, when investigating the information propagation in a network with clusters, it is important toanalyze the information propagation times among the clusters. Therefore, our investigation also helps to understandthe information propagation in networks with clusters.
Figure 7 shows relative error ϵ m for randomly-weighted
ER and cut BA networks. According to this figure, ϵ m approaches to 0 as kave increases regardless of the link weight
distribution and network topology. Although the discretization error due to n and nh aﬀects relative error ϵ of eigenvalue
frequent distribution f N (λ), it does not aﬀect ϵ m . This characteristic is useful for the information propagation analysis.
By the comparison between Figs. 2 and 7, we conclude
that our analysis based on Eq. (14) is valid for social networks
2 ≫ k
if the degree condition k min
ave is fulfilled.
5.

Conclusion and Future Work

Spectral graph theory cannot be simply applied to social

network analysis because the matrix elements used in thetheory cannot be given exactly to represent the structure ofa social network. For this reason, we first discussed theuniversality of random matrices with the feature of social
networks. As such a random matrix, we used the normalized Laplacian matrix N for a network where link weights
are randomly given. We clarified that the universality (i.e.,the Wigner semicircle law given by Eq. (7)) of normalized
Laplacian matrix N appears regardless of the link weight
distribution in ER networks and cut BA networks, which are
the modified version of the BA networks [5]. According to
the universality, eigenvalue frequency distribution f N (λ) of
N is is determined by only the number n of nodes and semicircle radius r = 1 − λ 2 or λ n − 1 where λ 2 and λ n are thesecond minimum eigenvalue and the maximum eigenvalueof N , respectively. Then, we analyzed the information propagation speed in a social network on the basis of the spectral
graph theory and the clarified universality. In this analysis,
we modeled the information propagation by a random walkin light of the resemblance between their characteristics,
and investigated expected value m of first arrival times of therandom walker for each node. Our analysis showed that theworst-case speed of the information propagation changes up
to twice if the structure (i.e., relationship among people) of
a social network changes.
As future work, we will investigate the relationship between topological property (e.g., scale-free property) and radius r since r determines the information propagation speed
in a social network. Next, we plan to design a social media for eﬀective information propagation on the basis of thefinding by our work.
Acknowledgments
This work was supported by JSPS KAKENHI Grant Number
15K00431.
References[1] F. Chung, Spectral Graph Theory, American Mathematical Society,1997.

IEICE TRANS. COMMUN., VOL.E102–B, NO.2 FEBRUARY 2019398

[2] T. Guhr, A. Müller-Groeling, and H.A. Weidenmüller, “Randommatrix theories in quantum physics: common concepts,” Physics
Reports, vol.299, no.4, pp.189–425, June 1998.
[3] E.P. Wigner, “On the distribution of the roots of certain symmetricmatrices,” Annals of Mathematics, vol.67, no.2, pp.325–327, 1958.
[4] P. Erdös and A. Rényi, “On random graphs,” Mathematicae, vol.6,
no.26, pp.290–297, 1959.
[5] A.L. Bárabasi and R. Albert, “Emergence of scaling in random networks,” Science, vol.286, no.5439, pp.509–512, Oct. 1999.
[6] C. Zhan, G. Chen, and L.F. Yeung, “On the distributions of laplacian
eigenvalues versus node degrees in complex networks,” Physica A:
Statistical Mechanics and its Applications, vol.389, no.8, pp.1779–
1788, April 2010.
[7] S. Jalan and J.N. Bandyopadhyay, “Random matrix analysis of network laplacians,” Physica A: Statistical Mechanics and its Applications, vol.387, no.2, pp.667–674, Jan. 2008.
[8] I.J. Farkas, I. Derényi, A.L. Barabási, and T. Vicsek, “Spectra of“real-world” graphs: Beyond the semicircle law,” Phys. Rev. E,
vol.64, no.2, p.026704, July 2001.
[9] Y. Sakumoto and H. Ohsaki, “Fluid-based analysis for understanding
tcp performance on scale-free structure,” J. Inf. Process., vol.24, no.4,
pp.660–668, July 2016.
[10] F. Chung, L. Lu, and V. Vu, “Spectra of random graphs with given
expected degrees,” Proc. National Academy of Sciences, vol.100,
no.11, pp.6313–6318, May 2003.
[11] A.L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol.286, no.5439, pp.509–512, Oct. 1999.
[12] P. Crucitti, V. Latora, M. Marchiori, and A. Rapisarda, “Eﬃciency
of scale-free networks: Error and attack tolerance,” Physica A: Statistical Mechanics and its Applications, vol.320, pp.622–642, March
2003.
[13] B. Viswanath, A. Post, K.P. Gummadi, and A. Mislove, “An analysis
of social network-based sybil defenses,” ACM SIGCOMM Comput.
Commun. Rev., vol.40, no.4, pp.363–374, Oct. 2010.
[14] L. Lovász, “Random walks on graphs: a survey,” Combinatorics,
Paul Erdős is eighty, vol.2, pp.353–398, 1996.

Appendix:
We describe the detailed deviation process of Eq. (14). If
eigenvalue frequency distribution f N (λ) is given by the
Wigner semicircle law, expected value m of the first-arrival
time is approximated by m̃. m̃ is given by∫ λn1m̃ = (n − 1)
ρ N (λ) dλλλ2∫ λn √
1 2
2 (n − 1)=r − (λ − 1) 2 dλ.
(A· 1)2πr
λ2 λBy substituting λ = r cos θ + 1 into Eq. (A· 1), we obtain∫ π 2
2 (n − 1)r sin2 θ
dθ
m̃ =
π r2
0 r cos θ + 1∫ π 2
2 (n − 1)
r − 1 + 1 − r 2 cos2 θ=dθr cos θ + 1
π r2
0
(
)
∫ π
2 (n − 1)
r2 − 1=+ 1 − r cos θ dθr cos θ + 1
π r2
0= I1 (r) + I2 (r),(A· 2)
where I1 (r) and I2 (r) are given by∫ π
2 (n − 1)
r2 − 1dθ,
2πr
0 r cos θ + 1∫ π
2 (n − 1)l 2 (r) =(1 − r cos θ) dθ,π r20I1 (r) =(A· 3)(A· 4)

respectively. When we use the half-angle formula of cos θ,l 1 (r) is given by
2 (n − 1)
π r2∫ πr2 − 1() () dθ
×
0 r cos2 θ − sin2 θ + cos2 θ + sin2 θ
2
2
2
2
∫ π
2 (n − 1)
r2 − 1
=
dθ
2 θ
2 θ
π r2
0 (1 + r) cos 2 + (1 − r) sin 2∫ π
2 (n − 1)
r2 − 11=dθ
2 θ cos2 θ
π r2
(1
+
r)
+
(1
−
r)
tan
0
2
2
∫ π
2 (n − 1)r −11=dθ, (A· 5)
2
1−r
θ
2 θ
2
2
πr
0 1 − i 1+r tan 2 cos 2

I1 (r) =where
i is the imaginary unit. By substituting x =√1−rθ
1+r tan 2 into Eq. (A· 5), l 1 (r) is derived as√∫ ∞−2 1 − r 2
2 (n − 1)dx
I1 (r) =π r2
1 − (i x) 20
2 (n − 1)=
π r2)∫ ∞( √
)( 1
1
×
+
dx
− 1 − r2
1+ix 1−ix
0)
2 (n − 1) ( √
2
=
−
1
−
r
π r2
]∞
[1
1
log(1 + i x) − log(1 − i x)
×
0
i
i
)
2 (n − 1) ( √=i 1 − r2
π r2[]
× lim log(1 + i x) − log(1 − i x) .
(A· 6)x→∞

When we use log z = log |z| + i arg(z), I1 (r) is derived as)
2 (n − 1) ( √2 lim 2 i tan−1 x
I1 (r) =
1
−
r
i
x→∞
π r2
2 (n − 1) √=−1 − r2.
(A· 7)
r2
Then, l 2 (r) is derived as∫ π
2 (n − 1)I2 (r) =(1 − r cos θ) dθ
π r2
0
]π
2 (n − 1) [
=
θ
−
r
sin
θ
0
π r2
2 (n − 1)=.
r2(A· 8)

By substituting Eqs. (A· 7) and (A· 8) into Eq. (A· 2), m̃
is given as

SAKUMOTO et al.: INFORMATION PROPAGATION ANALYSIS OF SOCIAL NETWORK USING THE UNIVERSALITY OF RANDOM MATRIX

399

m̃ = I1 (r) + I2 (r))√
2 (n − 1) (
2 .
=
1
−
1
−
r
r2

(A· 9)

Yusuke Sakumotoreceived M.E. and Ph.D.
degrees in the Information and Computer Sciences from Osaka University in 2008 and 2010,
respectively. He is currently an assistant professor at Graduate School of Systems Design,
Tokyo Metropolitan University, Japan. His research work is in the area of the networking forsocial, comuter, electricity device. He is a member of IEEE, IPSJ and IEICE.

Tsukasa Kameyama
received B.E. and M.E.
degrees from Tokyo Metropolitan University in2016 and 2018, respectively. He was a student at Graduate School of System Design, Tokyo Metropolitan University, Japan from 2016 to2018. He currently works at Nochu Information
System Co., Ltd. His research interest is in thearea of social network.

Chisa Takano
received the B.E. degree
in Telecommunication Engineering from Osaka
University, Japan, in 2000, and received the
Ph.D. in Telecommunications Engineering from
Tokyo Metropolitan University, Japan, in 2008.
In 2000 she joined the Traﬃc Research Center,
NTT Advanced Technology Corporation (NTTAT). Since April 2008, she has been an Associate Professor of the Graduate School of Information Sciences, Hiroshima City University.
Her research interests are in the area of compute networks and distributed systems. She received the IEICE’s Young
Researchers’ Award in 2003.

Masaki Aida
received the B.S. degree inPhysics and M.S. degree in Atomic Physics from
St. Paul’s University, Tokyo, Japan, in 1987 and1989, respectively, and received the Ph.D. in
Telecommunications Engineering from the University of Tokyo, Japan, in 1999. After joining
NTT Laboratories in April 1989, he has been
engaged in research on traﬃc issues in computercommunication networks. From April 2005 to
March 2007, he was an Associate Professor at
the Faculty of System Design, Tokyo Metropolitan University. He has been a Professor of the Graduate School of Systems
Design, Tokyo Metropolitan University since April 2007. He received theBest Tutorial Paper Award of IEICE Communications Society in 2013. Prof.
Aida is a member of the IEEE, IEICE, and the Operations Research Societyof Japan.