标题： 循环动态消息传递用于网络上的流行病 显示英文标题

标题： Recurrent Dynamic Message Passing with Loops for Epidemics on Networks

摘要： 几种理论方法已被开发用于近似网络上的流行率和流行阈值。 其中，递归动态消息传递（rDMP）理论通过防止网络边上的回音室效应，提供了最先进的性能。 然而，rDMP理论是通过直观的随意方式推导出来的，缺乏坚实的理论基础，导致了概率不一致的缺陷。 此外，现实世界的网络是聚类的，并充满了像三角形这样的局部环，而rDMP基于局部树状网络结构的假设，这使得rDMP在实际应用中可能效率不高。 在本工作中，针对循环状态的流行病，我们首先证明了回音室效应不仅存在于边上，也存在于局部环中，rDMP-like方法无法避免。 然后，我们以一种系统的方式纠正rDMP的不足，从而自然地引入了新的高阶动态消息，扩展了rDMP以处理局部环。 通过对扩展的消息传递方程进行线性化，给出了一个新的流行病阈值估计，即由一个名为三角形非回溯矩阵的矩阵的主特征值的倒数给出。 在合成和现实世界网络上进行的数值实验评估了我们的方法，其有效性在流行病流行率和阈值预测任务中得到了验证。 此外，我们的方法有可能加快网络中免疫、影响力最大化和鲁棒性优化问题的求解。 显示英文摘要

摘要： Several theoretical methods have been developed to approximate prevalence and threshold of epidemics on networks. Among them, the recurrent dynamic message-passing (rDMP) theory offers a state-of-the-art performance by preventing the echo chamber effect in network edges. However, the rDMP theory was derived in an intuitive ad-hoc way, lacking a solid theoretical foundation and resulting in a probabilistic inconsistency flaw. Furthermore, real-world networks are clustered and full of local loops like triangles, whereas rDMP is based on the assumption of a locally tree-like network structure, which makes rDMP potentially inefficient on real applications. In this work, for the recurrent-state epidemics, we first demonstrate that the echo chamber effect exits not only in edges but also in local loops, which rDMP-like method can not avoid. We then correct the deficiency of rDMP in a principled manner, leading to the natural introduction of new higher-order dynamic messages, extending rDMP to handle local loops. By linearizing the extended message-passing equations, a new epidemic threshold estimation is given by the inverse of the leading eigenvalue of a matrix named triangular non-backtracking matrix. Numerical experiments conducted on synthetic and real-world networks to evaluate our method, the efficacy of which is validated in epidemic prevalence and threshold prediction tasks. In addition, our method has the potential to speed up the solution of the immunization, influence maximization, and robustness optimization problems in the networks.