Information Technology Reference
In-Depth Information
Calculating modularity [12] in the new weighted network plays a significant role in
community detection. Modularity has high computation complexity and is highly
dependent on the scale of network. The optimization efficiency will be improved if we
can prove that searching modularity optimum in the new constructed network and the
original one is equivalent.
The equivalence here means optimization modularity in the new constructed
network equals optimization in the original one with fixed combination of core areas.
In another word, core area will not split when applying random optimization method.
The proof of the equivalence of optimization modularity is presented briefly in the
following paragraph.
Let
G
denotes the original network and A=
(
i
A
)
denotes the adjacency
n
×
n
matrix of
G
where
i
A
is the weight of the edge from node
i
to
j
.
1
k
=
A
is the degree of node
i
, and
m
=
i
A
is the total of the
ij
i
ij
ij
2
edge weight of
G
,
c
is the identifier of the community that node
i
belongs to
in certain iteration. If node
i
and node
j
are in the same community,
δ
(
c
i
c
,
)
=
1
, otherwise 0.
Q
denotes the modularity of
G
.
j
k
k
1
i
j
s (6)
Q
=
(
A
−
)
δ
(
c
,
c
),
1
≤
i
,
j
≤
n
ij
i
j
2
m
2
m
ij
Since all the edges in G are kept in the new constructed network. According to the
definition of modularity, it is easy to find out that the modularity of the new
constructed network equals
Q
. Therefore, searching modularity optimum in the new
constructed network is equivalent to searching in the original one.
4
Modularity Optimization
Particle Swarm Optimization (PSO) is a computational intelligence algorithm proposed
by Kennedy and Eberhart in 1995 [18]. It is a swarm intelligence algorithm that
simulates the movements of a flock of birds which seek food. Its relative simplicity and
fast convergence have made it a popular optimization method in many research fields
including community detection [11].
Fitness Function
Each particle represents a potential community structure of the network. Modularity
which is a popular evaluation index for community detection is chosen as the fitness
function. It is based on the intuitive idea that random networks do not have community
structure, a good division into communities should have a high value of modularity[12].
PSO will select the particle with the maximum modularity as the best solution.
