大规模符号网络划分的学习驱动型扩展变邻域搜索算法  

Learning-driven extended variable neighborhood search forsigned graph partitioning

作　　者：陶子君 陆芷 蒙炳金 Tao Zijun;Lu Zhi;Meng Bingjin(Business School,University of Shanghai for Science&Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机应用研究》2025年第3期770-776,共7页Application Research of Computers

基　　金：国家自然科学基金青年项目(72101149);上海市浦江人才计划资助项目(22PJC080)。

摘　　要：给定一个无向图,符号网络划分问题(signed graph partitioning problem,SGPP)是将节点集合划分为K(K≥2)个互不相交的非空分组,旨在最小化所有位于分组内的负符号边权重之和加上位于分组之间的正符号边权重之和,使网络划分结构尽量趋于平衡。SGPP是NP难问题,在计算机视觉、社交网络分析、生物信息学等实际领域中具有重要应用。但大数据时代的到来给求解大规模SGPP带来一定的挑战。因此,设计新颖且高效的学习驱动型扩展变邻域搜索算法(learning driven extended variable neighborhood search,LDEVNS)来求解SGPP。具体来说,该算法设计全新的快速增量更新策略以及高效的扩展变邻域搜索,同时结合强化学习机制来调整算法搜索过程中的前进方向,进一步探索更有希望的解空间区域来找到更高质量的求解方案。实验部分使用15组大规模社交网络图来评估LDEVNS的高性能,实验结果显示,LDEVNS在求解质量和计算时间方面相较于当前表现最佳的算法具有显著优势,同时也验证了强化学习在LDEVNS中的有效性。Given an undirected signed graph,the SGPP divides the set of nodes into K(K≥2)pairwise disjoint nonempty subsets to minimize the number of positive edges between the subsets and the number of negative edges within the subsets.The SGPP is an NP-hard problem with significant applications in real-world fields such as computer vision,social network analysis,bioinformatics,etc.However,the SGPP has become more challenging to address in the big data era.This paper proposed a learning driven extended variable neighborhood search(LDEVNS)to tackle the SGPP.Specifically,it designed a new fast incremental update strategy and an efficient extended variable neighborhood search.To explore the search space more efficiently,it combined a reinforcement learning mechanism to guide the search direction.The experiment utilized 15 large-scale social networks to assess the performance of the LDEVNS algorithm.Experimental results show that the LDEVNS outperforms the best-performing algorithms in terms of solution quality and computing time.Additionally,it verifies the effectiveness of the reinforcement learning mechanism in the LDEVNS.

关 键 词：符号网络划分 启发式 变邻域搜索 强化学习 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]