The Shortest-Path distance on graphons

Abstract

We define an analogue of the shortest-path distance for graphons. The proposed method is rooted on the extension to graphons of Varadhan's formula, a result that links the solution of the heat equation on a Riemannian manifold to its geodesic distance. The resulting metric is integer-valued, and for step graphons obtained from finite graphs it is essentially equivalent to the usual shortest-path distance. We further draw a link between the Varadhan distance and the communicability distance, that contains information from all paths, not just shortest-paths, and thus provides a finer distance on graphons along with a natural isometric embedding into a Hilbert space.

38 pages, 3 figures

References in corpus (9)

• An $L^p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions
• Graphon Mean Field Games and the GMFG Equations
• A Class of Graph-Geodetic Distances Generalizing the Shortest-Path and the Resistance Distances
• Centrality measures for graphons: Accounting for uncertainty in networks
• The Walk Distances in Graphs
• Ollivier-Ricci curvature convergence in random geometric graphs
• The Forest Metrics for Graph Vertices
• Random hyperbolic graphs in $d+1$ dimensions
• Pattern Formation in Random Networks Using Graphons