Expected distance based on random walks

Eglantine Camby 1, 2 Gilles Caporossi 3 Marcia Paiva 4 Marcelo Eduardo Vieira Segatto 4
2 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : By considering a graph as a network of resistances, Klein and Randi c [14] proposed the definition of a distance measure. Indeed, if each edge of the graph represents a resistance of 1Ω, 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 [17] 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 [16] when defining an alternative to Freeman’s betweenness cen- trality [9, 10] based upon random walks. In the present paper, the similitude between these two processes is ex- ploited 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. We call it the expected distance and we prove that it is actually a distance. 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. We compare the three indices and establish the vertex and the edge decompositions for both. We compute some value of the RW index for some families of graphs and conjecture the upper and lower bounds of the RW index.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01944246
Contributor : Bernard Fortz <>
Submitted on : Tuesday, December 4, 2018 - 2:59:52 PM
Last modification on : Friday, March 22, 2019 - 1:37:13 AM

File

RWIndex_JMC_revised.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01944246, version 1

Données associées

Collections

Citation

Eglantine Camby, Gilles Caporossi, Marcia Paiva, Marcelo Eduardo Vieira Segatto. Expected distance based on random walks. Journal of Mathematical Chemistry, Springer Verlag (Germany), 2018, 56 (2), pp.618-629. ⟨hal-01944246⟩

Share

Metrics

Record views

61

Files downloads

129