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

摘要

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