Abstract: A multi-objective particle swarm optimization with decomposition for network community discovery was proposed and the multi-objective optimization model of community discovery was constructed through comparing the optimization objectives of different community discovery algorithms in social network. The proposed algorithm adopted the Chebyshev method to decompose the multi-objective optimization problem into a number of single-objective optimization sub-problems and used Particle Swarm Optimization (PSO) to discover the community structure. Moreover, a new local search based mutation strategy was put forward to improve the search efficiency and speed up convergence. The proposed algorithm overcame the defects of single objective optimization methods. The experimental results on synthetic networks and real-world networks show that the proposed algorithm can discover the community structure rapidly and accurately and reveal the hierarchical community structure.

Key words: social network, community discovery, multi-objective decomposition, Particle Swarm Optimization (PSO), mutation strategy

摘要： 通过分析社会网络中社区发现问题的优化目标,构造了社区发现的多目标优化模型,提出一种网络社区发现的多目标分解粒子群优化算法。该算法采用切比雪夫法将多目标优化问题分解为多个单目标优化子问题,使用粒子群优化(PSO)算法对社区结构进行挖掘,并引入了一种新颖的基于局部搜索的变异策略以提高算法的搜索效率和收敛速度,该算法克服了单目标优化算法存在的解单一以及难以发现社区层次结构的缺陷。人工网络及真实网络上的实验结果表明,该算法能够快速准确地挖掘网络社区并揭示社区的层次结构。

关键词: 社会网络, 社区发现, 多目标分解, 粒子群优化, 变异策略