Information Technology Reference
In-Depth Information
algorithm [7] etc. The secondary category choose optimization methods or approxi-
mation methods, such as spectral method [8], Kernighan-Lin algorithm [9] and Gui-
mera-Amaral algorithm (GA) [10] etc. In recent years, with the widely application of
computational intelligence, some global optimization algorithms have been used in
detecting community structure with good results. In [11], particle swarm optimization
(PSO) is used to optimize modularity[12] for community detection. However, global
optimization process always has high computation complexity, and resolution limit
problem[13]. There are also some multi-objective optimization algorithms for com-
munity detection [14] [15], these algorithms are flexible, but it is hard to design an
effective strategy that can automatically selects a proper solution from Pareto front.
In this paper, community detection is considered as an optimization problem. An al-
gorithm named SCPSO (Similarity Based Clustering and Particle Swarm Optimiza-
tion) is proposed. The rest of this paper is organized as follows. Section 2 designs a
similarity clustering algorithm and then the construction of new weighted network will
be introduced in section 3. Section 4 depicts an improved PSO algorithm for communi-
ty detection. In section 5, experimental results in synthetic network and four real-world
networks are presented and analyzed. Finally, Section 6 draws the conclusion.
2
Clustering Based on Similarity
Many algorithms can discover core clusters (dense-linked areas) of the network. For
example, DBSCAN is able to discover arbitrary clusters in any database and detect
noise at the same time in one scan [16]. SCAN [17] is also a structural clustering al-
gorithm for networks based on DBSCAN. SCAN is effective and fast, but it depends
on a sensitive parameter: minimum similarity threshold
ε
. In the proposed algo-
rithm, we aimed at finding the core areas effectively, so a similarity based clustering
method is introduced.
2.1
Basic Concepts
Here, for simplicity and without loss of generality, we only consider simple, un-
directed, and un-weighted networks. Let
represents the network where
V is the set of nodes and E is the set of edges. Some terms required for explaining
the clustering algorithm is defined as follows [16][17].
=
NVE
(,)
DEFINITION1 (NODE STRUCTURE)
The common neighborhoods of two connected nodes are important for measuring
similarity. So in this paper, we define the structure of node
ν
as the node set
including node
and its neighborhoods , denoted by
Γ
( ν
)
as follows.
ν
(
)
{
V
|
{
,
}
E
}
{
}
Γ
ν
=
μ
ν
μ
ν
(1)
DEFINITION2 (NODE SIMILARITY)
Nodes in the same community share similar structure, the value of structural similarity
metric will be large. The larger similarity value a pair of nodes have, the more likely
Search WWH ::




Custom Search