Article ID Journal Published Year Pages File Type
4598869 Linear Algebra and its Applications 2016 20 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Algebra and Number Theory
Authors
, , , ,