Percolation and matrix spectrum through NIB message passing

Abstract

Given its computational efficiency and versatility, belief propagation is the most prominent message passing method in several applications. In order to diminish the damaging effect of loops on its accuracy, the first explicit version of generalized belief propagation for networks, the KCN-method, was recently introduced. This approach was originally developed in the context of two target problems: percolation and the calculation of the spectra of sparse matrices. Later on, the KCN-method was extended in order to deal with inference in the context of probabilistic graphical models on networks. It was in this scenario where an improvement on the KCN-method, the NIB-method, was conceived. We show here that this improvement can also achieved in the original applications of the KCN-method, namely percolation and matrix spectra.