Spectral classes of regular, random, and empirical graphs

Abstract

We define a (pseudo-)distance between graphs based on the spectrum of the normalized Laplacian, which is easy to compute or to estimate numerically. It can therefore serve as a rough classification of large empirical graphs into families that share the same asymptotic behavior of the spectrum so that the distance of two graphs from the same family is bounded by $\mathcal{O}(1/n)$ in terms of size $n$ of their vertex sets. Numerical experiments demonstrate that the spectral distance provides a practically useful measure of graph dissimilarity.

References in corpus (1)

• Cross-species analysis of biological networks by Bayesian alignment

Cited by in corpus (6)

• Spectral distances on graphs
• Geometry and symmetry in biochemical reaction systems
• Spectral density of random graphs: convergence properties and application in model fitting
• Random geometric complexes and graphs on Riemannian manifolds in the thermodynamic limit
• Dynamic landscape models of coevolutionary games
• Constructing transient amplifiers for death-Birth updating: A case study of cubic and quartic regular graphs