Spectra of networks containing short loops

Abstract

The spectrum of the adjacency matrix plays several important roles in the mathematical theory of networks and in 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 tree-like, 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.

arXiv comment8 pages, 4 figures

References in corpus (25)

• Modularity and community structure in networks
• Random graphs with arbitrary degree distributions and their applications
• Growing Scale-Free Networks with Tunable Clustering
• Random graphs with clustering
• Phase transition in the detection of modules in sparse networks
• Highly clustered scale-free networks
• Graph spectra and the detectability of community structure in networks
• Localization and centrality in networks
• Percolation on sparse networks
• Spectra of complex networks
• Random graphs containing arbitrary distributions of subgraphs
• Sparse random matrices: the eigenvalue spectrum revisited
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Tuning clustering in random networks with arbitrary degree distributions
• Spectra of Sparse Random Matrices
• Dynamical Systems on Networks: A Tutorial
• Bond percolation on a class of clustered random networks
• Percolation on dense graph sequences
• Hopping on the Bethe lattice: Exact results for densities of states and dynamical mean-field theory
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Spectra of random networks with arbitrary degrees
• Spectra of sparse regular graphs with loops
• Spectral density of random graphs with topological constraints
• Localization on low-order eigenvectors of data matrices
• Spectra of random networks in the weak clustering regime

Cited by in corpus (10)

• Message passing on networks with loops
• Linear stability analysis for large dynamical systems on directed random graphs
• Eigenvalue Repulsion and Eigenfunction Localization in Sparse Non-Hermitian Random Matrices
• The spectral density of dense random networks and the breakdown of the Wigner semicircle law
• Percolation in random graphs with higher-order clustering
• Atomic subgraphs and the statistical mechanics of networks
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Effects of clustering heterogeneity on the spectral density of sparse networks
• Belief propagation on networks with cliques and chordless cycles
• On the accuracy of message-passing approaches to percolation in complex networks