Spectral distances on graphs
Jiao Gu, Bobo Hua, and Shiping Liu
Contact the author: Please use for correspondence this email.
Submission date: 25. Feb. 2014
published in: Discrete applied mathematics, 190-191 (2015), p. 56-74
DOI number (of the published article): 10.1016/j.dam.2015.04.011
Download full preprint: PDF (609 kB)
By assigning a probability measure via the spectrum of the normalized Laplacian to each graph and using Lp Wasserstein distances between probability measures, we deﬁne the corresponding spectral distances dp on the set of all graphs. This approach can even be extended to measuring the distances between inﬁnite graphs. We prove that the diameter of the set of graphs, as a pseudo-metric space equipped with d1, is one. We further study the behavior of d1 when the size of graphs tends to inﬁnity by interlacing inequalities aiming at exploring large real networks. A monotonic relation between d1 and the evolutionary distance of biological networks is observed in simulations.