Sparse randomized shortest paths routing with Tsallis divergence regularization

Computational aspects of data analysis and big data (68T09) Programming involving graphs or networks (90C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random walks on graphs (05C81) Stochastic network models in operations research (90B15)

Abstract: This work elaborates on the important problem of (1) designing optimal randomized routing policies for reaching a target node t from a source note s on a weighted directed graph G and (2) defining distance measures between nodes interpolating between the least cost (based on optimal movements) and the commute-cost (based on a random walk on G), depending on a temperature parameter T. To this end, the randomized shortest path formalism (RSP, [2,99,124]) is rephrased in terms of Tsallis divergence regularization, instead of Kullback-Leibler divergence. The main consequence of this change is that the resulting routing policy (local transition probabilities) becomes sparser when T decreases, therefore inducing a sparse random walk on G converging to the least-cost directed acyclic graph when T tends to 0. Experimental comparisons on node clustering and semi-supervised classification tasks show that the derived dissimilarity measures based on expected routing costs provide state-of-the-art results. The sparse RSP is therefore a promising model of movements on a graph, balancing sparse exploitation and exploration in an optimal way.

Recommendations

Cites work

Cited in

(6)

Describes a project that uses

Uses Software

This page was built for publication: Sparse randomized shortest paths routing with Tsallis divergence regularization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2036747)