Groupe d’études et de recherche en analyse des décisions

G-2016-83

The RW index: A new distance measure based on random walks

, , et

Considering a graph as a network of resistances, Klein and Randić (1993) proposed the definition of a distance measure. Indeed, if each edge of the graph represents a resistance of \(1 \Omega\), the equivalent resistance of the graph between each pair of vertices may be used as a distance. Based upon random walks in graphs, Stephenson and Zelen (1989) built a computational model to find the probability that each edge is used. From a mathematical point of view, both articles are based upon exactly the same model and the link between random walks and the electrical representation was established by Newman (2005) when defining an alternative to Freeman's betweenness centrality (1977), (1979) based upon random walks.

In the present paper, the similitude between these two processes is exploited to propose a new random walks based distance measure that may be defined as the expected length of a walk between any pair of vertices. From this new definition, the RW Index is proposed that sums the expected walks lengths between pairs of vertices exactly in the same way as the Wiener index sums the shortest paths distances or the Kirchhoff index sums the equivalent resistances. In the same way as the Wiener index (Caporossi, 2012), vertex and edge decompositions of the RW and Kirchhoff indices are proposed. Interestingly, we show that even if the random walks and the resistance distances are based upon a similar mathematical model, they are not equivalent.

, 12 pages