Image Processing Reference
In-Depth Information
where
L
=
A
−
D
is the Laplacian matrix of
G
.
The solution of (15) in the form of normal
ω
i
(
)
modes
t
may be written as
N
j
=
1
V
ij
θ
j
(
t
)=
k
c
ω
i
(
t
0
)
e
−λ
i
t
ω
i
(
t
)=
k
c
,
(16)
where
λ
N
are eigenvalues and
V
is the matrix of eigenvectors of
L
. Note that (16)
describes a convergence speed to a consensus for each nodes. Let's order these equations
according to the descending order of their eigenvalues. Then it is easy to see that nodes are
approaching the consensus in a hierarchical way, revealing in the same time a hierarchy of
communities in the given network
G
.
Note that (15) has the same form as (3), with the difference that the random walk process (3)
is based on
L
rw
λ
1
,...,
D
−
1
L
. It allows us to consider random-walk-based communities detection
in the previous section as a special case of coupled oscillators synchronization.
Similarly to (15), we may derive the Laplacian presentation for locally coupled oscillators (13).
In particular, the connectivity of a graph may be described by the graph incidence
=
(
×
)
N
E
matrix
B
:
{
B
}
ij
=
1(or
−
1) if nodes
j
and
i
are connected, otherwise
{
B
}
ij
=
0. In case of
weighted graphs we use the weighted Laplacian defined as
BD
A
B
T
.
L
A
(17)
Based on (17) we can rewrite (13) as
k
c
BD
A
sin
B
T
,
˙
Θ
(
t
)=
Ω
−
Θ
(
t
)
(18)
where vectors and matrices are defined as follows:
Θ
(
T
;
T
;
D
A
)
[
θ
1
(
)
···
θ
N
(
)]
Ω
(
)
[
ω
1
(
)
···
ω
N
(
)]
{
}
t
t
,
,
t
t
t
,
,
t
diag
a
1
,...,
a
E
,
a
1
, ...,
a
E
are weights
A
ij
indexed from 1 to
E
.
In the following we use (18) to describe different coupling scenarios.
3.2 Dynamical structures with different coupling scenarios
Let's consider local correlations between instant phases of oscillators,
cos
r
ij
(
)=
θ
j
(
)
− θ
i
(
)
t
t
t
,
(19)
where the average is taken over initial random phases
.
Following (Arenas et al, 2006; 2008) we may define a dynamical connectivity matrix
C
t
θ
i
(
t
=
0
)
,
where two nodes
i
and
j
are connected at time
t
if their local phase correlation is above a given
threshold
(
η
)
η
,
C
t
(
η
)
=
1if
r
ij
(
t
)
>
η
ij
(
η
)
ij
=
0 f
r
ij
(
)
< η
C
t
t
.
(20)
We select communities resolution level (time
t
) using a random walk as in Section 2. Next,
by changing the threshold
which reveal
dynamical topological structures for different correlation levels. Since the local correlations
r
ij
(
η
, we obtain a set of connectivity matrices
C
t
(
η
)
)
t
are continuous and monotonic functions in time, we may also fix
η
and express