Developments in the theory of randomized shortest paths with a comparison of graph node distances

Abstract

There have lately been several suggestions for parametrized distances on a graph that generalize the shortest path distance and the commute time or resistance distance. The need for developing such distances has risen from the observation that the above-mentioned common distances in many situations fail to take into account the global structure of the graph. In this article, we develop the theory of one family of graph node distances, known as the randomized shortest path dissimilarity, which has its foundation in statistical physics. We show that the randomized shortest path dissimilarity can be easily computed in closed form for all pairs of nodes of a graph. Moreover, we come up with a new definition of a distance measure that we call the free energy distance. The free energy distance can be seen as an upgrade of the randomized shortest path dissimilarity as it defines a metric, in addition to which it satisfies the graph-geodetic property. The derivation and computation of the free energy distance are also straightforward. We then make a comparison between a set of generalized distances that interpolate between the shortest path distance and the commute time, or resistance distance. This comparison focuses on the applicability of the distances in graph node clustering and classification. The comparison, in general, shows that the parametrized distances perform well in the tasks. In particular, we see that the results obtained with the free energy distance are among the best in all the experiments.

30 pages, 4 figures, 3 tables

References in corpus (4)

• Modularity and community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• A bag-of-paths framework for network data analysis

Cited by in corpus (14)

• Effective Distances for Epidemics Spreading on Complex Networks
• Two betweenness centrality measures based on Randomized Shortest Paths
• A bag-of-paths framework for network data analysis
• Similarities on Graphs: Kernels versus Proximity Measures
• Studying new classes of graph metrics
• Randomized Shortest Paths with Net Flows and Capacity Constraints
• Absorbing Random Walks Interpolating Between Centrality Measures on Complex Networks
• 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 Constrained Randomized Shortest-Paths Framework for Optimal Exploration
• Dissecting graph measure performance for node clustering in LFR parameter space
• Measuring Proximity in Attributed Networks for Community Detection
• Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling