Kirkley Alec, Cantwell George T, Newman M E J
Department of Physics, University of Michigan, Ann Arbor, MI 48109, USA.
Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, USA.
Sci Adv. 2021 Apr 23;7(17). doi: 10.1126/sciadv.abf1211. Print 2021 Apr.
Belief propagation is a widely used message passing method for the solution of probabilistic models on networks such as epidemic models, spin models, and Bayesian graphical models, but it suffers from the serious shortcoming that it works poorly in the common case of networks that contain short loops. Here, we provide a solution to this long-standing problem, deriving a belief propagation method that allows for fast calculation of probability distributions in systems with short loops, potentially with high density, as well as giving expressions for the entropy and partition function, which are notoriously difficult quantities to compute. Using the Ising model as an example, we show that our approach gives excellent results on both real and synthetic networks, improving substantially on standard message passing methods. We also discuss potential applications of our method to a variety of other problems.
信念传播是一种广泛应用的消息传递方法，用于求解诸如流行病模型、自旋模型和贝叶斯图形模型等网络上的概率模型，但它存在一个严重的缺点，即在包含短环的网络这种常见情况下效果不佳。在此，我们为这个长期存在的问题提供了一个解决方案，推导了一种信念传播方法，该方法能够在具有短环（可能具有高密度）的系统中快速计算概率分布，同时还给出了熵和配分函数的表达式，而这些量的计算一直是非常困难的。以伊辛模型为例，我们表明我们的方法在真实网络和合成网络上都能给出优异的结果，相比标准的消息传递方法有显著改进。我们还讨论了我们的方法在各种其他问题上的潜在应用。
