Image Processing Reference
In-Depth Information
P
ij
d
i
d
j
/2
m
.
By construction
=
|
| <
=
0 means that the network under study is equivalent to
the used null model (an equivalent random graph).
Q
1and
Q
0 indicates a presence of a
community structure, i.e., more links remain within communities than would be expected
in an equivalent random graph. Hence, a network partition which maximizes modularity
may be used to locate communities. This maximization is NP-hard and many suboptimal
algorithms are suggested, e.g., see (Fortunato, 2011) and references within.
In the following we use the basic greedy search algorithm (Newman, 2004) extended with a
random walk approach, since it gives a reasonable trade-off between accuracy of community
detection and scalability.
Greedy Search Algorithm
Case
Q
>
×
Input: a weighted graph described by
N
N
adjacency matrix
A
.
d
i
2
m
2
Initialize
each node
i
as a community
c
i
with modularity
Q
(
i
)=
−
.
Repeat
until there is an increase in modularity:
for all nodes
i
do
:
-remove
i
from its community
c
i
;
-insert
i
sequentially in neighboring communities
c
j
for all
j
with
A
ij
>
0;
c
(
i
→
c
j
)
j
(
)
- calculate modularity
Q
;
- select a move (if any) of
i
-th node to community
c
j
with max modularity
c
(
i
→
c
j
)
j
c
(
i
→
c
j
)
j
(
)=
(
)
Q
max
Q
;
j
∈
N
(
i
)
Stop
when (a local) maximum is reached.
2.2 Communities detection with random walk
It is well-known that a network topology affects a system dynamics, it allows us to
use the system dynamics to identify the underlying topology (Arenas et al, 2006; 2008;
Lambiotte et al, 2009). First, we review the Laplacian dynamics formalism recently developed
in (Evans & Lambiotte, 2009; Lambiotte et al, 2009).
Let's consider
N
independent identical Poisson processes defined on every node of a graph
G
N
, where random walkers are jumping at a constant rate from each of the
nodes. We define
p
n
as the density of random walkers on node
i
at step
n
, then its dynamics
is given by
(
V
,
E
)
,
|
V
|
=
A
ij
d
j
p
i
,
n
+
1
=
∑
j
p
j
,
n
.
(2)
The corresponding continuous-time process, described by (3),
A
ij
d
j
−
δ
ij
p
i
A
ij
d
j
dp
i
dt
=
∑
j
p
i
=
∑
j
p
j
−
(3)