Spectral classes of regular, random, and empirical graphs

We define a (pseudo-)distance between graphs based on the spectrum of the normalized Laplacian. Since this quantity can be computed easily, or at numerically estimated, it is suitable for comparing in particular large graphs. Numerical experiments demonstrate that the spectral distance provides a practically useful measure of graph dissimilarity. The asymptotic behavior of the Laplacian spectrum furthermore yields a tool for classifying families of graphs in such a way that the distance of two graphs from the same family is bounded by O(1/n)O(1/n) in terms of size n of their vertex sets.