Randomized Shortest-Path Problems: Two Related Models

DOI10.1162/neco.2009.11-07-643zbMath1192.90031OpenAlexW2122597713WikidataQ48290073 ScholiaQ48290073MaRDI QIDQ5323768

François Fouss, Luh Yen, Marco Saerens, Youssef Achbany

Publication date: 30 July 2009

Published in: Neural Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1162/neco.2009.11-07-643

zbMATH Keywords

necessary conditionsoptimal policyfinite Markov chainexpected Shannon entropy spread

Mathematics Subject Classification ID

Stochastic network models in operations research (90B15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Related Items

Interpolating between random walks and optimal transportation routes: flow with multiple sources and targets ⋮ Randomized shortest paths with net flows and capacity constraints ⋮ The stochastic shortest-path problem for Markov chains with infinite state space with applications to nearest-neighbor lattice chains ⋮ Different closed-form expressions for generalized entropy rates of Markov chains ⋮ Design of biased random walks on a graph with application to collaborative recommendation ⋮ A bag-of-paths framework for network data analysis ⋮ Agglomerative clustering via maximum incremental path integral ⋮ A sum-over-paths extension of edit distances accounting for all sequence alignments ⋮ Semi-supervised classification and betweenness computation on large, sparse, directed graphs ⋮ Probabilistic choice (models) as a result of balancing multiple goals ⋮ Developments in the theory of randomized shortest paths with a comparison of graph node distances ⋮ Sparse randomized shortest paths routing with Tsallis divergence regularization ⋮ A simple extension of the bag-of-paths model weighting path lengths by a Poisson distribution

Uses Software

• GMRFLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Graphs, networks and algorithms.
• Characteristic functions of directed graphs and applications to stochastic equilibrium problems
• Entropy maximization for Markov and semi-Markov processes
• Entropy Rate and Maximum Entropy Methods for Countable Semi-Markov Chains
• Information Theory and Statistical Mechanics
• The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
• Direct Methods for Sparse Linear Systems
• Biological Sequence Analysis
• Algorithms on Strings, Trees and Sequences
• Decomposition of Path Choice Entropy in General Transport Networks
• The entropy of Markov trajectories
• Fastest Mixing Markov Chain on a Graph
• Approximate Dynamic Programming
• Space-Time Approach to Non-Relativistic Quantum Mechanics
• Planning Algorithms
• Elements of Information Theory