基于标签传播的蚁群优化算法求解社区发现问题

社区发现问题对于研究复杂网络的特性具有重要作用。蚁群算法由于其采用分布式正反馈并行机制,具有较强的鲁棒性和稳定性,被越来越频繁地应用于社区发现领域。针对蚁群算法求解社区发现存在求解精度低、收敛速度慢的问题,提出一种基于标签传播的蚁群优化算法(BLP_ACO)。采用一种新的解向量表达方式,其中每个节点位置存放该节点所属社区的标签。在解的构造阶段提出基于节点凝聚性的蚂蚁转移策略,降低蚂蚁转移过程中的随机性,从而提高算法的精确度;将标签传播思想引入到蚁群搜索过程,使算法快速收敛。在解的优化阶段采用基于模块度优化的合并策略,进一步提高算法的求解精度;更新信息素时对所有处于社区内部的边滞留信息素。在真实网络和LFR基准网络上验证,结果表明该算法能够准确高效地挖掘出社区结构。

ANT COLONY OPTIMIZATION ALGORITHM BASED ON LABEL PROPAGATION FOR COMMUNITY DISCOVERY

Community discovery plays an important role in the study of the characteristics of complex networks.Ant colony algorithm has been applied more and more frequently in the field of community discovery due to its distributed positive feedback parallel mechanism and strong robustness and stability.However,it is found that ant colony optimization algorithm has problems of low accuracy and slow convergence speed in solving community problems.This paper proposed an ant colony optimization algorithm based on label propagation(BLP_ACO)for this problem.We proposed a new expression of solution vector in which each node located the label of the community to which the node belonged.In the construction stage of the solution,an ant transfer strategy based on node cohesion was proposed to reduce the randomness in the process of ant transfer,so as to improve the accuracy of the algorithm.In order to make the algorithm converge quickly,the idea of label propagation was introduced into the ant colony search process.In the optimization stage,the combined algorithm based on modularity optimization was adopted to further improve the precision of the algorithm.The pheromones were retained on all edges of the community when they were updated.It is verified that the algorithm can accurately and efficiently mine community structure on real network and LFR benchmark network.