Information Technology Reference
In-Depth Information
Step2 .Set the parameters, and initiate each particle with a random value selected
based on the local-neighbor-list.
Step3 . For each particle, calculates its current fitness, copies its current position
(fitness) to its local best position (fitness).
Step4 . Perform the update strategy to each particle, if the fitness is better than its
local best; update its local best,
Step5 . Select the global best from the local best of each particle. If the fitness is
better than the current global value, update current global value gbest .
Step6. If the stop condition is met, the community structure relevant to the global
best particle is selected as the best partition of the network, otherwise go to step 4.
5
Experimental Results
In this section, extensive experiments are carried out to validate the proposed algorithm
SCPSO(Similarity Based Clustering and Particle Swarm Optimization). The
experimental results of SCPSO are compared with several classical methods (GN [5]
and MOGA-Net [14]) on both synthetic and real world networks. In the clustering
process, the minimum similarity threshold
-
neighborhoods of core node is set to 2.In the optimization process, the mutation rate is
set to 0.1.
ε
is set to 0.5 and the minimum
ε
Evaluation metric
In order to compare the performance of different solutions, two evaluation metrics
are introduced.
One metric adopted in the experiments is Normalized Mutual Information (NMI)
[19]. NMI is always used to calculate the similarity between two partitions. NMI is
defined as follows. A higher NMI value represents a greater similarity between
partition A and partition B . When partition A and partition B are exactly the same,
NMI will reach the max value of 1.
(
)
C
C

A
B
2
C
log
CN C
/
C
(
)
ij
ij
i j
(9)
=
i
=
1
j
=
1
NMI A B
,
(
)
(
)
C
C
A
+
B
C
lo
g
C
/
N
C
lg
o
C
/
N
i
i
j
j
=
=
i
1
j
1
The other metric adopted in the experiments is modularity Q. Modularity Q is
always used in estimating the quality of community structure discovered by different
solutions if the community structure of a network is unknown. The community
partition with a larger modularity usually indicates a better solution. Modularity and
NMI are two commonly used metrics for evaluating the quality of community structure.
Experimental results and analysis on synthetic network
The synthetic network is a benchmark proposed by Girvan and Newman [5]. The
network consists of 128 nodes and is divided into four equally-sized communities,
each with 32 nodes. Each node has ou Z links to nodes of other communities, i Z
links to nodes in the same community, and has an average degree of 16, namely
Search WWH ::




Custom Search