Information Technology Reference
In-Depth Information
Detecting Community Structures in Social Networks
with Particle Swarm Optimization
Yuzhong Chen
1,*
and Xiaohui Qiu
1
1
Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information
Processing, Fuzhou University, China
yzchen@fzu.edu.cn
Abstract.
Community detection in social networks is usually considered as an
objective optimization problem. Due to the limitation of the objective function,
the global optimum cannot describe the real partition well, and it is time con-
suming. In this paper, a novel PSO (particle swarm optimization) algorithm
based on modularity optimization for community detection in social networks is
proposed. Firstly, the algorithm takes similarity-based clustering to find core
areas in the network, and then a modified particle swarm optimization is per-
formed to optimize modularity in a new constructed weighted network which is
compressed from the original one, and it is equivalent to optimize modularity in
the original network with some restriction. Experiments are conducted in the
synthetic and four real-world networks. The experimental results show that the
proposed algorithm can effectively extract the intrinsic community structures of
social networks.
Keywords:
Community Detection, Particle Swarm Optimization, Modularity.
1
Introduction
In recent years, community detection in social networks has attracted a lot of attention
[1] [2]. Informally, communities are groups of nodes that are connected densely inside
the group but connected sparely with the rest of the network. Community structure is
the key feature for uncovering the global property in social networks, which is very
important for studying social networks. The community can represent special role,
group or a substructure of certain function. For example, communities in World Wide
Web are considered as thematic clusters [3], communities in biological networks are
widely believed to have a close connection to biological function [4], etc.
As an important attribute of the social networks, community detection has attracted
lots of people's attention from different fields, like sociology, biology, computer
science, etc. Many classic methods have been proposed to detect community struc-
tures in social networks. They can be roughly classified into two categories. The first
category employ heuristic strategies, such as Girvan-Newman (GN) algorithm [5],
Wu-Huberman (WH) algorithm [6] and Hyperlink Induced Topic Search (HITS)
