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
Search WWH ::




Custom Search