Abstract—Overlapping community detection algorithm resea-
rch is one of hot topics in current social network analysis. In this
paper, we applied the idea of weighted label propagation to
overlapping community detection algorithm design, and propose
a weighted label propagation algorithm (WLPA). Moreover, in
order to evaluate the performance results of various overlapping
community detection algorithms, we put forward a series of
evaluation criteria based on error distribution curve of
overlapping vertices. The experiment results show that the
algorithm has a faster speed and better community detection
results, and the evaluation criteria is in line with the inherent
characteristics of the social network overlapping community
structure.
Index Terms—social networks, overlapping community
detection, label propagation, evaluation criteria
I. I
NTRODUCTION
etwork community structure is one of the most popular
and important topological properties of networks.
Typically a network can be modeled with a graph, which
consists of nodes and edges. Non-overlapping community is
defined as the dense connected components of a network. In a
community, the nodes, which have same or similar attributes,
are closely interconnected, while in different communities,
nodes are sparsely interconnected [1][2]. At the same time, a
community that shares some nodes and edges, resulting in
overlap, is called an overlapping community [3][4]. Compared
with non-overlapping community, overlapping community can
better reflect the actual characteristics of the networks.
Discovering the different community structures in a complex
network can identify potential relationships between elements,
thus contributing to understanding and developing networks.
Therefore it has great social value. Overlapping community
detection algorithm [5] is designed to identify overlapping
Manuscript received September 30, 2014. This work is supported by the
National Natural Science Foundation of China under Grant No. 61472024,
61103030, 61170296 and 61190125, Science Foundation of China University
of Petroleum, Beijing (No.KYJJ2012-05-22), and the R&D Program
(2013BAH35F01).
Chao Tong, Jianwei Niu, Zhongyu Xie are with School of Computer
Science and Engineering, Beihang University, No.37 Xueyuan Road, 100191
Beijing, China. (e-mail: tongchao@buaa.edu.cn, niujianwei@buaa.edu.cn,
dakenz1990@163.com ). The corresponding author is Jianwei Niu.
Jinming Wen is with the Department of Mathematics and Statistics, McGill
University, 3480 University Street, Montreal, H3A 0B9, Canada. (e-mail:
jinming.wen@mail.mcgill.ca).
Fu Peng is with Department of Systems Engineering and Engineering
Management, The Chinese University of Hong Kong, Shatin, Hong Kong,
China. (e-mail: kevin.pengfu@gmail.com)
communities’ inherent structure in the networks, which means
nodes need to be divided into several groups in accordance with
the link relations. And above all, the algorithm can also detect
the communities’ overlaps.
The researchers have proposed several overlapping
community detection algorithms. Palla et al. proposed CPM [1]
algorithm for finding the network overlapping community
structure. Gregory put forward an algorithm named COPRA [6],
which adopts the idea of label propagation. COPRA is an
algorithm improved from RAK [7]. RAK uses the label
propagation to find the overlapping community structure. Xie
also gave a method named SLPA algorithm [8], which is very
similar with the COPRA algorithm. Chen et al. also proposed
an algorithm based on the game theory which is similar with
SLPA [9] too. Besides, there are some other label propagation
algorithms [10][11].
By analyzing the overlapping community detection, we can
summarize the main problems of the current study as follows. 1)
Existing overlapping community detection algorithms often
cannot meet the requirements of less computing speed, high
accuracy, not relying on the prior knowledge, and not being
sensitive to parameters. 2) Overlapping community detection
algorithm is often “biased”. 3) Lack of effective evaluation
criteria for overlapping community detection algorithm.
In this paper, we applied weighted label propagation to
overlapping community detection algorithm, and propose a
weighted label propagation algorithm (WLPA). In order to
evaluate the performance of various overlapping community
detection algorithms, we propose a series of evaluation criteria
based on error distribution curve of overlapping vertices. The
experiments show it has a faster speed and better community
detection results, and can avoid the above problems.
II.
WEIGHTED LABEL PROPAGATION OVERLAPPING COMMUNITY DETECTION
ALGORITHM
A. Algorithms Introduction
Label propagation algorithm (LPA) is a graph-based
semi-supervised learning method. The core idea is to use the
label information of marked node to predict that of unmarked
node. Raghavan, who first applied the idea of LPA to networks
community detection, proposed a non-overlapping community
detection algorithm, RAK [7]. RAK is to allow each node have
an associated label, the essence of the label is to use an integer
as the identifier of a node. The nodes with the same labels will
form a community after several iterations. RAK’s specific
algorithm steps are as follows:
(1) Initialize the labels of all nodes in the network, as for a
Weighted Label Propagation Algorithm for Overlapping
Community Detection
Chao Tong, Jianwei Niu, Senior Member, IEEE, Jinming Wen, Zhongyu Xie, and Fu Peng
IEEE ICC 2015 SAC - Social Networking
978-1-4673-6432-4/15/$31.00 ©2015 IEEE 1238