基于Spark的多策略蚁群算法求解最大团问题

作者：顾军华; 王守彬; 武君艳; 张素琪^*

来源：中国科学技术大学学报, 2019, 49(10): 851-860.

• 最大团
• Spark
• 蚁群算法
• 蚂蚁选点策略
• 局部改善

社会网络分析目前是数据挖掘领域的研究热点之一,凝聚子群是测量社会网络结构的重要指标,而最大团结构是社会网络中最紧密的凝聚子群,最大团问题的研究也成为社会网络分析的一个重要角度.随着大数据的发展,图中节点的丰富性和边结构的复杂性对求解最大团问题提出了更高的要求.为此提出了一种基于Spark的多策略蚁群算法求解最大团的算法.首先,该算法利用多条件选点策略扩大搜索空间,增加可行解的多样性,避免了陷入局部最优解;然后,采取一个局部搜索策略来提高该算法的精度和收敛速度;最后,在Spark分布式平台上并行地实现了该算法,验证了算法的并行性,证明该算法提高了算法处理大规模社区网络的执行效率.

• 单位
  天津商业大学; 河北工业大学