一种面向社会网络社区发现的改进粒子群优化算法

An Improved Particle-swarm-optimization Algorithm for Community Discovery in Social Networks

社区结构是反映社会网络整体性质的重要特征,挖掘社区结构对研究社会网络具有重要意义.本文提出一种基于模块度优化的改进粒子群优化算法用于社会网络的社区发现,该优化算法以模块度为优化目标,寻找模块度最优的社区结构;算法采用基于节点邻居表的粒子编码方案,并设计了一种连续空间粒子更新方案以避免产生非法粒子;算法引入了基于最多邻居从属的变异策略,提高粒子群算法的稳定性以及社区划分的质量.人工网络和真实网络中的实验结果表明,本文所提出的算法能够快速有效地揭示社会网络中的社区结构.

Community structure is the key feature for uncovering the global property in social networks, which is very important for studying social networks. In this paper, an improved PSO（ particle swarm optimization） algorithm based on modularity optimization for community discovery in social networks is proposed. The algorithm takes modularity as the optimization objective and discoveries community structure which produces the best modularity. The algorithm adopts an encoding method based on local neighborhoods. A particle-position adjustment strategy is designed to avoid the production of illegal particles. Furthermore, a mutation strategy based on maximum neighborhood similarity is introduced to guarantee the efficiency and stability of PSO. Experimental results on synthetic networks and real world networks show that the proposed algorithm can effectively discover the community structure in social networks.