The Walk Distances in Graphs

Abstract

The walk distances in graphs are defined as the result of appropriate transformations of the ${\sum }_{k=0}^{\infty }(tA{)}^k$ proximity measures, where $A$ is the weighted adjacency matrix of a graph and $t$ is a sufficiently small positive parameter. The walk distances are graph-geodetic; moreover, they converge to the shortest path distance and to the so-called long walk distance as the parameter $t$ approaches its limiting values. We also show that the logarithmic forest distances which are known to generalize the resistance distance and the shortest path distance are a subclass of walk distances. On the other hand, the long walk distance is equal to the resistance distance in a transformed graph.

Accepted for publication in Discrete Applied Mathematics. 26 pages, 3 figures

References in corpus (3)

• Forest matrices around the Laplacian matrix
• The graph bottleneck identity
• Simple expressions for the long walk distance

Cited by in corpus (17)

• Network Geometry
• Developments in the theory of randomized shortest paths with a comparison of graph node distances
• A bag-of-paths framework for network data analysis
• Similarities on Graphs: Kernels versus Proximity Measures
• A graph interpretation of the least squares ranking method
• Measuring centrality by a generalization of degree
• Studying new classes of graph metrics
• Randomized Shortest Paths with Net Flows and Capacity Constraints
• Impact of network topology on efficiency of proximity measures for community detection
• Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization
• Covariance and Correlation Kernels on a Graph in the Generalized Bag-of-Paths Formalism
• Measuring Proximity in Attributed Networks for Community Detection
• Matrices of forests, analysis of networks, and ranking problems
• How to choose the most appropriate centrality measure? A decision tree approach
• Simple expressions for the long walk distance
• A topological interpretation of the walk distances
• The Shortest-Path distance on graphons