Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
31/2014

Spectral distances on graphs

Jiao Gu, Bobo Hua and Shiping Liu

Abstract

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.

Received:
Feb 25, 2014
Published:
Feb 26, 2014

Related publications

inJournal
2015 Journal Open Access
Jiao Gu, Bobo Hua and Shiping Liu

Spectral distances on graphs

In: Discrete applied mathematics, 190-191 (2015), pp. 56-74