Image Processing Reference
In-Depth Information
is driven by the random walk operator A ij
d j δ ij , which in case of a discrete time process
is presented by the random walk matrix L rw =
D 1 A ,where L
D 1 L
=
I
=
D
A is a
=
{
}
=
Laplacian matrix, A is a non-negative weighted adjacency matrix, D
diag
d i
,i
1,...,N.
For an undirected connected network the stationary solution of (2) is given by p i =
d i /2 m .
Let's now assume that for an undirected network there exist a partition
P
with communities
c k ∈P
, k
=
1,..., N c .
The probability that initially, at t 0 , a random walker belongs to a
(
) = ∑
j
community c k is Pr
c k , t 0
d j /2 m . Probability that a random walker, which was initially
c k
in c k , will stay in the same community at the next step t 0 +
1isgivenby
A ij
d j
d j
2 m
.
) = j c k i c k
Pr
(
c k , t 0 , t 0 +
1
(4)
The assumption that dynamics is ergodic means that the memory of the initial conditions are
lost at infinity, hence Pr
(
c k , t 0 ,
)
is equal to the probability that two independent walkers are
in c k ,
j c k
.
d j
2 m
d i
2 m
i c k
(
∞)=
Pr
c k , t 0 ,
(5)
Combining (4) and (5) we may write
A ij
d i d j
2 m
1
2 m
c k
i , j
P (
Pr
(
c k , t 0 , t 0 +
1
)
Pr
(
c k , t 0 ,
)) =
δ (
c i , c j )=
Q .
(6)
P
In general case, using (3), one may define a stability of the partition
as (Evans & Lambiotte,
2009; Lambiotte et al, 2009)
)=
c k ∈P
P (
c k , t 0 , t 0 +
)
(
∞)
R
t
Pr
(
t
Pr
c k , t 0 ,
(7)
e t (
4 m 2 ,where A ij
) ij
d j
2 m
d i d j
A ij
d j
A
I
=
c k ∈P
=
.
(8)
i , j
c k
Then, as the special cases of (8) at t
=
1, we get the expression for modularity (6).
P (
)
is non-increasing function of time: at t
=
Note that R
t
0weget
d i d j
4 m 2
c k ∈P
P (
)=
R
0
1
(9)
i , j
c k
and max
P
R
(
0
)
is reached when each node is assigned to its own community.
Note that (9)
corresponds to collision entropy or Rényi entropy of order 2.
On the other hand, in the limit
is achieved with Fiedler
spectral decomposition into 2 communities. In other words, time here may be seen as a
resolution parameter: with time t increasing, the max
P
t
, the maximum of R
P (
t
)
(
)
R
t
results in a sequence of hierarchical
Search WWH ::




Custom Search