Skip to main content

Research Repository

Advanced Search

Spectral distances on graphs

Gu, Jiao; Hua, Bobo; Liu, Shiping

Spectral distances on graphs Thumbnail


Authors

Jiao Gu

Bobo Hua

Shiping Liu



Abstract

By assigning a probability measure via the spectrum of the normalized Laplacian to each graph and using Lp Wasserstein distances between probability measures, we define the corresponding spectral distances dp 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 d1, is one. We further study the behavior of d1 when the size of graphs tends to infinity 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.

Citation

Gu, J., Hua, B., & Liu, S. (2015). Spectral distances on graphs. Discrete Applied Mathematics, 190-191, 56-74. https://doi.org/10.1016/j.dam.2015.04.011

Journal Article Type Article
Acceptance Date Apr 16, 2015
Publication Date Aug 20, 2015
Deposit Date Mar 16, 2015
Publicly Available Date Jun 4, 2015
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 190-191
Pages 56-74
DOI https://doi.org/10.1016/j.dam.2015.04.011
Keywords Wasserstein distance, Spectral measure, Random rooted graph, Asymptotic behavior, Biological networks.

Files




You might also like



Downloadable Citations