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

Multi-strategy ant colony algorithm for solving the maximum clique problem based on Spark

作　　者：顾军华 王守彬 武君艳 张素琪[3] GU Junhua;WANG Shoubin;WU Junyan;ZHANG suqi(School of Artificial Intelligence, Hebei University of Technology, Tianjin 300401, China;Hebei Province Key Laboratory of Big Data Computing, Tianjin 300401, China;School of Information Engineering, Tianjin University of Commerce, Tianjin 300134, China)

机构地区：[1]河北工业大学人工智能与数据科学学院,天津300401 [2]河北省大数据计算重点实验室,天津300401 [3]天津商业大学信息工程学院,天津300134

出　　处：《中国科学技术大学学报》2019年第10期851-860,共10页JUSTC

基　　金：国家自然科学基金(61802282);天津市自然科学基金(19JCTPJC54200);河北省创新能力提升计划(199676146H)资助。

摘　　要：社会网络分析目前是数据挖掘领域的研究热点之一,凝聚子群是测量社会网络结构的重要指标,而最大团结构是社会网络中最紧密的凝聚子群,最大团问题的研究也成为社会网络分析的一个重要角度.随着大数据的发展,图中节点的丰富性和边结构的复杂性对求解最大团问题提出了更高的要求.为此提出了一种基于Spark的多策略蚁群算法求解最大团的算法.首先,该算法利用多条件选点策略扩大搜索空间,增加可行解的多样性,避免了陷入局部最优解;然后,采取一个局部搜索策略来提高该算法的精度和收敛速度;最后,在Spark分布式平台上并行地实现了该算法,验证了算法的并行性,证明该算法提高了算法处理大规模社区网络的执行效率.Social network analysis has become one of the hotspots in data mining research.Aggregating subgroups are important indicators for measuring the structure of social networks.The maximum clique structure is the most compact condensed subgroup in social networks.The study of the maximum clique problem has also become an important angle of social network analysis.With the development of big data,the massiveness of the nodes and the complexity of the edge structure in the graph put forward a higher requirement for solving the maximum clique problem.Therefore,a multi-strategy ant colony algorithm is proposed for solving the maximum clique problem first,the algorithm uses a multi-conditional selection strategy to expand the search space,increases the diversity of feasible solutions,and avoids falling into the local optimal solution.At the same time,a local search strategy is adopted to improve the accuracy and convergence speed of the algorithm;Then,the algorithm is implemented in parallel on the Spark distributed platform,which verifies the parallelism of the algorithm and improves the efficiency of the algorithm in handling large-scale community networks.

关 键 词：最大团 SPARK 蚁群算法 蚂蚁选点策略 局部改善 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]