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 di, 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. (C) 2015 The Authors. Published by Elsevier B.V.