CAS Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China.
Phys Rev E. 2017 Oct;96(4-1):042303. doi: 10.1103/PhysRevE.96.042303. Epub 2017 Oct 16.
There have been several spectral bounds for the percolation transition in networks, using spectrum of matrices associated with the network such as the adjacency matrix and the nonbacktracking matrix. However, they are far from being tight when the network is sparse and displays clustering or transitivity, which is represented by existence of short loops, e.g., triangles. In this paper, for the bond percolation, we first propose a message-passing algorithm for calculating size of percolating clusters considering effects of triangles, then relate the percolation transition to the leading eigenvalue of a matrix that we name the triangle-nonbacktracking matrix, by analyzing stability of the message-passing equations. We establish that our method gives a tighter lower bound to the bond percolation transition than previous spectral bounds, and it becomes exact for an infinite network with no loops longer than 3. We evaluate numerically our methods on synthetic and real-world networks, and discuss further generalizations of our approach to include higher-order substructures.
已经有几种网络渗流相变的谱界，使用与网络相关的矩阵的谱，如邻接矩阵和非回返矩阵。然而，当网络稀疏且显示聚类或传递性时，它们远非紧密的，这由短环的存在表示，例如三角形。在本文中，对于键渗流，我们首先提出了一种考虑三角形影响的消息传递算法来计算渗流簇的大小，然后通过分析消息传递方程的稳定性，将渗流相变与我们称之为三角形非回返矩阵的矩阵的主特征值联系起来。我们证明，我们的方法比以前的谱界对键渗流相变给出了更紧的下界，并且对于没有长度超过 3 的环的无限网络，它是精确的。我们在合成和真实网络上数值评估了我们的方法，并进一步讨论了我们的方法的推广，以包括更高阶的子结构。
