Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109, USA.
Phys Rev E. 2019 Jul;100(1-1):012314. doi: 10.1103/PhysRevE.100.012314.
The spectrum of the adjacency matrix plays several important roles in the mathematical theory of networks and network data analysis, for example in percolation theory, community detection, centrality measures, and the theory of dynamical systems on networks. A number of methods have been developed for the analytic computation of network spectra, but they typically assume that networks are locally treelike, meaning that the local neighborhood of any node takes the form of a tree, free of short loops. Empirically observed networks, by contrast, often have many short loops. Here we develop an approach for calculating the spectra of networks with short loops using a message passing method. We give example applications to some previously studied classes of networks and find that the presence of loops induces substantial qualitative changes in the shape of network spectra, generating asymmetries, multiple spectral bands, and other features.
邻接矩阵的谱在网络的数学理论和网络数据分析中扮演着几个重要的角色，例如在渗流理论、社区检测、中心性度量和网络上的动力系统理论中。已经开发了许多用于分析计算网络谱的方法，但它们通常假设网络是局部树状的，这意味着任何节点的局部邻域都采用没有短环的树的形式。相比之下，经验观察到的网络通常有许多短环。在这里，我们使用消息传递方法开发了一种计算带有短环的网络谱的方法。我们给出了一些先前研究过的网络类别的应用示例，并发现环的存在会导致网络谱的形状发生实质性的定性变化，产生不对称、多个谱带和其他特征。
