2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Dynamical Model of Flaming Phenomena
in On-Line Social Networks
Masaki Aida

Chisa Takano

Masayuki Murata

Graduate School of Systems Design Graduate School of Information Sciences Graduate School of Information Sciences
Tokyo Metropolitan University
Hiroshima City University
Osaka University
Hino-shi 191–0065, Japan
Hiroshima-shi 731–3194, Japan
Suita-shi 565–0871, Japan
Email: aida@tmu.ac.jp
Email: takano@hiroshima-cu.ac.jp Email: murata@ist.osaka-u.ac.jp

Abstract—This paper proposes an oscillation model for describing the flaming phenomena in on-line social networks, anddiscusses countermeasures to flaming based on the proposed
oscillation model. The most significant feature of the proposedmodel is that the cause of flaming can be explained by the
structure of the network. Based on the proposed model, we cansuppress the generation of flaming by controlling link weights
of a part of the network. This passive solution to flaming isimportant for the stable operation of social media networks.

I. I NTRODUCTION
Since information exchange on social networks is being
activated by the recent rapid adoption of information networks,
the complex dynamics thought to underlie the propagation ofactivities in on-line social networks have become interesting
research subjects [1], [2], [3]. In particular, the explosive
phenomenon called flaming seriously impacts not only on thestability of information networks but also social activities in
the real world.
The spectral graph theory is a powerful approach to the analysis of network dynamics, and is applicable to many problems
such as clustering of networks, graph drawing, graph cut, nodecoloring, and image segmentation [4], [5], [6]. Spectral graphtheory is also important for describing diffusion on networks
and the Markov process, and the consensus problem [7], [8].
Oscillation dynamics are quite different from the above topics.
Recently, we introduced an oscillation model on networks
and investigated its properties [9], [10], [11], [12], [13]. The
significance of our oscillation model is that the oscillationenergy of each node gives a generalized node centrality that
describes the strength of the node’s activity. Generalized
node centrality can reproduce the conventional node centrality(degree centrality and betweenness centrality [14], [15], [16])in simple cases. As an application of the oscillation model, thePermission to make digital or hard copies of part or all of this work forpersonal or classroom use is granted without fee provided that copies are notmade or distributed for profit or commercial advantage and that copies bear
this notice and the full citation on the first page. Copyrights for third-party
components of this work must be honored. For all other uses, contact the
Owner/Author.
ASONAM ’17, July 31-August 03, 2017, Sydney, Australia
c 2017 Copyright is held by the owner/author(s).
⃝ACM ISBN 978-1-4503-4993-2/17/07.
https://doi.org/10.1145/3110025.3120982

network resonance method that can determine the link weightof social networks (the strength of interaction between users)
has been investigated [17], [18].
In this paper, we define the flaming phenomenon as divergence of generalized node centrality. We are able to model
flaming by generalizing the oscillation model for a general
directed graph. In this model, the strength of node activity
increases exponentially with time under a certain condition.
The most significant feature of the proposed model is that thecause of flaming can be explained by network structure. Basedon this feature, we also discuss countermeasures to flaming.
The rest of this paper is organized as follows: In Sec. II, we
discuss ways of decomposing directed graphs to symmetrizable
directed graphs and one-way link graphs, and introduce thescaled Laplacian matrix [9], [10]. In addition, we introduce
an oscillation model on a symmetrizable directed graph, andthe concept of generalized node centrality as the oscillationenergy of each node. In Sec III, we propose a generalization of
the oscillation model for general directed graphs, and discuss
the solution of the equation of motion. In Sec IV, after
defining flaming, we propose a model that describes flaming.
In addition, we discuss a countermeasure.
II. P RELIMINARY
A. Decomposition of Directed Networks and Symmetrizable
Directed Networks
Network structure is frequently expressed as a matrix. Let
us consider loop-free directed graph G(V, E) with n nodes,
where V = {1, 2, . . . , n} is the set of nodes and E is theset of directed links. In addition, let the link weight for link(i → j) ∈ E be wij > 0. We define the following n × nsquare matrix A = [Aij ] as{wij ((i → j) ∈ E),
Aij :=(1)0 ((i → j) ̸∈ E).
This matrix represents link presence and weight, and is called
the (weighted) adjacency matrix. Next, we define the weighted
out-degree, di , of node i (i = 1, 2, . . . , n) as
∑
di :=
wij ,
(2)
j∈∂i

1164

2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
symmetrizable graphwhere ∂i denotes the set of nodes adjacent to node i. Also,
weighted out-degree matrix D is defined as1

D := diag(d1 , . . . , dn ).

L = L0 + LI .

4

= 1

1

2
1

2

2
1

4

+ 1

3

= 1

(3)

where this is, in general, an asymmetric matrix. Figure 1
shows an example of the Laplacian matrix for directed graphs.
Note that since the row sum of the Laplacian matrix is 0,
the Laplacian matrix has 0 as an eigenvalue. In addition, it
is known that the multiplicity of eigenvalue 0 is equal to
the number of connected components of the corresponding
graph [4]. So, for a connected graph, the multiplicity is 1.
Hereafter, we consider a connected graph without loss ofgenerality.
We now consider how to decompose the Laplacian matrix ofa directed graph into two parts: one is the Laplacian matrix fora symmetrizable graph, L0 , (the definition is stated below) andthe other is the Laplacian matrix for a one-way link graph, LI ,this has at most only one-way directed links between nodes,that is,2

3

The Laplacian matrix L of directed graph G(V, E) is defined
as follows [4], [5] (Fig. 1).
L := D − A,

2 2
2
3
4
1 3
2
1
1
3

one-way link graph

2 1
2
3
3
1 3
1
1
1
2

2
2

1

4

2

3

1

2
4

+ 1

3

1

1
1

3

4
1

Fig. 2: Examples of decomposition L = L0 + LI (1)symmetrization 3
2 3
2 1
2
6
3
3
3
3
1
1
1 1
4
2
1
2
1
1
2
3
3
1
asymmetrization
 



4 −6/2 −2/2
0
8 −6 −2 0
1/2 0 0 0
−6/3 4 −3/3 −3/3  0 1/3 0 0  −6 12 −3 −3 
=


=
−2/1 −3/1
6 −1/1  0 0 1 0  −2 −3 6 −1 
0 −3/1 −1/1
4
0 0 0 1
0 −3 −1 4



4 −3
−2 4

L0= −2 −3
0 −3

−1
−1
6
−1


0
−1

−1
4

4

1

Fig. 3: Symmetrization of a symmetrizable Laplacian matrix
L0(4)Here, the definition of the symmetrizable graph is as follows.
We consider the left eigenvector tm = (m1 , . . . , mn ) of
Laplacian matrix L associated with eigenvalue 0, that is,(6), the corresponding Laplacian matrix L is symmetric. By
using L, the symmetrizable Laplacian matrix L0 is expressedasm L = t 0,

L0 = M −1 L,

t

(5)

t

where 0 := (0, . . . , 0). Note that the multiplicity of eigenvalue 0 is 1 for a connected graph. The directed graphdescribed by L is symmetrizable iff each component mi > 0of the left eigenvector tm satisfies
mi wij = mj wji .

(6)

The physical meaning of this condition is discussed in
Sect. II-C. We denote the Laplacian matrix for a symmetrizable graph as L0 .
Let G(V, E) be an undirected graph whose link weight
between node i–j is kij := mi wij . Since kij = kji from

1

2 2
2
3
4
1 3
2
1
1
3
3


5
0
D= 
0
0

0 0
5 0
0 7
0 0

4



0
2

A=
3
0

4
0
3
3

1
1
0
2


0
2

1
0




5 −4 −1 00−2 5 −1 −2
0

 L=
−3 −3 7 −1
0
0 −3 −2 55

Fig. 1: Example of Laplacian matrix L(7)where M := diag(m1 , . . . , mn ) means the scaling factors of
nodes. An example of the symmetrizable Laplacian matrix isshown later with a discussion of its decomposition.
Figure 2 shows examples of decomposition (4) of thedirected graph depicted in Fig. 1. The first decomposition ofFig. 2 yields an undirected graph and a one-way link graph.
This decomposition is uniquely determined by choosing thecomponents of L0 = [ℓ0ij ] and LI = [ℓIij ] as
ℓ0ij = − min(wij , wji ),(8)ℓIij = −wij + min(wij , wji ),(9)for i ̸= j. The second decomposition of Fig. 2 yields a
symmetrizable directed graph and an one-way link graph. The
Laplacian matrix of the symmetrizable graph in the second
decomposition is expressed in the form of (7) as shown in
Fig. 3. The undirected graph is a special case of symmetrizablegraphs and M = I (unit matrix) for undirected graphs.
From the above discussion, we can recognize the following
facts:• Any directed graph can be decomposed into a symmetrizable directed graph and a one-way link graph.
• The decomposition is not unique, as it depends on the
choice of symmetrizable directed graph included in theoriginal directed graph.

1165

2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

1

2 2
2
3
4
1 3
2
1
1
3

4

symmetrizable graphone-way link graph

2 2
2
3
1/2
1 3/4
2
1
3
1

2

= 1

4

+ 1

7/2

3

3

4

9/4

3

2 1/2
3
2
1 3
4
2
1
3
1

equilibrium

2

2

= 1

xi

+ 1

3/2

2

3

xj

4

3

i

j

Fig. 4: Examples of decomposition L = L0 + LI (2)Fig. 5: Oscillation model on networks.

If the original directed graph is symmetrizable, we can choosea decomposition such that LI = O (the null matrix).
Figure 4 shows other examples of decomposition (4) of thedirected graph depicted in Fig. 1. As discussed later, the degreeof freedom of the decomposition (the degree of freedom of
choice in symmetrizable directed graph) plays a significant
role in controlling network dynamics.

This means scaled Laplacian matrix S has the same eigenvalues as L, and its eigenvector is y := M +1/2 x. Thus,
the characteristics of a directed graph expressed by L can beinvestigated through S.
Next, we consider S 0 of decomposition (12). Since S 0
is a semi-positive definite matrix, let us consider sorting the
eigenvalues of S 0 (also L0 ) in ascending order,

B. Scaled Laplacian Matrix and Its Decomposition

0 = λ0 < λ1 ≤ λ2 ≤ · · · ≤ λn−1 .

First, we define the scaled Laplacian matrix for a symmetrizable network as
S 0 := M +1/2 L0 M −1/2 = M −1/2 L M −1/2 ,(10)

where M := diag(m1 , . . . , mn ) is the scaling factors forsymmetrizable graph L0 . From the second equality of (10),S 0 is a symmetric matrix.
Next, we introduce the scaled Laplacian matrix, S, forgeneral directed graphs. The most significant characteristicof S is that the definition of S depends on the choice ofsymmetrizable directed graph made in the decomposition of(4). Starting with L0 and its scaling factor M , we define thescaled Laplacian matrix S for a general directed graph as
S := M

+1/2

LM

−1/2

.

(11)

S is decomposed as
S = S0 + SI,
where

(12)

S I := M +1/2 LI M −1/2 .

It is noteworthy that the definition of S depends on the choiceof L0 , and decomposition (12) also depends on the choice ofL0 .
Here, we summarize two important characteristics withrespect to the scaled Laplacian matrix.
Let us consider the eigenvalue equation of L as

In addition, since S 0 is a real symmetric matrix, we can choose
eigenvector v µ (µ = 0, 1, . . . , n − 1) as the orthonormal
eigenvector associated with λµ . That is,
S 0 v µ = λµ v µ ,M +1/2 L x = S M +1/2 x = λ̄ M +1/2 x.

v µ · v ν = δµν ,(14)

where δµν denotes the Kronecker delta. Selecting L0 (or,equivalently, defining S) corresponds to selecting a basis of then-dimensional state space. Thus, we can choose an appropriate
basis of the n-dimensional state space based on the degree of
freedom of the decomposition of (4).
C. Oscillation Model on a Symmetrizable Directed Graph
Let weight xi of node i be displacement from equilibrium,and let its restoring force be proportional to the differencein the displacements of adjacent nodes. Figure 5 is a representative image of our oscillation model. Although the figure
shows a 1-dimensional network, it is easily extended to general
networks. To represent diverse oscillating behaviors, we allow
the spring constant of each link to be different and each node
to have different mass.
Here, it is worthwhile discussing the validity of the oscillation model given that its restoring force is proportional
to the difference in displacements. Let the restoring force ofnode i from node j be a function f (∆x) of the difference∆x := xi − xj of the displacements of adjacent nodes i andj. It is natural to assume f (∆x) = 0 if ∆x = 0. For small∆x, we can expand f (∆x) as

L x = λ̄ x,where λ̄ is an eigenvalue of L and x is the eigenvector
associated with the eigenvalue λ̄. By multiplying M +1/2 fromthe left, we have(13)

f (∆x) = −kij ∆x + O(∆x2 ),(15)

where kij is a positive constant corresponding to the spring
constant. Our oscillation model can be considered as a basic
and universal model if the nonlinear effects in O(∆x2 ) are
relatively small.

1166

2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
We assign a spring constant to each link and express it aslink weight kij > 0. In addition, we assign mass mi > 0 to
node i. The equation of motion of the node displacement vector x(t) := t (x1 (t), . . . , xn (t)) for non-damped oscillation
on networks is obtained as follows (see Appendix):M

d2 x(t)= −L x(t),dt2or, by multiplying M −1 from the left,
d2 x(t)= −L0 x(t),
dt2

(16)

where M is the mass matrix M := diag(m1 , . . . , mn ).
Note that the equation of motion (16) reflects the asymmetriccharacteristics of links described by the asymmetric Laplacianmatrix (7). Also note that L0 is a Laplacian matrix for thesymmetrizable directed graph. Node characteristic mi in (6)corresponds to the mass of node i in the oscillation model. In
addition, condition (6) represents Newton’s third law (the lawof action and reaction). To symmetrize the equation of motion,
we introduce vector y which is defined byy(t) = M +1/2 x(t),In closed dynamic models, any oscillation is damped overtime due to frictional force. Let us consider the equation of
motion for damped oscillationd x(t)
d2 x(t)+γM= −L x(t),
(21)
dt2
dt
where γ is a constant. Here γM means the viscous damping
coefficient, where it is important to note that the viscous damping coefficient is assumed to be proportional to node mass.
By using vector y(t) = M +1/2 x(t), we can symmetrize theequation of motion asM

d y(t)
d2 y(t)+γ= −S 0 y(t).
dt2dt

The equation of motion for Fourier mode aµ (t) is expressedasd2 aµ (t)d aµ (t)+γ+ λµ aµ (t) = 0.
(23)
2
dt
dt
To analyze the solution of this equation, we assume thesolution takes the form of aµ (t) ∝ eαt . By substituting
this into the equation of motion, we obtain the characteristic
equation
α2 + γα + λµ = 0.

where the equation of motion is written as
d2 y(t)= −S 0 y(t).
dt2

(17)

It follows that the equation of motion will yield the eigenvalue
problem of the symmetric scaled Laplacian matrix.
Let y(t) be expanded by the eigenbasis v µ of S 0 asy(t) =

n−1
∑

(24)

The form of solution to the equation of motion is different
depending √on the solution of the characteristic equation, α =−(γ/2) ± (γ/2)2 − λµ . In the case of (γ/2)2 < λµ , thesolution describes damped oscillations,
[
]
√
γ
2
aµ (t) = aµ (0) exp − t ± i λµ − (γ/2) t .
(25)
2
On the other hand, if (γ/2)2 ≥ λµ , the solution is notoscillating because the strength of damping is too great.

aµ (t) v µ .

µ=0Substituting it into the equation of motion (17) yields theequations of motion for the Fourier mode aµ (t) (µ =0, 1, . . . , n − 1) as follows,
d2 aµ (t)= −λµ aµ (t).
dt2

(22)

(18)

The solution of (18) is given byaµ (t) = aµ (0) e±i ωµ t ,(19)√√
where ωµ = λµ , i = −1. The initial condition, aµ (0) =|aµ (0)| eiθµ (−π < θµ ≤ π), gives the amplitude |aµ (0)| andphase θµ of the corresponding Fourier mode, µ.
The solution (19) means that the oscillation dynamics on
symmetrizable directed networks can be expressed by using
decomposition into the equation of motion of the harmonic
oscillator (18) for each Fourier mode. The solution of oscillation on networks (the solution of (16)) is expressed as
(n−1
)
∑
−1/2
±i ωµ tx(t) = Maµ (0) evµ .
(20)

D. Generalized Node Centrality
The importance of the oscillation model lies in the relationship between the oscillation energy of each node and node
centrality.
From (19), oscillation behavior is decomposed into n independent harmonic oscillators. Since the oscillation energy ofa harmonic oscillator with mass m, natural frequency ω, andamplitude A is given by 21 m ω 2 A2 , the oscillation energy Ei
of node i is obtained by summing the oscillation energy foreach Fourier mode,
Ei =

n−1
2
∑
1
vµ (i)miωµ aµ (t) √
2
mi
µ=0

1∑
2
=
| ωµ aµ (t) vµ (i) | ,
2 µ=0
n−1

(26)

where vµ (i) denotes the i-th component of the eigenbasis v µ
associated with the eigenvalue λµ of the scaled Laplacianmatrix S 0 , that is,v µ = t (vµ (1), . . . , vµ (n)).

µ=0

1167

2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
As the initial condition of the wave equation (16), we use
node displacement. We call this node the source node ofactivity. Let us consider the situation that the source nodeof activity is chosen at random. If we set all link weights(node masses are set at 1), the oscillation energy of each node
gives the degree centrality. On the other hand, we consider
the shortest paths between all pairs of nodes. If we set all linkweights as the number of the shortest paths passing through thelink, the oscillation energy of each node gives the betweenness
centrality. Assigning link weights and node masses flexibly
yields a generalized form of node centrality. The oscillationenergy can be defined even for damped oscillation on networks. A detailed discussion is presented in [11], [12].
For damped oscillation, the oscillation energy depends ontime. From (25) and (26), the time-dependent oscillationenergy Ei (t) for node i is given byEi (t) = Ei e−γt ,Here, it is worthwhile noting that if the oscillation occurs on an
unsymmetrizable graph i.e. LI ̸= O, Newton’s third law does
not hold. This means that the generalized oscillation modelcannot be depicted by a dynamical model like Fig. 5. In otherwords, the generalized oscillation model does not correspondto dynamical phenomena in the real world, but to a kind of
virtual phenomena in cyber space.
Similar to (22), the equation of motion of damped oscillation can be written as
d2 y(t)d y(t)−γ= −S y(t) = −(S 0 + S I ) y(t),dt2dt

where γ ≥ 0 (it includes (30) for γ = 0).
Since S is no longer a real symmetric matrix, we should
consider the following issues when solving the equation of
motion (31):(27)

where Ei = Ei (0). For non-damped oscillation γ = 0, Ei (t)is time independent
Ei (t) = Ei .
The total oscillation energy of the network is obtained as
the sum of the oscillation energy of each node,n∑E(t) =Ei (t)i=1

1 ∑∑2| ωµ aµ (t) vµ (i) |2 i=1 µ=0

S is not always diagonalizable.
Eigenvectors of S cannot always be orthogonalized.
• Eigenvalues of S are, in general, complex numbers.
••

Let us consider the impact of these issues on the solution ofequation of motion (31) and the oscillation energy.
Let the eigenvalues of S be λ̄µ (µ = 0, . . . , n − 1) and theeigenvector associated with λ̄µ be v̄ µ . The necessary condition
that S is not diagonalizable is that S has multiple eigenvalues.
In other words, the eigenvalue equation

n n−1

=

det(S − λ̄ I) = 0,1∑2=
| ωµ aµ (t) |
2 µ=0
n−1

=

1
2
|z(t)| ,2

wherez(t) =

n−1
∑

(28)

ωµ aµ (t) v µ .

µ=0III. G ENERALIZED O SCILLATION M ODEL ON G ENERALD IRECTED N ETWORKS
Here, we extend the oscillation model described in
Sect. II-C to a general directed graph.
Let xi (t) be the displacement of node i at time t on directed
graph G(V, E), and the restoring force that node i receives
from adjacent node j be −wij (xi (t)−xj (t))．Note that since
wij ̸= wji , the strength of restoring forces between nodes i–j
are asymmetric, in general.
Then, the equation of motion of the displacement vector
x(t) = t (x1 (t), . . . , xn (t)) can be written as+1/2

and the equation of motion of vector y(t) = M 0
obtained as
d2 y(t)= −S y(t) = −(S 0 + S I ) y(t).
dt2

(29)
x(t) is(30)(32)

has repeated roots, where I is the unit matrix. In engineering,
the value of link weights of actual networks is determined tothe accuracy level of the significant digits expected. Therefore,
the mathematical condition for repeated roots of (32) is easily
avoided by changing the link weights only very slightly. This
allows us to assume that S has n distinct eigenvalues.
The fact that the eigenvectors are not orthogonal meansthat the total oscillation energy is not given by the simple
summation of oscillation energy of each oscillation mode, andthus different oscillation modes are coupled. This complicatesthe expression of the oscillation energy of the network.
The eigenvectors associated with the different eigenvalues
are generally not orthogonal, but it is guaranteed that they arelinearly independent. Therefore, by using the following n × nsquare matrices
Λ̄ := diag(λ̄0 , . . . , λ̄n−1 ), and P̄ := (v̄ 0 , . . . , v̄ n−1 ),S can be diagonalized as follows:Λ̄ = P̄2d x(t)= −L x(t) = −(L0 + LI ) x(t),
dt2

(31)

−1

−1

S P̄ ,(33)

where the existence of P̄
arises from the linear independence of v̄ µ . Incidentally, the eigenvalues of S 0 are nonnegative and all the components of the eigenvectors have realvalues. However, the eigenvalues of S are generally complex
numbers, and the components of the eigenvectors are also
generally complex numbers.

1168

2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
Let us expand the solution y(t) of (31) by the eigenvectorsof S, asn−1∑y(t) =āµ (t) v̄ µ .

be measured by oscillation energy. That is, flaming is definedas the divergence of oscillation energy,
lim E(t) = ∞.

By substituting this into the equation of motion (31), andapplying a procedure similar to that described in II-C, thecharacteristic function for Ansatz āµ (t) ∝ eᾱt is obtained as

Since the time dependent factors of E(t) are present onlyin āµ (t)’s, we need focus only on the behavior of āµ (t)’s.
Therefore, flaming occurs if
lim |āµ (t)| = ∞,ᾱ2 + γ ᾱ + λ̄µ = 0.

for some µ (µ = 0, 1, . . . , n − 1).

r ei θ := λ̄µ − (γ/2)2 = −(ᾱ + γ/2)2 ,where r ≥ 0 and −π < θ ≤ π. Then, the solution of thecharacteristic function is obtained as√γᾱ = − ± i r eiθ/2 .
2This yields the oscillating solution of aµ (t) as
[ γ
(√
) ]
āµ (t) = āµ (0) exp − t ± i
r eiθ/2 t .
(34)
2
IV. F LAMING P HENOMENON IN O N -L INE S OCIALN ETWORKS

B. Modeling of Flaming in Network Dynamics
In order to model flaming, let us consider the behavior of(34). Since
( )
( )
√
√ iθ/2 √θθ= r cos+ i r sin
,
(38)
re
2
2
we have[āµ (t) = āµ (0) exp −(A. Definition of Flaming in Networks
The term flaming is a phenomenon arising in on-line social
network that strongly impacts not only the on-line social
networks themselves but also on off-line social networks.
Although flaming causes various social impacts, a common
feature of these explosive phenomena is it is caused by the
behavior of users.
In our oscillation model, the strength of activity of a network
can be expressed by its oscillation energy. Thus, we introduce
the total oscillation energy E(t) of the network as=

2 µ=0 ν=0

λ̄µ

( ))
θ
t
2
( ) ]
√
θ
± i r cos
t .
2

γ √
± r sin2

This section proposes a dynamical model of the flaming
phenomenon in on-line social networks, and a countermeasure.

12|z̄(t)|
2n−1 n−1 √
1 ∑∑

(37)

t→∞

Since λ̄µ is a complex number, we define

E(t) :=

(36)

t→∞

µ=0

This means that the imaginary part of the eigenvalue λ̄µcontributes to the amplitude of the oscillation mode. Fromthe structure of (39), we can recognize that āµ (t) diverges
exponentially if
( )
√
θ
γ
r sin
> .
2
2
This mechanism can be interpreted as the cause of theflaming phenomenon in on-line√social networks. Examplesof√ the behavior of āµ (t) for r | sin(θ/2) | < γ/2 andr | sin(θ/2) | > γ/2 are shown in Figs. 6 and 7, respectively.

2λ̄ν |āµ (t) āν (t)| (v̄ µ · v̄ ν ),āµ (t)(35)
wherez̄(t) =

(39)

time

n−1
∑√

|λ̄µ | āµ (t) v̄ µ .

Fig.
6: Example of√r | sin(θ/2) | < γ/2.

µ=0

Different from the case of symmetrizable graphs, the oscillation energy cannot be divided into the oscillation energy
for each oscillation mode. This is because the eigenvectorsv̄ µ ’s are in general, not orthogonal, and this causes coupling
between different oscillation modes. Note that if the network
is symmetrizable, S = S 0 , the eigenvalue λ̄µ is real and theeigenvectors are orthogonal. Then, (35) is reduced to (28).
Here, we define flaming in on-line social networks. We
expect that the strength of explosive behavior of users canthebehaviorofāµ (t)whereāµ (t)time

7: Example ofFig.
√r | sin(θ/2) | > γ/2.

1169

the

behaviorofāµ (t)where2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
C. Flaming CountermeasureRIn order to prevent and/or suppress flaming, an effective
control strategy is to make the network symmetrizable. Thisapproach makes LI = O based on the decomposition (4). At
this time, the diversity of decomposition (4) leads to control
flexibility.
Regardless of the value of γ ≥ 0, in order to always preventthe outbreak of flaming, it suffices if all the eigenvalues of
S are real numbers. The condition that the directed graph
G(V, E) is symmetrizable is a sufficient condition that all the
eigenvalues of S are real numbers. Therefore, we can prevent
flaming by making G(V, E) symmetrizable.
Let us consider nodes i1 , i2 , . . . , ik (in a loop), and the
product of kink weights along i1 → i2 → · · · → ik → i1 . If
all pairs of adjacent nodes satisfy the condition (6), the productof link weights is written as
m i2
m i3
mi1
wi1 i2 wi2 i3 · · · wik i1 =wi2 i1
wi3 i2 · · ·
wi i
m i1
m i2
m ik 1 k= wi1 ik · · · wi3 i2 wi2 i1 .
(40)
That is, the product of link weights through the loop in one
direction is equivalent to the product in the opposite direction.
Conversely, if (40) holds, we can choose mi and mj thatsatisfy (6). Therefore, it is possible to symmetrize a directed
graph by adjusting the product of link weights in the clockwise direction so that it equals that in the counterclockwise
direction, for all loops.
Next, we consider two loops C1 and C2 as shown in theupper figure of Fig. 8, and let the products of link weights
in the clockwise and the counterclockwise directions be R1
and L1 for loops C1 , and be R2 and L2 for C2 , respectively.
In addition, let loops C1 and C2 share a part of their paths
as shown in the lower figure of Fig. 8. For the shared path,
let the products of link weights in the upward and downward
directions be U and D, respectively. If loops C1 and C2 satisfy
the condition (6) (i.e. R1 = L1 and R2 = L2 ), the productsof link weights of the combined loop C1+2 satisfy
R1 R2
L1 L2
=
.
(41)
D U
U D
This means the products of link weight in the clockwise andcounterclockwise directions of the combined loop C1+2 areequal. Therefore, it is sufficient to adjust the link weight for
undividable loops.
Note that we can adjust the products of link weights of aloop regardless of which link we select. This fact is related to
the fact that decomposition (4) does not have a unique solution.
V. C ONCLUSION
This paper has introduced a generalization of the oscillation
model on directed networks by adding the effect of one-way
link topology to the conventional oscillation model. The proposed generalized oscillation can describe general asymmetricinteractions between nodes. We have shown that the solution of
the generalized oscillation model depends on the eigenvaluesof the asymmetric scaled Laplacian matrix, and from the fact

L

R

C

C

L

C

U

D

C

Fig. 8: The product of link weights with respect to the
combined closed loops

that the eigenvalues are complex numbers in general, we
have clarified a framework that can explain the exponential
increase of oscillation energy. This framework can explain why
explosive behaviors like flaming can autonomously breakout
in networks. Based on the framework, we also discussed
countermeasures to flaming.
ACKNOWLEDGMENT
This research was supported by Grant-in-Aid for Scientific
Research (B) No. 26280032 and No. 17H01737 from the Japan
Society for the Promotion of Science (JSPS).
R EFERENCES[1] A. Mislove, M. Marcon, K.P. Gummadi, P. Druschel and B. Bhattacharjee, “Measurement and analysis of online social networks,” Proc. of
ACM SIGCOMM conference on Internet measurement, pp. 29–42, 2007.
[2] A. Sandryhaila and J.M.F. Moura, “Discrete signal processing ongraphs,” IEEE Trans. Signal Process., vol. 61, no. 7, pp. 1644–1656,
2013.
[3] A. Sandryhaila and J.M.F. Moura, “Big data analysis with signal
processing on graphs: Representation and processing of massive data
sets IEEE Signal Process. Mag., vol. 31, no. 5, pp. 80–90, 2014.
[4] F. R. K. Chung, “Lectures on spectral graph theory,” CBMS Lecture
Notes, AMS Publications, Providence, 1995.
[5] D. Spielman, “Spectral graph theory,” Chapter 18 of Combinatorial
Scientific Computing (Eds. U. Naumann & O. Schenk), pp. 495–524,
Chapman and Hall/CRC, 2012.
[6] M.E.J. Newman, “The graph Laplacian,” Section 6.13 of Networks: An
Introduction, pp. 152–157, Oxford University Press, 2010.
[7] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobileautonomous agents using nearest neighbor rules,” IEEE Transactions on
Automatic Control, vol. 48, no. 6, pp. 988-1001, 2003,[8] R. Olfati-Saber and R.M. Murray, “Consensus problems in networks ofagents with switching topology and time-delays,” IEEE Transactions on
Automatic Control, vol. 49, no. 9, pp. 1520–1533, 2004.
[9] 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 onFoundations of Computer Science (FCS 2016), July 2016.
[10] M, Aida, “Oscillation model for describing propagation of activities
on network caused by asymmetric node interactions,” Keynote Speech,
IEICE Information and Communication Technology Forum 2016 (ICTF
2016), July 2016.
[11] C. Takano and M. Aida, “Proposal of new index for describing node
centralities based on oscillation dynamics on networks,” IEEE GLOBECOM 2016, December 2016.

1170

2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining[12] C. Takano and M. Aida, “Fundamental framework for describing various
node centralities using an oscillation model on social media networks,”
IEEE ICC 2017, May 2017.
[13] M. Aida, C. Takano, and M. Murata, “Oscillation model for describing
network dynamics caused by asymmetric node interaction,” IEICE
Transactions on Communications, vol. E101-B, no. 1, January 2018.
(in press)[14] L.C. Freeman, “Centrality in social networks: Conceptual clarification,”
Social Networks, vol. 1, no. 3, pp. 215–239, 1979.
[15] L.C. Freeman, S.P. Borgatti and D.R. White, “Centrality in valued
graphs: A measure of betweenness based on network flow,” Social
Networks, vol. 13, pp. 141–154, 1991.
[16] P.J. Carrington, J. Scott and S. Wasserman, Models and methods in social
network analysis, Cambridge University Press, 2005.
[17] S. Furutani, C. Takano and M. Aida, “Proposal of the network resonancemethod for estimating eigenvalues of the scaled Laplacian matrix,”
INCoS 2016 Workshop, pp. 451–456, September 2016.
[18] S. Furutani, C. Takano and M. Aida, “Method for estimating the eigenvectors of a scaled Laplacian matrix using the resonance of oscillation
dynamics on networks,” IEEE/ACM ASONAM 2017, July 2017.

1171