无公共边的双圈图上置信传播算法的收敛性和正确性  

Convergence and Correctness of Belief Propagation Algorithms for Double-Cycles Graphs with No Common Edge

作　　者：靳艺香 杨卫华 JIN Yixiang;YANG Weihua(College of Mathematics,Taiyuan University of Technology,Jinzhong Shanxi 030600,China)

机构地区：[1]太原理工大学数学学院,山西晋中030600

出　　处：《新疆大学学报（自然科学版）（中英文）》2023年第3期274-285,共12页Journal of Xinjiang University(Natural Science Edition in Chinese and English)

基　　金：山西省基础研究计划项目“连通性条件下图的圈结构若干问题研究”(20210302123097)。

摘　　要：为了研究置信传播算法在无公共边的双圈图上的收敛性,以及其收敛的正确性,提出了无公共边的双圈图的置信传播算法和无公共边的二元双圈图的纠正置信传播算法,并给出了无公共边的双圈图全局收敛的条件.应用这两种算法,对无公共边的双圈图进行仿真实验.结果表明:1)全局收敛率为100%;2)稳态置信与正确边际分布不同,但配置可能相同;二元稳态纠正置信与正确边际分布完全相同.In order to study the convergence of belief propagation algorithms on double-cycles graphs with no common edge and its convergence correctness,in this paper,a belief propagation algorithm for the double-cycles graphs with no common edge and a correction belief propagation algorithm for the binary double-cycles graphs with no common edge are presented,and a condition of global convergence for the double-cycles graphs with no common edge is given.The two algorithms are used to simulate the double-cycles graphs with no common edge.The results show that:1)The global convergence percentage is 100%;2)The steady-state belief is different from the correct marginal distribution,but the configuration may be the same;The binary steady-state correction belief is identical to the correct marginal distribution.

关 键 词：置信传播算法 纠正置信传播算法 双圈图 附加树 仿真实验 

分 类 号：O157.5[理学—数学] O242.21[理学—基础数学]