Developments in the theory of randomized shortest paths with a comparison of graph node distances
Open accessThe DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fouss, F., Pirotte, A., Renders, J.-M., & Saerens, M. (2007) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.46 · Cited by 1,265
Self-citationClassification in Networked Data: A Toolkit and a Univariate Case Study
(2007) · Journal of Machine Learning Research · doi:10.5555/1248659.1248693 · Cited by 452
The electrical resistance of a graph captures its commute and cover times
Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R., & Tiwari, P. (1996) · Computational Complexity · doi:10.1007/bf01270385 · Cited by 328
Cited by
R Package gdistance : Distances and Routes on Geographical Grids
van Etten, J. (2017) · Journal of Statistical Software · doi:10.18637/jss.v076.i13 · Cited by 439
Deterministic, random, or in between? Inferring the randomness level of wildlife movements
Goicolea, T., Gastón, A., Cisneros-Araujo, P., García-Viñas, J. I., & Mateo-Sánchez, M. C. (2021) · Movement Ecology · doi:10.1186/s40462-021-00273-7 · Cited by 19
Progress and prospects of quantitative simulation research on ancient human migration paths
Wang, L., Peng, P., Liu, X., & Chen, F. (2025) · Chinese Science Bulletin · doi:10.1360/tb-2025-0148
Metadata
- Authors
- Kivimäki, I., Shimbo, M., & Saerens, M.
- Venue
- Physica A: Statistical Mechanics and its Applications
- Publisher
- Elsevier BV
- Published
- 2014-01
- Volume
- 393
- Pages
- 600-616
- ISSN
- 0378-4371 (ISSN-L)
- OpenAlex
- W2065229575
- Cited by
- 75
- References
- 3
- FWCI
- 4.78
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.