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




Custom Search