一种求解高密度最大权重团的信息传播算法  

An Information Propagation Algorithm for Solving High-density Maximum Weight Groups

作　　者：于卓 王晓峰[1,2] 吴宇翔 谢志新 曹泽轩 YU Zhuo;WANG Xiaofeng;WU Yuxiang;XIE Zhixin;CAO Zexuan(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;Key Laboratory of Image and Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021 [2]北方民族大学图像图形智能处理国家民委重点实验室,宁夏银川750021

出　　处：《郑州大学学报（理学版）》2024年第4期56-64,共9页Journal of Zhengzhou University:Natural Science Edition

基　　金：国家自然科学基金项目(62062001,61962002);宁夏自然科学基金项目(2020AAC03214);北方民族大学重大专项(ZDZX201901)。

摘　　要：在高密度复杂结构带权无向图中,由于信息传递复杂,传统信息传播算法求解最大权重团问题效率较低。利用最大权重独立集与最大权重团的映射关系提出一种针对高密度带权无向图求解最大权重团问题算法,该算法以最大积信息传播算法为框架,将最大权重团的约束条件与置信传播算法迭代方程相结合,设计信息传播算法势函数。同时,将高密度复杂结构带权无向图映射为因子图,并进行去环操作,利用信息传播迭代式进行特征收敛计算,通过迭代收敛后的最大后验概率计算最大权重团最优解。基于不同密度随机图进行实验对比分析,实验结果表明,该算法求解高密度复杂结构带权无向图最大权重问题时非常有效,求解总权值的准确度与求解速率均高于标准置信传播算法。In the weighted undirected graph with high density and complex structure,due to the complex information transfer,the traditional information propagation algorithm was less efficient to solve the maximum weighted clique problem.Using the mapping relationship between the maximum weight independent set and the maximum weight clique,an algorithm was proposed to solve the maximum weight group problem for high-density weighted undirected graphs.The propagation algorithm was combined with the iterative equation to design the potential function of the information propagation algorithm.At the same time,the weighted undirected graph of the high-density complex structure was mapped into a factor graph,and the deloop operation was performed,and the feature convergence calculation was performed by iterative information propagation,and the optimal solution of the maximum weight group was calculated by the maximum posterior probability after iterative convergence.Experimental results were compared and analyzed based on random graphs with different densities.The results showed that the algorithm was very effective in solving the maximum weight problem of weighted undirected graphs with high-density complex structures,and the accuracy and speed of solving the total weights were higher than those of the standard belief propagation algorithm.

关 键 词：最大权重团 信息传播算法 因子图 最大积算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]