[Science] Random walks on graphs with interval weights and precise marginals


The International Journal of Approximate Reasoning released an article by Damjan Škulj entitled Random walks on graphs with interval weights and precise marginals.

Abstract

We propose a model of random walks on weighted graphs where the weights are interval valued, and connect it to reversible imprecise Markov chains. While the theory of imprecise Markov chains is now well established, this is a first attempt to model reversible chains. In contrast with the existing theory, the probability models that have to be considered are now non-convex. This presents a difficulty in computational sense, since convexity is critical for the existence of efficient optimization algorithms used in the existing models. The second part of the paper therefore addresses the computational issues of the model. The goal is finding sets of weights which maximize or minimize expectations corresponding to multiple steps transition probabilities. In particular, we present a local optimization algorithm and numerically test its efficiency. We show that its application allows finding close approximations of the globally best solutions in reasonable time.

Keywords

  • Weighted graph; 
  • Random walk; 
  • Markov chain; 
  • Imprecise Markov chain; 
  • Reversible Markov chain; 
  • Local optimization
The article is available HERE.
Back to list of notificationsPublished: 26. April 2016 | Category: Achievements, Publikacija