NOLTA, IEICE
Paper

Reconstructing the Laplacian matrix
to estimate social network structureby using compressed sensing
Shun Sugimoto 1 a) and Masaki Aida 1 b)
1Graduate School of Systems Design, Tokyo Metropolitan University
Hino-shi 191-0065, Japana)sugimoto-shun@ed.tmu.ac.jp
aida@tmu.ac.jpb)Received January 22, 2019; Revised May 12, 2019; Published October 1, 2019
Abstract: For complex large scale networks, like social networks, it is usually impossible toobserve complete information about their topology structure or link weight directly. A recent proposal, the network resonance method, can estimate the eigenvalues and eigenvectorsof the Laplacian matrix for representing network structure, by using the resonance phenomenaof oscillation dynamics on networks. However, it is generally not possible to observe all the
eigenvalues and eigenvectors. This paper uses compressed sensing to create a new method ofreconstructing the original Laplacian matrix from a partial set of its eigenvalues and eigenvectors. Since very few node pairs in social networks have links, we can expect that compressedsensing will be eﬀective. The estimated Laplacian matrix of a social network enables to us todetermine its structure and link weights.
Key Words: compressed sensing, Laplacian matrix, eigenvalue, eigenvector

1. Introduction
Due to the spread of the Internet, information exchange among users through on-line social networks
is becoming active. One signiﬁcant feature of social networks is their scale-free topology structure,that is, the degree distribution of nodes follows a power law [1]. Accordingly, just a few nodes have avery large number of links while most nodes have only a few links. For example, in Social Networking
Service (SNS), while most users have hundreds of followers at most, there are celebrities who havemillions of followers. If we consider the relationship of follow as a link, we can understand the structureof scale-free networks in social networks from SNS data [2, 3]. It is known that scale-free networks
appear frequently in the topologies of complex networks in various ﬁelds other than social networks [4].
Networks topology structure can be represented by a square matrix by setting the link informationfrom node i to node j as the (i, j) component of the matrix. Spectral graph theory is a method ofanalyzing the characteristics of networks by eigenvalues and eigenvectors of the matrix representing
the network structure, and it is applicable to many problems including clustering of networks, graphdrawing, graph cut, node coloring, and image segmentation [5, 6]. In graph signal processing, the496
Nonlinear Theory and Its Applications, IEICE, vol. 10, no. 4, pp. 496–506c
IEICE2019

DOI: 10.1587/nolta.10.496

graph Fourier transformation plays importance role, and it is introduced based on the spectral graphtheory [7, 8].
Since the eigenvalues and eigenvectors include information of the corresponding matrix, the original
matrix can be reproduced if all the eigenvalues and eigenvectors are given. This means that if all the
eigenvalues and eigenvectors are given, we can acquire complete information of the topology structureof the network.
In social networks, the strength of the inﬂuence of the human relationship between two users isrepresented as the weight of link between the corresponding user nodes. If we can measure such
quantities directly, we can determine the topology structure of the network, and at the same time,
determine the square matrix representing the network structure. For example, inﬂuence strength
could be taken to be proportional to the volume of traﬃc exchanged between the user nodes, which
can be easily measured. Unfortunately, the strength of inﬂuence in human relations is diﬀerent inconcept from the amount of traﬃc exchanged between user nodes. As this is also true for othermeasurable quantities, we have to determine link weights in a diﬀerent way.
We introduced the oscillation model on networks as a model that can describe network dynamics
generated from the inﬂuences among user nodes [9, 10]. The importance of the oscillation model liesin the relationship between the oscillation energy of each node and node centrality. The oscillationenergy of each node gives the degree centrality or the betweenness centrality in simple cases, andgives a generalized notion of node centrality [11, 12]. Based on the oscillation model, we proposed amethod to estimate the eigenvalues and eigenvectors of the Laplacian matrix that represents network
structure called the network resonance method [13, 14]. This method is based on the resonancephenomena of network behavior with respect to an external input that varies at a certain frequency.
Even if we do not know the Laplacian matrix, knowing all the eigenvalues and eigenvectors of the
Laplacian matrix allows us to reproduce the original Laplacian matrix. To know all the eigenvalues
and eigenvectors of the Laplacian matrix means knowing link presence and weights between user
nodes for the corresponding social network.
When estimating the eigenvalues of the Laplacian matrix by the network resonance method, it is
not always possible to estimate all eigenvalues due to factors such as the duplication of eigenvalues andthe unknown strength of oscillation damping. Of course, it is also not always possible to estimate all
the eigenvectors. Therefore, it is desirable to be able to reproduce the original Laplacian matrix fromjust some of the eigenvalues/eigenvectors of the Laplacian matrix. In addition, since estimation of
eigenvalues/eigenvectors involves errors, the inﬂuence of these errors on networks structure estimationmust be oﬀset.
Almost all components of the Laplacian matrix are occupied by zero components, because social
networks are scale-free. This property, zero components are dominant, is called sparsity. We can
expect that applying compressed sensing exerts a good eﬀect in this situation.
The compressed sensing is a technique that leverages sparsity to attain reasonable estimation accuracy from the fewest observations possible; it has been studied actively in various ﬁelds in recent
years [15], including information systems [16], signal processing [17], and communications systems [18].
In particular in communication networks, the compressed sensing is used in eﬃcient observations fordata gathering in wireless sensor networks [19] and for classiﬁcation of link quality of service (QoS)
in network tomography [20].
In this paper, we investigate the method that uses compressed sensing to reconstruct the original
Laplacian matrix from just some of the eigenvalues and eigenvectors. This is basic research on
estimating social network structure from some partial information observed through the network
resonance method.
This paper is organized as follows. Section 2 explains the fundamental properties of spectral graphtheory and compressed sensing to aid the reader’s understanding. Section 3 proposes a method forreconstructing the Laplacian matrix that uses compressed sensing. Section 4 discusses the eﬃciencyof the proposed method.

497

2. Preliminaries
2.1 Laplacian matrix
Let us consider undirected graph G = G(V, E) with n nodes, where V = {1, 2, . . . , n} is a set ofnodes and E is a set of links. Let wij (> 0) be the link weight between node i and j. The (weighted)
adjacency matrix A = [Aij ] for undirected graph G(V, E) is the n × n matrix deﬁned aswij ((i, j) ∈ E),
Aij :=(1)
0((i, j) ∈/ E).
Since wij = wji , adjacency matrix A is real and symmetric. Next, node i has degree di deﬁned as

wij ,
(2)
di :=
j∈∂i

where ∂i is the set of nodes adjacent to node i. The degree matrix is deﬁned as D := diag({di }), andthe Laplacian matrix of G(V, E) is deﬁned as
L := D − A.

(3)

Note that the Laplacian matrix is real and symmetric, so the eigenvalues of L are real numbers andeigenvectors can be chosen as the eigenbasis. In addition, L is a positive-semideﬁnite matrix, and it
is known that the minimum eigenvalue is 0 [6]. Here, we write the n eigenvalues of L in ascendingorder as0 = λ0 ≤ λ1 ≤ · · · ≤ λn−1 .
The eigenvectors vμ associated with eigenvalues λμ (μ = 0, 1, . . . , n − 1) are chosen as follows.
L vμ = λμ vμ ,vμ · vν = δμν ,where δμν denotes the Kronecker delta.
If all eigenvalues and eigenvectors are known, using diagonal matrix Λ := diag(λ0 , λ1 , · · · , λn−1 )and orthogonal matrix P := [v0 , v1 , . . . , vn−1 ], Laplacian matrix L is expressed as
L = P Λ tP .

(4)

Therefore, the Laplacian matrix can be reproduced from the information expressed by eigenvalues
and eigenvectors. In addition, once the Laplacian matrix is known, we can also know the topology
structure of the network.

2.2 Compressed sensing
Compressed sensing can estimate unknown vectors from linear observations. Let x (∈ Rn ) be an ndimensional unknown vector. At this time, linear observations for x can be written as inner producta · x, where a (∈ Rn ) is an observation vector. When this linear observation is performed m times,
the observation matrix F ∈ Rm×n is expressed as
⎡
⎤
t
a1
⎢t ⎥
⎢ a2 ⎥⎥(5)F =⎢⎢ .. ⎥⎣ . ⎦t

amby setting each observation vector as ai (i = 1, 2, . . . , m). The m linear observations for the unknown
vector x can be deﬁned as
y = F x,(6)

where the m-dimensional vector y (∈ Rm ) is a vector having ai ·x (i = 1, 2, . . . , m) in each component
as a result of the m linear observations.

498

When the observation matrix F is known, (6) is equivalent to a set of simultaneous linear equations
in which each component of unknown vector x is a variable. Since the number of observations, m,corresponds to the number of equations, and x is an n-dimensional vector, it is necessary to satisfy atleast m ≥ n in order to solve the equations. Even if unknown vector x is sparse, the use of compressedsensing allows us to obtain a solution even if m < n. In other words, compressed sensing is a method
for solving underdetermined linear equations, and regularizing ||x||1 as a cost function as follows.
x̂ = arg min ||x||1 subj. to y = F x,x(7)where ||x||1 = ni=1 |xi |. Regularization via (7) is called 1 reconstruction and is known to be very
eﬀective in compressed sensing. When there are k non-zero components in unknown vector x, x is
said to be k-sparse. In general, smaller values of k make estimation possible with fewer observations,m. Extensive studies have been conducted on compressed sensing, for details please refer to [16, 17].

3. Estimation of the Laplacian matrix by compressed sensing
In this section we propose a method that uses compressed sensing in estimating a Laplacian matrix
from just a few eigenvalues and eigenvectors. The eigenvalues and eigenvectors are estimated by the
network resonance method [13, 14]. Eigenvalue estimation by using the network resonance method is
outlined in Appendix A. In this section, matrices and vectors are denoted by [ ] and ( ), respectively.

3.1 Proposed method
First, we denote the Laplacian matrix as
⎡

⎤
l0
⎢ t ⎥
⎢ l1 ⎥⎥
L=⎢⎢ .. ⎥ ,
⎣ . ⎦
t
ln−1
t

(8)

where t li (i = 0, 1, . . . , n − 1) is a row vector of Laplacian matrix L. The characteristic equation of
the Laplacian matrix is given as
L vi = λi vi .
Using (8), the left-hand side of (9) is expressed as
⎡
⎤
⎛
⎞
t
l0
l0 · vi⎢ t ⎥⎜⎟⎢ l1 ⎥⎜ l1 · vi ⎟⎢⎥⎜⎟.
L vi = ⎢ . ⎥ vi = ⎜..
⎟.
⎣ .. ⎦⎝⎠tln−1
ln−1 · vi

(9)

(10)

We denote each component of eigenvector vi as vi (j) (j = 0, 1, . . . , n − 1), and extract the j-thcomponent from (9) and (10) as
λi vi (j) = lj · vi .

(11)

Since the right-hand side of (11) is an inner product, we can reverse the order as
λi vi (j) = vi · lj .

(12)

Since there are n eigenvalues (i = 0, 1, . . . , n − 1), it can be considered that there are n relational
expressions for each j. Here, we select m equations from among these n relational expressions andwrite the eigenvalues and eigenvectors as λ̄k and v̄k = (v̄k (0), v̄k (1), . . . , v̄k (n−1)) (k = 1, 2, . . . , m),respectively. By using the selected eigenvalues and eigenvectors, we can cast the relationship of (12)as a vector as follows.

499

⎛

⎞ ⎡ ⎤
λ̄1 v̄1 (j)
v̄1
⎜
⎟ ⎢ ⎥
⎜ λ̄2 v̄2 (j) ⎟ ⎢ v̄2 ⎥⎜⎟ = ⎢ . ⎥ lj .
..
⎜⎟ ⎢ . ⎥.
⎝
⎠ ⎣ . ⎦(13)v̄m

λ̄m v̄m (j)Now, if we regard the left-hand side of (13) as y and the right-hand side as F = t [v̄1 , v̄2 , . . . , v̄m ] andx = lj , (13) has the same form as (6). Thus, when lj is sparse, we can estimate the j-th row vectorof the unknown Laplacian matrix from m (< n) sets of eigenvalues/eigenvectors. In addition, if thisestimation is extended to all row vectors (l0 , l1 , . . . , ln−1 ), we can reproduce the entire Laplacianmatrix.
This method can be applied to not only Laplacian matrices but also other real symmetric matrices.
Unfortunately, it is diﬃcult to apply this method to asymmetric Laplacian matrices, e.g. general
directed graphs, because eigenvalues are generally complex numbers. However, this method can beapplied to the symmetrizable directed graphs [10].

3.2 Related method
First, we summarize the requirements of the proposed method proposed in the previous subsection.
In reproducing the matrix by using the diagonal matrix and the orthogonal matrix as in (4), all the
eigenvalues and eigenvectors are used. However, not all the eigenvalues/eigenvectors can be estimatedby the network resonance method, and it is likely that some estimations will be somewhat inaccurate.
Thus it is diﬃcult to reconstruct Laplacian matrixes by using (4).
We now consider the low-rank approximation of real symmetric matrixes as another estimation
method. (4) can be transformed into
L = P Λ tP =n−1
λμ vμ tvμ .

(14)

μ=0

Since eigenvalue λμ with low value contributes little to L, it is possible to approximate the real
symmetric matrix by considering only terms with large eigenvalues. Unfortunately, with this method,the estimation accuracy decreases, when large eigenvalues are missing or are quite noisy. The proposed
method, on the other hand, does not require all of the large eigenvalues, and makes it possible toselect eigenvalues ﬂexibly.

4. Evaluations
In this section, we demonstrate the performance of the proposed method. In order to clarify basic
features for reconstruction of the Laplacian matrix by using compressed sensing, we generate networkmodels as pseudo social networks and evaluate the proposed method by using the network models.
Many complex networks including social networks are known to exhibit the scale-free characteristic.
Based on this, our evaluations use network models with scale-free property. In particular, we estimate
the Laplacian matrix for scale-free networks generated by the BA model [1].
When creating a network with the BA model, the initial state is a complete graph with 3 nodes, andevery time one node is added, links are established to three nodes selected by preferential attachment.
The number of nodes in our network model is n = 100.
The following evaluation results are the averages of the experimental results gained from ten independent scale-free networks generated independently.

4.1 Estimation accuracy in each eigenvalues patterns
In the proposed method, estimation accuracy greatly diﬀers depending on the eigenvalues and theeigenvectors used for reconstruction. Therefore, in this section, we classify combinations of the eigenvalues used for the reconstruction into several typical categories and investigate which eigenvalues
patterns improve the estimation performance.

500

All the link weights of our network model are set to 1; the Laplacian matrix is unknown. In addition,
we consider the situation where m pairs of eigenvalues and eigenvectors of the Laplacian matrix canbe selected; they are assumed to be noise-free.
Here, we introduce the Vector Estimation Success Rate as the performance index. The successof vector estimation is deﬁned as the case where the diﬀerence between the actual value and theestimated value of all components of the vector is less than 0.01. Figure 1 plots the Vector Estimation
Success Rate versus the number of pairs of eigenvalues and eigenvectors, m. We use diﬀerent methods
to select m pairs and the results are plotted using diﬀerent colors. Selection methods of eigenvalues
are listed in Table I. The mixing ratio of the eigenvalues in Mixture is based on the combination thatyielded the highest estimated performance as determined in the experiments.

Fig. 1.

Vector estimation success rate of each pattern.

Table I.

Randomm-Largest
m-Smallest
MixtureSelection methods of eigenvalues.

m eigenvalues at randomm eigenvalues in ascending orderm eigenvalues in descending order(m × 1/8) in ascending, (m × 7/8) in descending

From Fig. 1, m-Smallest () yields the smallest Vector Estimation Success Rate regardless of m.
This result implies that estimation accuracy does not improve even if more small eigenvalues used. In
addition, m-Largest () always higher Vector Estimation Success Rate than m-Smallest. However,Random () oﬀers better performance, suggesting that larger eigenvalues and smaller eigenvalues
are needed for higher performance. Mixture (2) achieves the best results; even if only half of theeigenvalues and eigenvectors are used, (m = 50), almost all vectors can be accurately estimated. The
optimal mixing ratio was 7 : 1, but ratios of 6 : 1 or 5 : 1 yielded very similar performance.
The reason why Mixture achieves best results is considered as follows. The eigenvalues of the
Laplacian matrix gives hierarchical structure with respect to spatial scales. Larger eigenvalues andtheir associated eigenvectors have information of ﬁne structure of the network. On the other hand,smaller eigenvalues and their associated eigenvectors have information of coarse grained structure of
the network. Since reproducing the structure of entire network requires both ﬁne structure and coarse
grained information, Mixture gives best results.

501

4.2 Estimation by the eigenvalues and the eigenvectors that contain noise
In this subsection, we consider the situation where in the given eigenvalues and eigenvectors containnoise. We generated a scale-free network by the BA model and assigned uniform random numbersin the range of [0.1, 1.1] as link weights. As noise, we added a random number following the normal
distribution (μ = 0, σ = 0.01) to all m eigenvalues and all components of the m eigenvectors. Since
the eigenvalues and eigenvectors contain noise, it is impossible to obtain a complete solution. Here weevaluate performance by using the absolute error between the actual value and the estimated valueof each component of the Laplacian matrix.
Figure 2 plot the average error and the maximum error versus m; Mixture was used to select the
eigenvalues. Average Error denotes the average of absolute error of all components of the estimatedmatrix. Max Error denotes the largest error among all components. From these ﬁgures, we canrecognize that the maximum error decreases with observation number m, but the average error isminimum around m = 70. Therefore, using many eigenvalues for estimation does not necessarily leadto an improvement in accuracy if noise is present.

Fig. 2.

Average and maximum error of the estimated Laplacian matrix.

Figures 3 and 4 are the heat maps showing the error of all components of the estimated matrix form = 40 and m = 80, respectively. Note that they have diﬀerent scales. The order of components isthe order of node addition in the BA model. Therefore, the nodes corresponding to the upper left
components are hub nodes.
These ﬁgures show that the errors fall as the observation number is increased from m = 40 tom = 80. In addition, for m = 40, the errors concentrate on diagonal components, but for m = 80,
many errors are found in non-diagonal components of hub nodes. In other words, it is considered that

Fig. 3.

Error matrix between actual matrix and estimated matrix (m = 40).

502

Fig. 4.

Error matrix between actual matrix and estimated matrix (m = 80).

row vectors with high sparsity can be accurately estimated by increasing m.

4.3 Extension of the estimation method considering existence of non-sparse row
vectors
In this section, we extend the proposed method described in the previous section in order to improve
the reconstruction performance of the Laplacian matrix. Since social networks have scale-free characteristic, there are several hub nodes. The hub nodes have links to a very large number of nodes andthe corresponding row vector li is not necessarily sparse. Therefore, the compressed sensing approach
might not work eﬀectively. In order to mitigate this eﬀect, we extend the estimation method of eachrow vector, shown in the previous section. Let the left-hand side of (13) be yi and t [v̄0 , v̄1 , . . . , v̄m−1 ]of the right-hand side be F . The proposed method can be expanded as follows.
⎛ ⎞ ⎡
⎤⎛ ⎞
y1
F
0
l1
⎜ ⎟ ⎢
⎥⎜ ⎟
F
⎜ y2 ⎟ ⎢⎥ ⎜ l2 ⎟⎜ . ⎟=⎢⎥⎜ . ⎟.
(15)..
⎜ . ⎟ ⎢⎥⎜ . ⎟.
⎝ . ⎠ ⎣⎦⎝ . ⎠
yn

F

0

ln

The matrix of the right-hand side is as follows.
⎡
⎤
F
0

⎢
⎥
F
⎢
⎥
⎢
⎥ = [Fij ] = v̄s (t), (i = kn + s, j = kn + t + 1) .
..
⎢
⎥
.
0,
(otherwise)
⎣
⎦
0
F

(16)

Where [Fij ] is the component of this matrix (i = 1, . . . , n2 , j = 1, . . . , n2 ) and v̄s (t) is the componentof the selected eigenvectors (k = 0, . . . , n − 1, s = 1, . . . , n, t = 0, . . . , n − 1). n denotes the numberof nodes. (15) also has the same form as compressed sensing, we can estimate all the row vectorsof Laplacian matrix L, simultaneously. By reconstructing all row vectors simultaneously, even if
the Laplacian matrix has low sparsity, compressed sensing can be expected to work eﬀectively. In
addition, as (15) contains all components of Laplacian matrix L, we can add some limiting conditions
for reconstruction. From the deﬁnition of the Laplacian matrix, L for an undirected graph is asymmetric matrix, and
Lij = Lji .
In addition, the diagonal components of L are503

Lii = −Lik .

k(=i)

If we use these equations as the constraint condition, Laplacian matrix L can be reconstructed moreaccurately because the candidate solutions are limited eﬀectively.
Figure 5 shows the average error of the method of reconstructing each row vector and the methodof reconstructing all the row vectors, simultaneously. All the link weights of our network model are
set to 1; the pattern of eigenvalues uses Mixture. Also, in the extended method for simultaneousreconstruction of all the row vectors, we added all the above constraints. From this ﬁgure, in situations where the number of m is the same, we can see that the extended method for simultaneousreconstruction of all the row vectors can most reduce the average error.

Fig. 5.

Average error of all-vector estimation.

Figure 5 also shows the average error of reconstruction based on low-rank approximation (14).
Here, we use m of the largest eigenvalues for reconstruction. From Fig. 5, the average error of lowrank approximation has larger error than our proposed method. Therefore, we can recognize thatthe proposed method has better performance than low-rank approximation for Laplacian matrix
reconstruction.
Since the dimensionality of (15) is very high for large-scale networks, it causes the problem incomputational cost. However, we can expect that the sparsity of the Laplacian matrix is valid for
actual social networks. The experimental network model generated by BA model has hub nodes whose
links are not sparse, and we need the aforementioned method to recover the sparsity. On the other
hand, links of hub nodes in actual social networks is sparse because even hub nodes have links verysmaller than the number of users. Therefore, the situation that we need the method of (15) is rarecase.

5. Conclusion
In this paper, we have proposed a method for reproducing a sparse Laplacian matrix from justsome of its eigenvalues and eigenvectors by using compressed sensing. This method can be used toinvestigate the structure of social networks from less than complete information. The performance of
this method was veriﬁed by experiments. The results showed that to improve the estimation accuracy,
it is necessary to use both large eigenvalues and small eigenvalues. In situations where the eigenvalues
and eigenvectors contain noise, the estimated matrix may contain relatively large errors even if many
eigenvalues are used. Since the Laplacian matrix of social networks has high sparsity, the estimation504

accuracy is improved by reconstructing all the row vectors of the Laplacian matrix simultaneously,
even if some nodes have high nodal degree. In addition, the proposed method is superior to low-rankapproximation in terms of accuracy.
In future research, we will evaluate the performance of the proposed method by using actual dataof eigenvalues and eigenvectors observed by the network resonance method.

Acknowledgments
This research was supported by Grant-in-Aid for Scientiﬁc Research (B) No. 17H01737 (2017–2019)and (C) No. 18K11271 (2018–2020) from the Japan Society for the Promotion of Science (JSPS).

Appendix
A. Network resonance method
Let x(t) = t({xi (t)}) be the vector representing the state of nodes at time t. When periodic external
force F with frequency ω is imposed on node j, the motion equation of the oscillation forced on the
network is given bydx(t)d2 x(t)+ L x(t) = (F cos ωt) 1{j} ,
+γ
dt2
dt

(A-1)

where γ is a constant, and 1{j} is a column vector such that only the j-th component is 1 and allothers are 0. Steady state solution x(t) is obtained asx(t) =n−1Aμ (ω) cos ωt + θμ (ω) vμ ,

(A-2)

μ=0

where Aμ (ω) and θμ (ω) are the amplitude and phase of mode μ, respectively. They can be written as
Aμ (ω) = 

F vμ (j)(ωμ2 − ω 2 )2 + (γω)2


γω
−1
θμ (ω) = tan,
ω 2 − ωμ2

where ωμ =



,

(A-3)

(A-4)

λμ . From (A-3), Aμ (ω) is maximized when the frequency of the external force, ω, is
(A-5)
ω = ωμ2 − γ 2 /2.

This phenomenon is called resonance. From the frequency at which resonance occurs, we can estimate
eigenfrequency ωμ . If eigenfrequency ωμ is given, we can estimate the eigenvalue λμ by using λμ = ωμ2 .
In estimating eigenvectors, we focus on not the position but the height of amplitude peaks. For
details, please see [14, 21].

References[1] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286,
pp. 509–512, 1999.
[2] K. Yuta, N. Ono, and Y. Fujiwara, “Structural analysis of human network in social networking
services,” Transactions of Information Processing Society of Japan, vol. 47, no. 3, pp. 865–874,
2005.
[3] M. Uchida and S. Shirayama, “Analysis of network structure and model estimation for SNS,”
Transactions of Information Processing Society of Japan, vol. 47, no. 9, pp. 2840–2849, 2006.
[4] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Reviews of Modern
Physics, vol. 74, pp. 47–97, 2002.
[5] F.R.K. Chung, “Lectures on spectral graph theory,” CBMS Lecture Notes, AMS Publications,
Providence, 1995.

505

[6] D. Spielman, “Spectral Graph Theory,” Chapter 18 of Combinatorial Scientific Computing,
Chapman and Hall/CRC, pp. 495–524, 2012.
[7] A. Sandryhaila and J.M.F. Moura, “Discrete signal processing on graphs,” IEEE Transactions
on Signal Processing, vol. 61, no. 7, pp. 1644–1656, 2013.
[8] A. Sandryhaila and J.M.F. Moura, “Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure,” IEEE Signal Processing
Magagine, vol. 31, no. 5, pp. 80–90, 2014.
[9] M. Aida, C. Takano, and M. Murata, “Oscillation model for network dynamics caused byasymmetric node interaction based on the symmetric scaled Laplacian matrix,” The 12th International Conference on Foundations of Computer Science (FCS 2016), pp. 38–44, 2016.
[10] M. Aida, C. Takano, and M. Murata, “Oscillation model for describing network dynamics causedby asymmetric node interaction,” IEICE Transactions on Communications, vol. E101-B, no. 1,
pp. 123–136, January 2018.
[11] C. Takano and M. Aida, “Proposal of new index for describing node centralities based on
oscillation dynamics on networks,” IEEE GLOBECOM 2016, 2016.
[12] C. Takano and M. Aida, “Revealing of the underlying mechanism of diﬀerent node centralities based on oscillation dynamics on networks,” IEICE Transactions on Communications,vol. E101-B, no. 8, pp. 1820–1832, August 2018.
[13] S. Furutani, C. Takano, and M. Aida, “Proposal of the network resonance method for estimating
eigenvalues of the scaled Laplacian matrix,” The 8th International Conference on Intelligent
Networking and Collaborative Systems (INCoS 2016) Workshop (WIND 2016), 2016.
[14] S. Furutani, C. Takano, and M. Aida, “Method for estimating eigenvectors of a scaled Laplacianmatrix using the resonance of oscillation dynamics on networks,” IEEE/ACM International
Conference on Social Networks Analysis and Mining (ASONAM 2017), Sydney, Australia, 2017.
[15] M. Elad, Sparse and Redundant Representations: From Theory to Applications in Signal andImage Processing, Springer Publishing Company, Incorporated, 2010.
[16] D. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory, vol. 52, no. 4,
pp. 1289–1306, 2006.
[17] E. Candes and M. Wakin, “An introduction to compressive sampling,” IEEE Signal Processing
Magazine, vol. 25, no. 2, pp. 21–30, 2008.
[18] K. Hayashi, M. Nagahara, and T. Tanaka, “A user’s guide to compressed sensing for communications systems,” IEICE Transactions on Communications, vol. E96-B, no. 3, pp. 685–712,
2013.
[19] H. Zheng, F. Yang, X. Tian, and X. Gan, “Data gathering with compressive sensing in wireless sensor networks: A random walk based approach,” IEEE Transactions on Parallel andDistributed Systems, vol. 26, no. 1, pp. 35–44, 2015.
[20] T. Matsuda, M. Nagahara, and K. Hayashi, “Link quality classiﬁer with compressed sensing
based on 1 -2 optimization,” IEEE Communications Letters, vol. 15, no. 10, pp. 1117–1119,
2011.
[21] S. Furutani, C. Takano, and M. Aida, “Network resonance method: Estimating network structure from the resonance of oscillation dynamics,” IEICE Transactions on Communications,vol. E102-B, no. 4, pp. 799–809, April 2019.

506