Randomized Shortest Paths with Net Flows and Capacity Constraints
  This work extends the randomized shortest paths (RSP) model by investigating
the net flow RSP and adding capacity constraints on edge flows. The standard
RSP is a model of movement, or spread, through a network interpolating between
a random-walk and a shortest-path behavior [30, 42, 49]. The framework assumes
a unit flow injected into a source node and collected from a target node with
flows minimizing the expected transportation cost, together with a relative
entropy regularization term. In this context, the present work first develops
the net flow RSP model considering that edge flows in opposite directions
neutralize each other (as in electric networks), and proposes an algorithm for
computing the expected routing costs between all pairs of nodes. This quantity
is called the net flow RSP dissimilarity measure between nodes. Experimental
comparisons on node clustering tasks indicate that the net flow RSP
dissimilarity is competitive with other state-of-the-art dissimilarities. In
the second part of the paper, it is shown how to introduce capacity constraints
on edge flows, and a procedure is developed to solve this constrained problem
by exploiting Lagrangian duality. These two extensions should improve
significantly the scope of applications of the RSP framework.
