Greedy discrete particle swarm optimization for large-scale social network clustering

被引:90
作者
Cai, Qing [1 ]
Gong, Maoguo [1 ]
Ma, Lijia [1 ]
Ruan, Shasha [1 ]
Yuan, Fuyan [1 ]
Jiao, Licheng [1 ]
机构
[1] Xidian Univ, Minist Educ, Int Res Ctr Intelligent Percept & Computat, Key Lab Intelligent Percept & Image Understanding, Xian 710071, Shaanxi Provinc, Peoples R China
基金
中国国家自然科学基金;
关键词
Social network; Clustering; Community structure; Particle swarm optimization; Large-scale global optimization; GENETIC ALGORITHM; COMMUNITY; VERSION;
D O I
10.1016/j.ins.2014.09.041
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Social computing is a new paradigm for information and communication technology. Social network analysis is one of the theoretical underpinnings of social computing. Community structure detection is believed to be an effective tool for social network analysis. Uncovering community structures in social networks can be regarded as clustering optimization problems. Because social networks are characterized by dynamics and huge volumes of data, conventional nature-inspired optimization algorithms encounter serious challenges when applied to solving large-scale social network clustering optimization problems. In this study, we put forward a novel particle swarm optimization algorithm to reveal community structures in social networks. The particle statuses are redefined under a discrete scenario. The status updating rules are reconsidered based on the network topology. A greedy strategy is designed to drive particles to a promising region. To this end, a greedy discrete particle swarm optimization framework for large-scale social network clustering is suggested. To determine the performance of the algorithm, extensive experiments on both synthetic and real-world social networks are carried out. We also compare the proposed algorithm with several state-of-the-art network community clustering methods. The experimental results demonstrate that the proposed method is effective and promising for social network clustering. (C) 2014 Elsevier Inc. All rights reserved.
引用
收藏
页码:503 / 516
页数:14
相关论文
共 54 条
[1]  
[Anonymous], 2009, ELEMENTS STAT LEARNI
[2]  
[Anonymous], INF P EV COMP
[3]  
[Anonymous], 2012, IEEE C EVOL COMPUTAT
[4]   Local method for detecting communities [J].
Bagrow, JP ;
Bollt, EM .
PHYSICAL REVIEW E, 2005, 72 (04)
[5]   Models of social networks based on social distance attachment -: art. no. 056122 [J].
Boguñá, M ;
Pastor-Satorras, R ;
Díaz-Guilera, A ;
Arenas, A .
PHYSICAL REVIEW E, 2004, 70 (05) :8-1
[6]   A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems [J].
Chen, Wei-Neng ;
Zhang, Jun ;
Chung, Henry S. H. ;
Zhong, Wen-Liang ;
Wu, Wei-Gang ;
Shi, Yu-hui .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2010, 14 (02) :278-300
[7]  
Clauset A, 2004, PHYS REV E, V70, DOI 10.1103/PhysRevE.70.066111
[8]   The particle swarm - Explosion, stability, and convergence in a multidimensional complex space [J].
Clerc, M ;
Kennedy, J .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2002, 6 (01) :58-73
[9]   Comparing community structure identification -: art. no. P09008 [J].
Danon, L ;
Díaz-Guilera, A ;
Duch, J ;
Arenas, A .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2005, :219-228
[10]  
Datta S, 2006, SIAM PROC S, P153