Randomized optimal transport on a graph: Framework and new distance measures

Guillaume Guex*, Ilkka Kivimäki, Marco Saerens

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

7 Citations (Scopus)


The recently developed bag-of-paths (BoP) framework consists in setting a Gibbs-Boltzmann distribution on all feasible paths of a graph. This probability distribution favors short paths over long ones, with a free parameter (the temperature T) controlling the entropic level of the distribution. This formalism enables the computation of new distances or dissimilarities, interpolating between the shortest-path and the resistance distance, which have been shown to perform well in clustering and classification tasks. In this work, the bag-of-paths formalism is extended by adding two independent equality constraints fixing starting and ending nodes distributions of paths (margins).When the temperature is low, this formalism is shown to be equivalent to a relaxation of the optimal transport problem on a network where paths carry a flow between two discrete distributions on nodes. The randomization is achieved by considering free energy minimization instead of traditional cost minimization. Algorithms computing the optimal free energy solution are developed for two types of paths: hitting (or absorbing) paths and non-hitting, regular, paths and require the inversion of an n × n matrix with n being the number of nodes. Interestingly, for regular paths on an undirected graph, the resulting optimal policy interpolates between the deterministic optimal transport policy (T → 0 + ) and the solution to the corresponding electrical circuit (T → ∞). Two distance measures between nodes and a dissimilarity between groups of nodes, both integrating weights on nodes, are derived from this framework.

Original languageEnglish
Pages (from-to)88-122
Number of pages35
JournalNetwork Science
Issue number1
Publication statusPublished - 1 Mar 2019
MoE publication typeA1 Journal article-refereed


  • Bag-of-paths
  • Distances between nodes
  • Link analysis
  • Network science
  • Optimal transportation
  • Randomized shortest path


Dive into the research topics of 'Randomized optimal transport on a graph: Framework and new distance measures'. Together they form a unique fingerprint.

Cite this