TY - JOUR

T1 - Randomized shortest paths with net flows and capacity constraints

AU - Courtain, Sylvain

AU - Leleux, Pierre

AU - Kivimäki, Ilkka

AU - Guex, Guillaume

AU - Saerens, Marco

PY - 2021

Y1 - 2021

N2 - 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 (Kivimäki et al., 2014; Saerens et al., 2009; Yen et al., 2008). 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.

AB - 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 (Kivimäki et al., 2014; Saerens et al., 2009; Yen et al., 2008). 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.

KW - Complex networks

KW - Distances between nodes

KW - Graph mining

KW - Link analysis

KW - Network data analysis

KW - Network science

UR - http://www.scopus.com/inward/record.url?scp=85099627642&partnerID=8YFLogxK

U2 - 10.1016/j.ins.2020.10.005

DO - 10.1016/j.ins.2020.10.005

M3 - Article

AN - SCOPUS:85099627642

JO - Information Sciences (Elsevier)

JF - Information Sciences (Elsevier)

SN - 0020-0255

ER -