Zhang Pan
Santa Fe Institute, Santa Fe, New Mexico 87501, USA and State Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China.
Phys Rev E Stat Nonlin Soft Matter Phys. 2015 Apr;91(4):042120. doi: 10.1103/PhysRevE.91.042120. Epub 2015 Apr 17.
The nonbacktracking operator for a graph is the adjacency matrix defined on directed edges of the graph. The operator was recently shown to perform optimally in spectral clustering in sparse synthetic graphs and have a deep connection to belief propagation algorithm. In this paper we consider nonbacktracking operator for Ising model on a general graph with a general coupling distribution and study the spectrum of this operator analytically. We show that spectral algorithms based on this operator is equivalent to belief propagation algorithm linearized at the paramagnetic fixed point and recovers replica-symmetry results on phase boundaries obtained by replica methods. This operator can be applied directly to systems with multiple states like Hopfield model. We show that spectrum of the operator can be used to determine number of patterns that stored successfully in the network, and the associated eigenvectors can be used to retrieve all the patterns simultaneously. We also give an example on how to control the Hopfield model, i.e., making network more sparse while keeping patterns stable, using the nonbacktracking operator and matrix perturbation theory.
图的非回溯算子是在图的有向边上定义的邻接矩阵。最近研究表明，该算子在稀疏合成图的谱聚类中表现最优，并且与信念传播算法有深刻联系。在本文中，我们考虑具有一般耦合分布的一般图上伊辛模型的非回溯算子，并对该算子的谱进行解析研究。我们证明基于该算子的谱算法等同于在顺磁不动点线性化的信念传播算法，并恢复了通过副本方法获得的相边界上的副本对称结果。该算子可直接应用于具有多个状态的系统，如霍普菲尔德模型。我们表明，该算子的谱可用于确定成功存储在网络中的模式数量，并且相关的特征向量可用于同时检索所有模式。我们还给出了一个示例，说明如何使用非回溯算子和矩阵扰动理论来控制霍普菲尔德模型，即让网络更稀疏同时保持模式稳定。
