Continuum of All-Pair Shortest-Path to All-Path via Random Walk

Date of Submission: 
April 19, 2013
Report Number: 
13-016
Report PDF: 
Abstract: 
A method is proposed to compute the continuum of paths, from shortest paths to all random paths between all pairs of nodes at once in a unified way. The analysis is based on treating the network as a random walk with an additional absorbing state named evaporating state reachable with nonzero probability from any state (so called "evaporating random walk"). The probability of avoiding absorption is tuned by a single parameter varying between 0 and 1, with lower values favoring shorter paths. A computational example is used to illustrate the method.