A Class of Graph-Geodetic Distances Generalizing the Shortest-Path and the Resistance Distances

Abstract

A new class of distances for graph vertices is proposed. This class contains parametric families of distances which reduce to the shortest-path, weighted shortest-path, and the resistance distances at the limiting values of the family parameters. The main property of the class is that all distances it comprises are graph-geodetic: $d(i,j)+d(j,k)=d(i,k)$ if and only if every path from $i$ to $k$ passes through $j$. The construction of the class is based on the matrix forest theorem and the transition inequality.

14 pages. Discrete Applied Mathematics

References in corpus (4)

• Forest matrices around the Laplacian matrix
• Spanning Forests and the Golden Ratio
• The Forest Metrics for Graph Vertices
• The graph bottleneck identity

Cited by in corpus (23)

• Network Geometry
• Two betweenness centrality measures based on Randomized Shortest Paths
• Developments in the theory of randomized shortest paths with a comparison of graph node distances
• A bag-of-paths framework for network data analysis
• The Walk Distances in Graphs
• Similarities on Graphs: Kernels versus Proximity Measures
• Studying new classes of graph metrics
• The graph bottleneck identity
• Nonlocal PageRank
• Learning Representations from Dendrograms
• Randomized Shortest Paths with Net Flows and Capacity Constraints
• From random walks to distances on unweighted graphs
• Covariance and Correlation Kernels on a Graph in the Generalized Bag-of-Paths Formalism
• Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization
• A Bellman-Ford algorithm for the path-length-weighted distance in graphs
• Simple expressions for the long walk distance
• How to choose the most appropriate centrality measure? A decision tree approach
• Unsupervised Representation Learning with Minimax Distance Measures
• Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling
• A topological interpretation of the walk distances
• Memory-Efficient Sampling for Minimax Distance Measures
• The Shortest-Path distance on graphons
• Effective Resistance Preserving Directed Graph Symmetrization