Spectral distances on graphs.

By assigning a probability measure via the spectrum of the normalized Laplacian to each graph and using L p Wasserstein distances between probability measures, we define the corresponding spectral distances d p on the set of all graphs. This approach can even be extended to measuring the distances between infinite graphs. We prove that the diameter of the set of graphs, as a pseudo-metric space equipped with d 1 , is one. We further study the behavior of d 1 when the size of graphs tends to infinity by interlacing inequalities aiming at exploring large real networks. A monotonic relation between d 1 and the evolutionary distance of biological networks is observed in simulations. [ABSTRACT FROM AUTHOR]