Abstract: Community detection is one of important research elements of complex networks. Traditional community detection algorithms are ineffective when the structure of complex networks is unclear. They cannot effectively exploit the easily accessible a priori information in complex networks. A semi-supervised community detection algorithm based on particle competition (SSPC) is proposed to solve community detection problem of complex networks. SSPC combines the node particle competition and the edge particle competition. Firstly, SSPC generates particles on the tagged nodes through a priori information in the network. Next, the particles perform walking and restarting steps in the network through established rules, which fully reflects particles’ tendency to walk, reducing particles’ randomness walking, accelerating particles’ convergence speed and limiting particles’ walking range. Finally, when the particles reach convergence, the nodes in the network will be occupied by a certain class of particles. The community structure of network is revealed based on the nodes occupied by each class of particles. Experimental comparisons with representative community detection algorithms of recent years on real network datasets and the LFR artificial benchmark network reveal that SSPC outperforms other algorithms overall in NMI index and can obtain better community detection results.

Key words: particle competition, semi-supervised learning, community detection, particle walking, restart mechanism

摘要： 社区发现是复杂网络重要研究内容之一。传统社区发现算法在复杂网络结构不清晰时效果不佳，并且无法有效利用复杂网络中易获取的先验信息。为了解决复杂网络的社区发现问题，提出一种融合节点粒子竞争机制和边粒子竞争机制的半监督社区发现算法（SSPC）。该算法首先通过网络中的先验信息在已标记节点上产生粒子。接下来粒子通过既定的规则在网络中执行游走和重启步骤，充分体现粒子游走的倾向性，降低粒子游走的随机性，加快粒子的收敛速度并且限制粒子游走范围。最后，当粒子达到收敛状态时，网络中的节点将被某一类粒子占据。根据各类粒子占据的节点来揭示网络的社区结构。在真实网络数据集和LFR人工基准网络上与近几年具有代表性的社区发现算法进行实验对比，发现SSPC算法在NMI指标上整体优于其他算法，可以获得更好的社区发现结果。

关键词: 粒子竞争机制, 半监督学习, 社区发现, 粒子游走, 重启机制