IEICE TRANS. COMMUN., VOL.E101–B, NO.8 AUGUST 2018

1820

PAPER

Revealing of the Underlying Mechanism of Different NodeCentralities Based on Oscillation Dynamics on Networks
Chisa TAKANO†a) and Masaki AIDA††b) , Members

SUMMARY In recent years, with the rapid development of the Internet
and cloud computing, an enormous amount of information is exchanged on
various social networking services. In order to handle and maintain such amountain of information properly by limited resources in the network, it isvery important to comprehend the dynamics for propagation of informationor activity on the social network. One of many indices used by social network analysis which investigates the network structure is “node centrality”.
A common characteristic of conventional node centralities is that it depends
on the topological structure of network and the value of node centrality
does not change unless the topology changes. The network dynamics isgenerated by interaction between users whose strength is asymmetric ingeneral. Network structure reflecting the asymmetric interaction between
users is modeled by a directed graph, and it is described by an asymmetricmatrix in matrix-based network model. In this paper, we showed an oscillation model for describing dynamics on networks generated from a certain
kind of asymmetric interaction between nodes by using a symmetric matrix. Moreover, we propose a new extended index of well-known two node
centralities based on the oscillation model. In addition, we show that the
proposed index can describe various aspect of node centrality that considers
not only the topological structure of the network, but also asymmetry oflinks, the distribution of source node of activity, and temporal evolution ofactivity propagation by properly assigning the weight of each link. The proposed model is regarded as the fundamental framework for different node
centralities.
key words: oscillation dynamics, node centrality, social network analysis

1.

Introduction

Recently, the survey “Digital in 2016” [1] for digital, socialand mobile usage was reported by the social media consulting company “We Are Social”. According to the survey, thenumber of social media users in the world is 2.31 billion,
and it is expected that its number will further increase in
the future. While an enormous amount of information is exchanged by many billion users through major social networking services (SNS), including Facebook, Twitter, Google+
and Instagram, information exchange manner between users
heavily depends on the structure of actual social network ofusers. In such a situation, social network analysis which isthe process of investigating the structure of social networks
has been attracted attention, and dynamics for propagationof information or activity on the social network is an interManuscript received September 27, 2017.
Manuscript revised January 11, 2018.
Manuscript publicized February 1, 2018.
† The author is with the Graduate School of Information Sciences, Hiroshima City University, Hiroshima-shi, 731-3194 Japan.
†† The author is with the Graduate School of System Design,
Tokyo Metropolitan University, Hino-shi, 191-0065 Japan.
a) E-mail: takano@hiroshima-cu.ac.jpb) E-mail: aida@tmu.ac.jp
DOI: 10.1587/transcom.2017EBP3370

Fig. 1

Examples of node centralities.

esting research object [2]–[4]. For social network analysis
based on graph theory, various indices have been appliedin order to describe the characteristics of networks: graphdiameter/radius, average path length and node density [5],degree distribution [6], [7], cluster coefficient [8]–[10], andvarious node centralities [11]–[14]. Most of these indices
are decided by the topological structure of the network, butsome of them are strongly related to user dynamics reflecting
the utilization state of the network. In this paper, we focus
on node centralities which are such indices.
Node centralities are indices that express the strengthof importance of node. Figure 1 shows examples of typicalnode centrality: the degree centrality and the betweenness
centrality. The black nodes have the highest degree centrality, that is, their node degree is high and they strongly
contribute propagation on the network. The gray node has
the highest betweenness centrality, that is, a lot of shortest paths between nodes are passing through the node andit is the essential node to relay. In this way, by choosing
different measures, we can define different node centrality.
Note that the node centrality is determined by the topologicalstructure of the network. For example, it is inappropriate tojudge that betweenness centrality measure of the gray nodeand degree centrality measure of the black node in the right
subnetwork are high in the situation where the communication is performed only in the left subnetwork in the figure,because the node centrality does not reflect the utilization
state of the network. In other words, the conventional node
centrality is an index assuming the uniform communication
on a given network structure. In general, the informationexchange in social networks and the utilization state in information networks are not uniformed spatially, and origin
nodes of information propagation providing new topics are

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

TAKANO and AIDA: REVEALING OF THE UNDERLYING MECHANISM OF DIFFERENT NODE CENTRALITIES BASED ON OSCILLATION DYNAMICS

unevenly distributed. Also, it is unlikely that a situation
where all nodes communicate directly. In view of thesefacts, it is significant for practical purposes to extend thenode centrality reflecting the utilization state of the network.
When a network structure is expressed algebraicallyby using a matrix, node-specific property and link-specificproperty are represented by the diagonal components and thenon-diagonal components of the matrix, respectively. For
this reason, an undirected/directed network is represented
by a symmetric/asymmetric matrix associated with the network. In spectral graph theory, the characteristics of network
structure is analyzed by studying eigenvalues and eigenvectors of the Laplacian matrix which represents the structureof the associated network [15]–[17]. The fact that the Laplacian matrix is symmetric is crucial in process to investigate
its eigenvalues and eigenvectors, because symmetric matrices always can be diagonalized [18], [19]. However, various
dynamics on social networks is generated as a result of theinteraction between nodes (humans, computers and contents,etc.), and the strength of such interaction depends on the direction of links in general, that is, it has asymmetric link
structure.
For problems mentioned above, in [20], [21], we focused on some types of link asymmetry that is reducible torepresent as the characteristic of the node, and represents the
structure of a directed graph with a symmetric matrix. We
call the network having this type of link asymmetry as thesymmetrizable directed network. Moreover, we considered
the model of oscillation dynamics on symmetrizable directed
networks and analyzed oscillation dynamics on symmetrizable directed networks which describes the propagation ofsome activities on the networks through the networks. In[22], we proposed a new index that is an extension of theconventional node centralities (degree and betweenness centralities). Unlike conventional node centralities, our proposed index can reflect various network situations including
topological structure of network, asymmetry of links, the distribution of source node of activity, and temporal evolutionof activity propagation. These characteristics have practical advantages. Note that the simulation evaluation in [22]focuses on the simple network model which has undirected
and non-weighted links. In this paper, we discuss generally
extension of node centralities based on the oscillation model
on symmetrizable directed networks. In addition, we showthat our proposed index can describe various node centralities by properly assigning the weight of each link, assuming
the directed and weighted network model through simulation experiments. Moreover, we show that the extension of
our proposed index can express the temporal evolution ofactivity propagation and the damped case with time.
The rest of this paper is organized as follows: First,
in Sect. 2, we show the outlines of some conventional node
centralities and take a brief look at applications of them forthe related work. For preliminary of our study, in Sect. 3,
after definition of the Laplacian matrix for symmetrizable
directed networks, we introduce the scaled Laplacian matrix
for describing asymmetric node interactions by a symmetric1821

matrix [20], [21]. In Sect. 4, we analyze the solutions of theequation of motion for non-damped and damped oscillation
model that can describe dynamics on networks. In addition,
we mathematically clarify the relation between the proposed
indices by oscillation model and several node centralities
in Sect. 5. As demonstration, we compare the proposed
indices by the oscillation model with several conventional
node centralities by the simulation and show the validityof the proposed model. In Sect. 6, we extend the proposed
index so as to describe the temporal evolution of activity
propagation and express the damped dynamics on networks.
Finally, we conclude this paper in Sect. 7.
2.

Related Works for Node Centralities

In this section, we outline some conventional node centralities and show application examples to control and management of information networks.
Node centralities are indices of which nodes are more
central than the others. The idea of first classic centralities
as applied to social network and human communication was
introduced by Bavelas [23], [24]. Moreover, Freeman [11]categorized three measures of node centralities based onthese three features (it has more links, it can reach all theothers more quickly, and it controls the flow between theothers) as follows:• Degree centrality : It is the simplest measure of the node
centralities and is defined as the number of links thata node has [23]. Degree centrality has generally been
extended to the sum of link weights for the weighted
networks which has the weighted directed links [26]–[29].
• Closeness centrality : Closeness was defined in connected graph by [23]. It is a centrality measure whichis calculated as the inverse of the sum (or average) of
the length of the shortest paths between the node andall other nodes [30]. For disconnected network, theextension of closeness has been proposed which uses
the harmonic mean of distances rather than the arithmetic mean [29], [31], [32]. Moreover, the directed andweighted network was studied by [27], [33].
• Betweenness centrality : Betweenness centrality is defined based on the number of shortest paths from allvertices to all others that pass through that node [23].
The importance of this conception of node centrality isin the potential of a node for control of information flowin the network. It is similar to the stress centrality [34]defined as the number of shortest paths but provides amore informative centrality index. Generalization of
betweenness centrality to directed graphs and weighted
graphs is shown in [29], [35]. Moreover, [36] proposeda new algorithm for calculating betweenness faster.
One of node centralities other than the above Freeman’scategorized measures is the eigenvector centrality [37] basedon a eigenvector for the greatest eigenvalue of the adjacency
matrix. Bonacich power centrality [38] and PageRank [39]

IEICE TRANS. COMMUN., VOL.E101–B, NO.8 AUGUST 20181822

can be viewed as modifications of the eigenvector centrality.
For applications of node centralities, the concepts of many
proposed node centralities are used by identifying the mostinfluential (key) persons in a social network [40], [41] andsuper-spreaders of disease [42], [43] as well as proposal ofcontrol algorithm of infrastructures in information network(e.g. ad hoc network and sensor network) [44]–[47].
3.
3.1

Symmetric Scaled Laplacian Matrix for Describing
the Link Asymmetry

Example of Laplacian matrix.

Definition of the Laplacian Matrix

In graph theory, network structure is frequently expressedby a matrix. Let us consider a loop-free directed graph
G = G(V, E) with n nodes: V = {1, 2, . . . , n} is the set ofnodes and E is the set of directed links. The directed linkfrom node i to node j is expressed by (i → j) ∈ E. In
addition, let the link weight for link (i → j) be wi j > 0.
Then, we define the n × n square matrix A = [Ai j ] asfollows:(
wi j ((i → j) ∈ E),(1)
Ai j :=
0 ((i → j) < E).
This matrix represents link presence and its weights, and iscalled the (weighted) adjacency matrix. If wi j = w ji for all iand j, G is a undirected graph, and A is a symmetric matrix.
The adjacency matrix can be used to investigate the network
structure algebraically. If wi j = 1 for all i and j, the (i, j)
component of A k shows the number of paths with the lengthof k from node i to node j.
Next, we define the weighted out-degree d i of node i(i = 1, . . . , n) asXd i :=
wi j ,(2)j ∈∂iwhere ∂i denotes the set of nodes adjacent to node i. Degree
matrix D of the weighted out-degree is defined as
D := diag(d 1, d 2, . . . , d n ).
If all link weights are wi j = 1, d i denotes out-degree, i.e. thenumber of outgoing links from node i.
Based on the above preparation, we define the Laplacianmatrix L of the directed graph G as follows:
L := D − A.

(3)

An example of the Laplacian matrix for an asymmetric graphis shown in Fig. 2.
3.2

Fig. 2Symmetrization of Laplacian Matrix and the Scaled
Laplacian Matrix

Although the Laplacian matrix L for directed graph is generally the asymmetric matrix, we can classify the link asymmetry into two types. Figure 3 shows typical examples ofFig. 3

Typical examples of asymmetric interaction between nodes.

link asymmetry. (a) shows a hub type relation, for example
the relation of a major blogger and its followers. The link
asymmetry in (a) can be expressed by the node characteristic
which is the strength of node. The node characteristic means
a numerical representation of the strength of node and is aconsistent value. On the other hand, (b) shows a cyclic relation like rock-paper-scissors. In this case, it is not possible
to define the consistent value of the strength of nodes (it isunknown which node is the strongest/weakest). Therefore,
the relation of (b) is defined by not the node characteristic but
the pure link characteristic. Let us consider the conditions
that the asymmetric relation is classified in (a) which can be
expressed by using node characteristics.
The Laplacian matrix L has the left eigenvector tm
associated with the left eigenvalue 0, that is,m L = 0.

(4)t

For each component mi of the left eigenvector tm =(m1, . . . , mn ), we assume the following condition:
mi wi j = m j w ji(≡ ki j ),(5)

where mi > 0. If the condition (5) is satisfied, the network isclassified into the type (a) in Fig. 3 and the link asymmetry
in directed network can be reduced to node characteristics
in an undirected graph. We call a network satisfying (5) asa symmetrizable directed network. Here, mi represents thenode characteristic (node strength) of the node i, and wi j
represents the link weight from node i to node j in a directed
network. The physical meaning of this condition (5) will be
discussed by the oscillation model for describing dynamics
on networks in the next section.
For symmetrizable directed netwrorks, the link asymmetry of L can be expressed by using a symmetric Laplacianmatrix, and the procedure is as follows. First, we introduce

TAKANO and AIDA: REVEALING OF THE UNDERLYING MECHANISM OF DIFFERENT NODE CENTRALITIES BASED ON OSCILLATION DYNAMICS

1823

the eigenvalues of S are nonnegative. We sort the eigenvalues
in ascending order as 0 = λ 0 ≤ λ 1 ≤ λ 2 ≤ · · · ≤ λ n−1 . We
can choose the eigenbasis v µ (µ = 0, 1, . . . , n − 1) as the
eigenvector of S with length of 1 associated with λ µ , which
satisfy
S v µ = λ µ v µ,v µ · vν = δµν,

(10)

where δµν denotes the Kronecker delta.
4.

Fig. 4In this section, we consider the solution of the equation of
motion that describes oscillation phenomena on networks.

Example of symmetrization of Laplacian matrix.

4.1
a symmetric Laplacian matrix L as L := D − A for an undirected network as follows: The adjacency matrix A = [Ai j ]is defined as(
ki j ((i, j) ∈ E),(6)
Ai j :=
0 ((i, j) < E),
and the degree matrix D is expressed as
n
n
n
X
X
X
*
.
An j +/ .
A2j , . . . ,D = diag
A1j ,
j=1
j=1
, j=1

Since k i j = k ji , L is a symmetric Laplacian matrix fora certain undirected graph. By using L, the asymmetric
Laplacian matrix L is expressed as
L = M −1 L,(7)where the scaling factors M of nodes is defined as M :=diag(m1, m2, . . . , mn ) to reduce the link asymmetry to thecharacteristics of the node. Figure 4 shows a simple exampleof the procedure which leads to (7).
Next, we define the scaled Laplacian matrix as
S := M −1/2 L M −1/2 .

(8)Note that S is a symmetric matrix as well as L.
By multiplying M 1/2 to the right eigenvalue equation
of L,
Lx=λx
from the left, we have
M 1/2 L x = S (M 1/2 x) = λ (M 1/2 x).

(9)This means that the scaled Laplacian matrix S has the same
eigenvalues of L and its eigenvector is expressed as y :=M 1/2 x. Since the quadratic form of S is
ySy =

t

!
yj 2
yi
ki j √ − √
≥ 0,
mj
mi
(i, j) ∈E
X

Oscillation Model on Networks Based on Asymmetric Interaction between Nodes

Minimal Model Describing Nodes’ Interaction

Let us consider the information propagation targeted by theoscillation model. In this paper, we do not propose models
that have the characteristics of specific information propagation, but pursue the so-called minimal model. The minimalmodel is an universal model as simplest as possible.
The minimal model is determined by considering not
only a rule that expresses the user’s state but also somerules that describe the interaction between users, as follows:
The state of each user is represented by a one-dimensionalparameter. Although multi-dimensional parameters may berequired to describe the user’s state, we select the simplest
model that the user’s state affecting the interaction between
users can be represented by one-dimensional parameter. On
the other hand, as rules for interaction between users, (1)if the difference in state between the user and the adjacentuser is 0, no interaction occurs (2) restoring-power acts sothat the difference in state between users becomes small(3) the strength of the restoring-force is represented by amonotonically increasing function of the difference against
state between users. We do not assume that the user’s state is
the observable quantity for the model. The interaction acts
according to the state of the user and the adjacent user, and nointeraction occurs when all users are in the same state. The
oscillation model shown in Sect. 4.2 is linearized so that thestrength of restoring-force is proportional to the difference
in state between users in the minimal model. Let us consider
the model linearization by using the well-known Ohm’s law
as an example.
Figure 5 is an example of the characteristic of the current
I when the voltage V is applied to the resistance. In general, no current flows when the voltage is 0, and the current
monotonically increases as the voltage increases. However,there is no proportional relationship between them. This isbecause the heat generation of the resistance prevents thecurrent from flowing. However, there is an approximately
proportional relationship between the current and the voltage
when the voltage is not large, and this relationship is known
as Ohm’s law. This law means a first order approximation
by Taylor expansion around V = 0 as a function of current I
for voltage V .

IEICE TRANS. COMMUN., VOL.E101–B, NO.8 AUGUST 20181824

d2 x(t)= −L x(t).
dt 2

(12)

The equation of motion (12) reflects the asymmetric characteristics of links described by an asymmetric Laplacianmatrix L.
If the directed graph can be symmetrized (that is, (5)is satisfied), we have the following wave equation as theequation of motion
M
Fig. 5 Example of the characteristic of the current I when the voltage V
is applied to the resistance.

The idea of Ohm’s law is a good example to explain
the linear approximation of the strength of interaction between users. Although the strength of interaction between
users may be described by using a nonlinear function of
the difference in the states of users, a first order approximation is possible when the difference in state between users
is not large. Therefore, it was found that the linear interaction model is an extremely universal model. Of course, themodel does not hold the linearity when the characteristic ofnonlinearity is very strong, but nonlinear correction can beconsidered based on a linear model. Thus, the oscillation
model expressing the interaction between users is intended
not to describe a specific information propagation but to describe the common features in wide range of user interaction
models, and the pursuit of the minimal model makes thispossible.
Note that there is no practical meaning unless this minimal model is linked with observable information at all. In
the oscillation model derived from the minimal model, theusefulness of this minimal model is indicated by the factthat the oscillation energy of nodes can reproduce the concept of the conventional degree centrality and betweenness
centrality. Therefore, all the propagation of activity on asymmetrizable directed network which has been discussed
using the conventional degree centrality and betweenness
centrality is understood through the oscillation model.
4.2

Non-Damped Oscillation Model on Networks

Based on the idea of the minimal model in the previous
section, the equation of motion for x i which is the state ofnode i can be obtained by the linear restoring-force between
nodes as follows:X
d2 x i=−wi j (x i − x j ),
2
dt
j ∈∂i

(11)

where wi j is a proportionality coefficient indicating thestrength of interaction between node i and node j, and denotes the weight of a directed graph.
Here, by using the vector x = (x 1, . . . , x n ), (11) canbe expressed as

d2 x(t)= −L x(t),
dt 2

(13)

where L is a symmetric Laplacian matrix of the undirected
graph and the scaling factor M. The model representedby (13) is equivalent to the following dynamic oscillation
model.
Let the weight x i of node i be the displacement fromthe equilibrium point, and let the restoring-force be proportional to the difference between the displacements of node i
and its adjacent node. The displacement of the node is a onedimensional parameter representing the user’s state, and theequilibrium point is the origin of the coordinates for digitizing the state of the user and can be decided arbitrarily. Since
only the difference in user’s state affects the interaction, theposition of the origin has no essential meaning. Figure 6
shows a representative image of our oscillation model. To
represent diverse oscillating behavior, we allow the spring
constant of each link to be different and the mass of eachnode to also be different. Let a spring constant for the link
between node i and node j be the link weight k i j > 0. In
addition, we assign mass mi > 0 to each node i. The nodecharacteristic mi in (5) corresponds to the mass of node in theoscillation model. In addition the condition (5) represents
Newton’s third law (about the law of action and its reaction).
The displacement of the node is generally a complexvalued function as a result of solving (12) or (13) and is
not an amount that can be observed directly. However, theoscillation energy obtained by squaring the displacement
leads to the concept of the traditional graph theory as the node
centrality. Such aspects also appear in quantum mechanics.
The wave function representing the state of the system inquantum mechanics is generally a complex-valued function
and is not observable, but the squared amount is associatedwith observable quantities.
By introducing the vector y(t), asy(t) = M 1/2 x(t),the equation of motion (12) can be expressed as
d2 y(t)= −S y(t).
dt 2

(14)

Thus, we can describe the equation of motion for the oscillation dynamics on networks using the symmetric matrix
S.
In order to solve the equation of motion (14), we expand
y(t) asTAKANO and AIDA: REVEALING OF THE UNDERLYING MECHANISM OF DIFFERENT NODE CENTRALITIES BASED ON OSCILLATION DYNAMICS

1825

n independent equations of motion for each oscillation modeµ, asd2 aµ (t)daµ (t)+γ+ ωµ2 = 0.
dt
dt 2

(21)

In order to solve (21), let us consider the characteristic equation of (21):α 2 + γα + ωµ2 = 0.
Fig. 6 Representative Image of the Oscillation Model on Symmetrizable
Directed Networks.

y(t) =n−1X

aµ (t) v µ,

(15)

µ=0

by the eigenbasis v µ of S. By substituting (15) into (14), we
obtain n independent equations of motion for each oscillation
mode µ as
d2 aµ (t)= −λ µ aµ (t),dt 2

The solutions of the characteristic equation are obtained asqα± = −(γ/2) ± (γ/2) 2 − ωµ2 (double-sign corresponds).
The solutions of the equation of motion (21) are classified
into three categories, depending on the solution of (22), as
follows. In case that α± are complex roots ((γ/2) 2 < ωµ2 ),the solution describes damped oscillations,√ 22aµ (t) = aµ (0) e−(γ/2)t e±i ωµ −(γ/2) t .
(23)
In case that α± are double roots ((γ/2) 2 = ωµ2 ), the solution
describes the critical damping,

and the solution isaµ (t) = (aµ (0) + cµ t) e−(γ/2)t ,aµ (t) = cµ e±i (ωµ t+θµ ),(16)√

where cµ is a constant, ωµ = λ µ , i = −1 and θ µ denotes
phase for the oscillation model. From the above, we have thesolution of (14) aspy(t) =n−1Xcµ e±i (ωµ t+θµ ) v µ .

(17)

µ=0

n−1
X
x(t) = M −1/2 *.
cµ e±i (ωµ t+θµ ) v µ +/ .
,µ=0-aµ (t) = cµ+ eα+ t + cµ− eα− t ,

M

dx(t)
d2 x(t)+Mγ= −L x(t),
dt
dt 2

(19)

where γ > 0 is a constant called the damping coefficient.
By using the vector y = M 1/2 x, we can symmetrize theequation of motion as
d2 y(t)dy(t)+γ= −S y(t).
2
dt
dt

n−1
X
x(t) = M −1/2 *.
aµ (t) v µ +/ .
,µ=0
-

5.

Since an oscillation is damped with time in actual situation,
we should consider the damped oscillation model. Since
the damping force is usually proportional to the velocity ofnode and its mass, the equation of motion for the damped
oscillation can be expressed as(20)

By applying the similar procedure using (15), we obtain(25)

where cµ+ and cµ− are constants.
Therefore, we obtain the solution of the equation of
motion (19) for the damped oscillation as(18)

Damped Oscillation Model on Networks(24)

where cµ is a constant. Finally, in case that α± are two
distinct real (negative) roots ((γ/2) 2 > ωµ2 ), the solution
describes overdamping,

In addition, the solution of (12) is

4.3

(22)

Oscillation Model and Node Centralities

In this section, we consider actual meaning of oscillation
models on networks proposed in the previous section. First,
we show the relationship between oscillation energy for eachnode and the node centrality, and propose the new node centrality index by using the oscillation energy. The proposed
index can reproduce the conventional degree centrality andbetweenness centrality as simple and special cases.
It would be inappropriate to suppose that the conceptof the node displacement is unnecessary and the model canbe constructed only with node centrality, even though thenode centrality can be observed but the displacement of thenode cannot be observed. In generalizing the node centrality
as the importance of the node and considering its temporal
evolution and propagation on the network, the oscillation
phenomenon based on the displacement of node is necessary as the underlying structure. In addition, by considering the oscillation phenomenon, it is possible to understandIEICE TRANS. COMMUN., VOL.E101–B, NO.8 AUGUST 20181826

the different centralities (degree centrality and betweenness
centrality) in the same framework and to derive extended
concept of node centrality reflecting the utilization state of
the network.
5.1

Oscillation Energy and Degree Centrality
Fig. 7Let us consider the behavior of the solution (18) for nondamped oscillation on networks. The solution (18) is acomplex valued function, and so it is difficult to interpret as
an actual quantity that can be directly observed. Therefore, it
is desired to make a non-negative valued index that describes
the strength of activity of each node on networks.
As the first step, we introduce the oscillation energy.
Since the oscillation energy of a simple harmonic oscillator
for node mass m, amplitude A and angular frequency ω is1
2 2
2 m ω A , the oscillation energy Ei for node i is expressed
as
!2
n−1
X
1
2
2 vµ (i)ωµ |aµ (t)| √Ei = mi2
miµ=0

Fig. 8 Oscillation energy for each node in undirected graph (M = I,
M = D 2 ).

n−1

=

1X 2
ω |aµ (t)| 2 (vµ (i)) 2,2 µ=0 µNetwork model (undirected graph).

(26)

where v µ = t(vµ (1), . . . , vµ (n)). Note that vµ (i) is a real
number because S is a real symmetric matrix.
As the initial condition of the wave equation (12), let us
give the displacement only at a certain node. We define thenode as a source node of activity. First of all, let us consider
the situation that the source node of activity is chosen at
random. In this case, all the oscillation modes√ contribute at
the same strength. If we choose |aµ (t)| = 2 for all µ, we
have
P
n−1
X
j ∈∂i k i j
2Ei =λ µ (vµ (i)) == di .
(27)
miµ=0
The reason of the second equality of (27) is justified by
the following discussion: S can be diagonalized by using
the orthogonal matrix P = (v 0, . . . , v n−1 ) as Λ = tP S P,
where Λ = diag(λ 0, . . . , λ n−1 ). By using S = P Λ tP, we
can recognized that Ei is the ith diagonal component of S.
Therefore, Ei gives the degree centrality of node i.
In order to demonstrate the actual meaning of the proposed index, we evaluate the oscillation energy Ei for nodei using the network model shown in Fig. 7.
In this paper, we show that it is possible to derive the extended concept of node centrality from the oscillation modelon the symmetrizable directed network. The property thatthe oscillation energy of each node results in degree centrality and betweenness centrality under specific conditions
is given mathematically in the symmetrizable directed network. Therefore, the above property is established in “any”
symmetrizable directed network. This paper gives somedemonstrations by using a specific network model, but it ismathematically guaranteed that similar results can be obtained even for other symmetrizable directed networks. For
example, the large-scale property and the scale free property
which the social network has do not affect the evaluation results in this paper. Note that general directed networks that
do not satisfy (5) are not considered, since this paper focuseson symmetrizable directed networks. The general directed
network can also be expressed as an oscillation model, but it
corresponds to the oscillation phenomenon which does notsatisfy Newton’s third law. In this case, the oscillation energyof the whole network can be defined, but it is generally impossible to distribute it to the oscillation energy of each node.
The divergence of oscillation energy has been analyzed anddiscussed as a flaming phenomena in networks [48], [49].
Figure 8 shows the evaluation results of the oscillationenergy Ei in case that the weight of all links wi j = 1, and√|aµ (t)| = 2 for all oscillation modes µ. The results areusing mass matrix M = I (left) and M = D2 (right). Figure 8(a) and (b) correspond to the case that the interaction
between nodes is symmetric (M = I ), and an example ofasymmetric node interaction (M = D2 ), respectively. Therefore, Fig. 8(b) can be considered as an extension of the degree
centrality for asymmetric interaction between nodes.
5.2

Oscillation Energy and Betweenness Centrality

The betweenness centrality is a well-known node centrality.
While [22] has stated the betweenness centrality for an undirected graph, we explain the betweenness centrality for a
directed graph to help easy understanding of characteristics
of node centralities in the following subsections.
Let the number of shortest paths from node j to node kbe σ jk , and the number of those paths passing through thenode i be σ jk (i) for the network which has the directed links.

TAKANO and AIDA: REVEALING OF THE UNDERLYING MECHANISM OF DIFFERENT NODE CENTRALITIES BASED ON OSCILLATION DYNAMICS

1827

The betweenness centrality Cbt (i) for node i is defined as
Cbt (i) :=σ jk (i).
σ jkj, k ∈V\{i }X(28)The normalized betweenness centrality C̄bt (i) is defined asC̄bt (i) :=Cbt (i).
(n − 1) (n − 2)

The physical meaning of C̄bt (i) is the ratio of the number ofshortest paths including node i to the number of permutationsof node pairs in V \{i}, that is n−1 P2 .
Here, let us set the link weight wi j as the number of theshortest paths passing through the link (i → j). Then the(weighted) degree of node i can be expressed as
X σik (i)σ jk (i)di =wi j =
+
,
σ jk
σik
j ∈∂i
j, k ∈V\{i }k ∈V\{i }X

X

Fig. 9(29)(30)

Network model with weighted directed links.

Fig. 10 Undirected network graph where the link asymmetry in weighted
directed network is reduced to node characteristics.

where V\{i} is the set of nodes excluding node i. The second
equality of (30) means the sum of the number of shortest
paths passing through node i and shortest paths started fromnode i. Since the number of shortest paths that are terminatedat node i is n − 1, we haved i = Cbt (i) + (n − 1).

(31)

Let us consider the situation that the source node ofactivity is chosen at random. In this case, all the oscillation
modes contribute at the same strength. If we choose |aµ (t)| =√2 for all µ and mi = 1 in (26), we have
Ei = d i = Cbt (i) + (n − 1).

(32)

If there is a node that any shortest paths never pass through,Emin := min Ei = n − 1,i ∈Vand that is to say that the difference Ei − Emin is equal to thebetweenness centrality.
5.3

Typical Examples of the Correspondence between Oscillation Energy

In this subsection, we take note of the betweenness centrality
for the simulation evaluation, and we clarify that the oscillation energy for the oscillation model corresponds to thesecentralities by properly assigning link weight between nodes
as shown in Sect. 5.2.
Let us consider the directed and weighted graph forthe network model used in the simulation evaluation. The
network model (Fig. 9) has 23 nodes and several weighted
links. The numerical character in each circle and that ofbeside each link denote node ID and the weight of eachlink, respectively. For example, the weight of the directed
link from node 1 to node 2 is 1.0. We can reduce the link
asymmetry in directed network to node characteristics in an
undirected graph as shown in Sect. 3.2. Incidentally, Fig. 10

Fig. 11(γ = 0).

Proposed index Ei −(n−1) and the betweenness centrality Cbt (i)is the undirected network which is derived from the weighted
directed network Fig. 9. We evaluate the proposed model byusing the weighted directed network model as Fig. 9.
Next, we set the link weight as the number of the shortest
paths passing through the link for the network model (Fig. 9)
and evaluate the oscillation energy for each node. Figure 11
shows the evaluation result of the betweenness centrality
Cbt√
and the energy Ei − (n − 1) in case that |aµ (t)| = 2 for all
oscillation modes µ and the damping coefficient γ = 0. We
can see from this figure that the energy Ei − (n − 1) is equal
to the betweenness centrality Cbt for each nodes as shown in(32).
Consequently, the proposed index by the oscillation energy can describe several conventional node centralities byproperly assigning each link weight, even if the topological structure of the network is asymmetric as the weighted
directed network (Fig. 9).
6.

Extended Node Centrality for Describing Propagation of Node Activity

6.1

Oscillation Energy for a Certain Source Node and NodeCentrality

The conventional node centralities do not consider the distribution of source nodes, while they depend on the topo-

IEICE TRANS. COMMUN., VOL.E101–B, NO.8 AUGUST 2018

1828

concerning index that depends on time for the following
two reasons:Fig. 12 Oscillation energy for each node in weighted directed graph(source node is node 1 and 12, γ = 0).

Fig. 13 Oscillation energy for each node in weighted directed graph. Thisshows the oscillation energy superposed for all source nodes.

• The first reason is to represent the propagation of the
wave in the network. We consider the initial state where
the particular node is selected as the source node. The
oscillation energy of a distant node from the source nodeis also positive constant and does not change, even if it
is before/after the arrival time of the wave. Therefore,
wave propagation can not be described by using theoscillation energy.
• The second reason is the oscillating phenomenon on
the network is damped with time in general. We want
to describe temporal evolution of the strength of nodeactivity.
We consider the kinetic energy of the node as a timedependent energy-concerning index. The kinetic energy is
given by 21 m (dx(t)/dt) 2 for the node position x(t) and themass m. If x(t) is a complex valued function, there are two
ways for calculation of the kinetic energy:(i). calculation of the kinetic energy from the only real partof dx(t)/dt, that is 21 m (Re[dx(t)/dt]) 2 , or

logical structure of network. Generally, the real importanceof nodes in a network should not be defined only by the
topology, because the frequency and the amount of information distribution are different among source nodes. In thissubsection, we confirm the oscillation energy for each node
when a certain node is a source node of activity. We use
the weighted directed network model as Fig. 9 and γ = 0.
Figure 12 shows the evaluations of the oscillation energy
for each node with respect to the different source node ofactivity. As the initial condition, a displacement of node
1 (Fig. 12(a)) or 12 (Fig. 12(b)) is set to 1 and that of theother nodes is set to 0. The results show that the oscillationenergy strongly depends on a position of the source node ofactivity. While the number of out-going links of node 12
is larger than that of node 1, the oscillation energy in (a) isrelatively larger than that in (b) because the sum of out-going
link weight of node 1 (sum = 2.0) is larger than that of node
12 (sum = 1.65). Note that by superposing oscillation energy for all source nodes, we have the degree centrality ofFig. 13. Therefore, the proposed oscillation energy can be
regarded as an extended index of well-known degree centrality. Consequently, the oscillation energy of each node gives
extensions of the degree centrality that can reflect link asymmetry and distribution of source nodes, and corresponds tothe original degree centrality in the simplest case.

as the time-dependent and energy-concerning index. Here,arbitrary constants are set by the initial conditions as follows: In the case of the damped oscillation, because allnodes stops at the time t = 0 and the time differential of
the oscillation part of (23) is 0, aµ (0) is a real number.
Therefore, daµ (t)/dt|t=0 = 0 for critical damping (24) andoverdamping (25) brings

6.2

cµ =

Kinetic Energy and Time-Dependent Node Centrality

In the non-damped oscillation, the kinetic energy and potential energy is alternating each other with time, but theoscillation energy, which is given by the sum of the kinetic
energy and potential energy, is not changed with time. So,
the oscillation energy (26) does not depend on time.
However, it is necessary to consider the energy-(ii). calculation of the kinetic energy from a complex valuedx(t)/dt, that is 12 m |dx(t)/dt| 2 .
In the former case (i), the kinetic energy is 0 if the nodestops. For the initial condition, we set that the source nodestops and displacement of it is not 0 at t = 0. Since we want
to recognize that the wave arrived at the source node at theinitial time, it is necessary that the initial kinetic energy to bea positive value at the source node, even if the source nodestops. In case (ii), the initial kinetic energy of the source
node is positive and that is due to the contribution of theimaginary part.
From the above discussion, we propose the kinetic energy EiK (t) for node i at time t defined as
EiK (t) :=1
dx i (t)
mi
2
dt

2

=

2

1 d yi (t)
,
2 dt

−α−
α+
γ
aµ (0), cµ+ =aµ (0), cµ− =aµ (0).
2α+ − α−α+ − α−Next, we evaluate the kinetic energy EiK (t) for eachnode as an extension of the degree centrality and betweenness
centrality. Network model for evaluations uses the weighted
directed graph shown in Fig. 9. First, we set the link weight
for each link as the same value 1. Figure 14 shows the
temporal evolution (t = 1, 3, 5) of the kinetic energy EiK (t)TAKANO and AIDA: REVEALING OF THE UNDERLYING MECHANISM OF DIFFERENT NODE CENTRALITIES BASED ON OSCILLATION DYNAMICS

Fig. 14 Temporal evolution of the kinetic energy for the weighted directed
graph (source node 3 or 12, γ = 0).

Fig. 15 hEiK i superposed for all the 23 source nodes in the weighted
directed graph (γ = 0).

when the displacement of the source node 3 or 12 is 1, thedisplacement of the other nodes is 0 for the initial condition,and the damping coefficient γ = 0. We can see from thisfigure that the kinetic energy EiK (t) expresses the behaviorof wave propagation from the source node.
Next, we evaluate the average of the kinetic energy
Z T
1K
hEi i :=EiK (t) dt
T 0
for an interval T. If we set the interval T = 1000 andsuperpose the hEiK i for all the 23 source nodes, the result is
proportional to the degree centrality shown in Fig. 15. The
value of hEiK i in this figure is multiplied by a constant number(2.0) to make it easy to compare the energy hEiK i with thedegree centrality for each node. Let us discuss this result:
In case of the non-damped oscillation model, the oscillationenergy is conserved and static. As shown in Sect. 5.1, theoscillation energy Ei gives the degree centrality of node i.
In addition, the oscillation energy is equal to the sum of
the kinetic energy and the potential energy, and the amountof the kinetic energy is equivalent to that of the potential
energy. Therefore, the degree centrality is twice as large as
the kinetic energy in this case. We can see from Figs. 14
and 15 that the kinetic energy of node is an extension of
the degree centrality that can describe temporal evolution ofdegree centrality.
Next, we set the link weight as the number of the shortest
paths passing through the link for the network model (Fig. 9)
and evaluate the characteristics of kinetic energy.
Figure 16 shows the temporal evolution (t = 1, 3, 5)of the kinetic energy EiK (t) for the source node 3 or 12

1829

Fig. 16 Temporal evolution of the kinetic energy for the weighted directed
graph (the weight for each link is the number of the shortest paths passing
through the link, γ = 0).

Fig. 17 hEiK i superposed for all the 23 source nodes in the weighted
directed graph (the weight for each link is the number of the shortest paths
passing through the link, γ = 0).

for the initial condition, and Fig. 17 is the evaluation resultcomparing the betweenness centrality Cbt with the energy
hEiK i × 2 − (n − 1) for all the 23 source nodes. In (32),the oscillation energy Ei is equal to Cbt (i) + (n − 1). Theenergy hEiK i × 2 − (n − 1) means the oscillation energy which
is double the kinetic energy minus Emin . We can see fromthese figures that the energy hEiK i × 2 − (n − 1) is equal to thebetweenness centrality Cbt for each nodes and our proposed
index can express the temporal evolution of Cbt by using the
kinetic energy hEiK i.
6.3

Node Centrality for Different Damping Factors

Regarding the non-damped oscillation mode (the damping
coefficient γ = 0), we have evaluated proposed new indices(the oscillation energy and the kinetic energy) in previous
sections. In this subsection, we focus on the damped oscillation model. As shown in Sect. 4.3, the magnitude relation between the damping coefficient γ and the oscillation
frequency ωµ for each oscillation mode µ influences the solution aµ of the equation of motion: that is, for each µ,aµ describes (1) the damped oscillation (γ/2) 2 < ωµ2 ), (2)the critical damping ((γ/2) 2 = ωµ2 ), or (3) the overdamping ((γ/2) 2 > ωµ2 ). Here, for the weighted directed graph(Fig. 9), the distribution of the oscillation frequency ωµ foreach oscillation mode µ is shown in Fig. 18.
We investigate the characteristics of the oscillation energy in the damped oscillation model where has the damping
coefficient γ = 0.2, 0.4, 0.8. Note that the oscillation energy

IEICE TRANS. COMMUN., VOL.E101–B, NO.8 AUGUST 2018

1830

Fig. 21

Temporal evolution of oscillation energy for each node in γ = 0.4.

Fig. 18 Oscillation frequency ω µ for each oscillation mode µ for theweighted directed graph.

Fig. 19

Temporal evolution of oscillation energy for each node in γ = 0.2.

Fig. 22 Oscillation energy (multiplied by a constant number) and thedegree centrality for each node for γ = 0.4, t = 20.

Fig. 23

Temporal evolution of oscillation energy for each node in γ = 0.8.

Fig. 20 Oscillation energy (multiplied by a constant number) and thedegree centrality for each node for γ = 0.2, time = 50.

in previous evaluations does not change over time because
the value of the damping coefficient γ is 0.
If the damping coefficient γ = 0.2, the relation (γ/2) 2 <2ωµ (µ = 0, 1, 2, · · · , 22) holds for almost all the oscillation
mode µ (except for the minimum value 0 of ω22 ), that is, thesolution aµ (µ = 0, 1, 2, · · · , 21) describes damped oscillations and the solution a22 expresses overdamping. Figure 19
shows the temporal evolution (t = 5, 10 and 50) of the oscillation energy superposed for all source nodes, where thedamping coefficient γ = 0.2 and the network model is Fig. 9.
This figure shows that the behavior of the oscillation energy
does not change through passage of time if the damping coefficient is small as γ = 0.2, while the value of oscillationenergy for each node diminishes gradually. That is that theoscillation energy at some time is equal to the result at theother time multiplied by a constant number. If the oscillation energy is multiplied by a constant number for the resultat time 50, we obtain the result that the oscillation energy
corresponds to the degree centrality as shown in Fig. 20.
Next, in case of γ = 0.4 (γ/2 = 0.2), the solutionaµ (µ = 0, 1, 2, · · · , 20) describes damped oscillations anda21 and a22 express overdamping. Figures 21 shows the
temporal evolution of oscillation energy in γ = 0.4. Since
the damping coefficient γ is larger and oscillation modes ofFig. 24 Oscillation energy (multiplied by a constant number) and thedegree centrality for each node for γ = 0.8, t = 20.

overdamping increases, the values of the oscillation energy
declines more drastically than that in Fig. 19. Moreover,
the relative relation of the oscillation energy for each nodechanges over time: the oscillation energy at some time is“not” equal to the result at the other time multiplied by aconstant number. Figure 22 shows the comparison resultwith the degree centrality at time t = 20. We can see fromthis figure that the oscillation energy does not coincide withthe degree centrality in γ = 0.4.
In addition, in case of γ = 0.8, the solution aµ (µ =0, 1, 2, · · · , 19) describes damped oscillations and the othera20 , a21 and a22 are overdamping. Figures 23 and 24 show
results in γ = 0.8 and the oscillation energy completely
differs from the degree centrality. From the above, we cansee that the conformity between the degree centrality andthe oscillation energy depends on the value of γ. Notethat we obtain the same results for comparison between the

TAKANO and AIDA: REVEALING OF THE UNDERLYING MECHANISM OF DIFFERENT NODE CENTRALITIES BASED ON OSCILLATION DYNAMICS

oscillation energy and the betweenness centrality, and so weomit the explanation.
7.

Conclusion

This paper discusses generally extension of node centralities
based on the oscillation model. For the oscillation model todescribe the network dynamics, we proposed the oscillationenergy and the kinetic energy of each node as new indices ofnode centrality. Our proposed indices by the oscillation energy and the kinetic energy can correspond to various node
centralities by properly assigning the weight of each link. In
addition, while the conventional node centralities (e.g. degree and betweenness) depend on the topological structureof network and the value of node centrality does not change
unless the topology changes, our proposed extended indicescan describe various network situations including topological structure of network, asymmetry of links, the distributionof source node of activity, and temporal evolution of activity
propagation. Moreover, we can see from evaluation by thesimulation that the conformity between the node centrality
and the oscillation energy depends on the value of γ. Finally,in this research, we succeeded in understanding the different
centralities (degree centrality and betweenness centrality) inthe same framework. This contributes to the basic research
field of the social network by understanding the concept ofnode centrality at a more fundamental level.
Acknowledgments
This work was partly supported by JSPS KAKENHI Grant
Numbers 15K00431, 17H01737 and the Telecommunications Advancement Foundation (TAF).
References[1] Digital in 2016, http://wearesocial.com/sg/special-reports/digital2016[2] A. Mislove, M. Marcon, K.P. Gummadi, P. Druschel, andB. Bhattacharjee, “Measurement and analysis of online social networks,” Proc. ACM SIGCOMM conference on Internet measurement, pp.29–42, 2007.
[3] A. Sandryhaila and J.M.F. Moura, “Discrete signal processing ongraphs,” IEEE Trans. Signal Process., vol.61, no.7, pp.1644–1656,
2013.
[4] 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 Process. Mag., vol.31,
no.5, pp.80–90, 2014.
[5] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
[6] A.L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science, vol.286, no.5439, pp.509–512, 1999.
[7] A.L. Barabasi, R. Albert, H. Jeong, and G. Bianconi, “Power-law distribution of the world wide web,” Science, vol.287, no.5461, p.2115,
March 2000.
[8] D.J. Watts and S. Strogatz, “Collective dynamics of ‘small-world’
networks,” Nature, vol.393, no.6684, pp.440–442, 1998.
[9] S. Wasserman and K. Faust, Social Network Analysis: Methods andApplications, Cambridge University Press, 1994.
[10] T. Opsahl and P. Panzarasa, “Clustering in weighted networks,” Soc.
Networks, vol.31, no.2, pp.155–163, 2009.

1831[11] L.C. Freeman, “Centrality in social networks: Conceptual clarification,” Soc. Networks, vol.1, no.3, pp.215–239, 1979.
[12] L.C. Freeman, S.P. Borgatti, and D.R. White, “Centrality in valued
graphs: A measure of betweenness based on network flow,” Soc.
Networks, vol.13, no.2, pp.141–154, 1991.
[13] P.J. Carrington, J. Scott and S. Wasserman, Models and Methods in
Social Network Analysis, Cambridge University Press, 2005.
[14] K. Stephenson and M. Zelen, “Rethinking centrality: Methods andexamples,” Soc. Networks, vol.11, no.1, pp.1–37, 1989.
[15] F.R.K. Chung, “Lectures on spectral graph theory,” CBMS Lecture
Notes, AMS Publications, Providence, 1995.
[16] D. Spielman, “Spectral graph theory,” in Combinatorial Scientific
Computing, U. Naumann and O. Schenk, eds., Chapter 18, pp.495–
524, Chapman and Hall/CRC, 2012.
[17] M.E.J. Newman, “The graph Laplacian,” in Networks: An Introduction, Section 6.13, pp.152–157, Oxford University Press, 2010.
[18] D.K. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets ongraphs via spectral graph theory,” Appl. Comput. Harmon. Anal.,
vol.30, no.2, pp.129–150, 2011.
[19] D.I. Shuman, S.K. Narang, P. Frossard, A. Ortega, andP. Vandergheynst, “The emerging field of signal processing ongraphs: Extending high-dimensional data analysis to networks andother irregular domains,” IEEE Signal Process. Mag., vol.30, no.3,
pp.83–98, 2013.
[20] M. Aida, C. Takano, and M. Murata, “Oscillation model for network
dynamics caused by asymmetric node interaction based on the symmetric scaled Laplacian matrix,” The 12th International Conference
on Foundations of Computer Science (FCS 2016), pp.38–44, July
2016.
[21] M. Aida, “Oscillation model for describing propagation of activities on network caused by asymmetric node interactions,” Keynote
Speech, IEICE Information and Communication Technology Forum2016 (ICTF 2016), July 2016.
[22] C. Takano and M. Aida, “Proposal of new index for describing
node centralities based on oscillation dynamics on networks,” IEEE
GLOBECOM 2016, Washington DC, USA, Dec. 2016.
[23] A. Bavelas, “A mathematical model for group structures,” Hum. Org.,vol.7, no.3, pp.16–30, 1948.
[24] A. Bavelas, “Communication patterns in task oriented groups,” J.
Acoust. Soc. Am., vol.22, no.6, pp.725–730, 1950.
[25] A. Bavelas and D. Barrett, “An experimental approach to organizational communication,” J. Acoust. Soc. Am., vol.22, no.6, pp.725–
730, 1950.
[26] A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani,“The architecture of complex weighted networks,” Proc. National
Academy of Sciences, vol.101, no.11, pp.3747–3752, 2004.
[27] M.E.J. Newman, “Scientific collaboration networks. II. Shortest
paths, weighted networks, and centrality,” Phys. Rev. E, vol.64,
016132, 2001.
[28] M.E.J. Newman and M. Girvan, “Finding and evaluating community
structure in networks,” Phys. Rev. E, vol.69, 026113, 2004.
[29] T. Opsahl, F. Agneessens, and J. Skvoretz, “Node centrality inweighted networks: Generalizing degree and shortest paths Social
Networks,” Soc. Networks, vol.32, no.3, pp.245–251, 2010.
[30] G. Sabidussi, “The centrality index of a graph,” Psychometrika,
vol.31, no.4, pp.581–603, 1966.
[31] M. Marchiori and V. Latora, “Harmony in the small-world,” Physica A: Statistical Mechanics and its Applications, vol.285, no.3-4,
pp.539–546, 2000.
[32] Y. Rochat, “Closeness centrality extended to unconnected graphs:
The harmonic centrality index,” Applications of Social Network
Analysis (ASNA) 2009, pp.26–28, 2009.
[33] P. Boldi and S. Vigna, “Axioms for centrality,” Internet Mathematics,
vol.10, no.3-4, pp.222–262, 2014.
[34] A. Shimbel, “Structural parameters of communication networks,”
Bulletin of Mathematical Biophysics, vol.15, no.4, pp.501–507,
1953.

1832
[35] D.R. White and S.P. Borgatti, “Betweenness centrality measures for
directed graphs,” Soc. Networks, vol.16, no.4, pp.335–346, 1994.
[36] U. Brandes, “A faster algorithm for betweenness centrality,” Journalof Mathematical Sociology, vol.25, no.2, pp.163–177, 2001.
[37] W.W. Leontief, The Structure of American Economy, 1919–1929:
An Empirical Application of Equilibrium Analysis, Harvard University Press, 1941.
[38] P. Bonacich, “Power and centrality: A family of measures,” Am. J.
Sociol., vol.92, no.5, pp.1170–1182, 1987.
[39] S. Brin and L. Page, “The anatomy of a largescale hypertextual
web search engine,” Comput. Networks ISDN Syst., vol.30, no.1-7,
pp.107–117, 1998.
[40] S.P. Borgatti, “Identifying sets of key players in a network,” Comput.
Math. Organiz. Theory, vol.12, no.1, pp.21–34, 2006.
[41] B.K. Sriganga, R. Krishna, and C.M. Prashanth, “A model for
predicting influential users in social network,” International Journal of Computer Science & Information Technologies, vol.5, no.3,
pp.4047–4053, 2014.
[42] M. Salathéa, M. Kazandjieva, J.W. Lee, P. Levis, M.W. Feldman, andJ.H. Jones, “A high-resolution human contact network for infectious
disease transmission,” Proc. National Academy of Sciences, vol.107,
no.51, pp.22020–22025, 2010.
[43] D. Bell, “Centrality measures for disease transmission networks,”
Soc. Networks, vol.21, no.1, pp.1–21, 1999.
[44] M. Wu, C. Kim, and J.J. Jung, “Leader election based on centrality and connectivity measurements in ad hoc networks,” Agent andMulti-Agent Systems: Technologies and Applications, vol.6070 of
the series Lecture Notes in Computer Science, pp.401–410, 2010.
[45] A. Jain and B.V.R. Reddy, “Node centrality in wireless sensor networks: Importance, applications and advances,” 3rd IEEE Advance
Computing Conference (IACC), pp.127–131, 2013.
[46] A. Jain, “Betweenness centrality based connectivity aware routing
algorithm for prolonging network lifetime in wireless sensor networks,” Wirel. Netw., vol.22, no.5, pp.1605–1624, 2015.
[47] N. Meghanathan, “Correlations between centrality measures for mobile ad hoc networks,” International Journal of Wireless Networks
and Broadband Technologies, vol.4, no.2, pp.15–27, 2015.
[48] M. Aida, C. Takano, and M. Murata, “Dynamical model of flaming
phenomena in on-line social networks,” IEEE/ACM International
Conference on Social Networks Analysis and Mining (ASONAM
2017), pp.1164–1171, Sydney, 2017.
[49] M. Aida, C. Takano, and M. Murata, “Oscillation model for describing network dynamics caused by asymmetric node interaction,”
IEICE Trans. Commun., vol.E101-B, no.1, pp.123–136, Jan. 2018.

Chisa Takano
received a B.E. degree
in Telecommunication Engineering from Osaka
University, Japan, in 2000, and a Ph.D. in System Design Engineering from Tokyo Metropolitan University, Japan, in 2008. In 2000, shejoined the Traffic Research Center, NTT Advanced Technology Corporation. Since April
2008, she has been an Associate Professor at theGraduate School of Information Sciences, Hiroshima City University. Her research interests arecomputer networks and distributed systems. She
received the IEICE Young Researchers’ Award in 2003. She received theInformation Network Research Award from the IEICE in 2004, 2012, and2015. She is a member of IEEE (U.S.A.) and IPSJ (Japan).

IEICE TRANS. COMMUN., VOL.E101–B, NO.8 AUGUST 2018

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 the Faculty of SystemsDesign, 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.
He is a member of the IEEE and the Operations Research Society of Japan.