A class of graph-geodetic distances generalizing the shortest-path and the resistance distances
A new class of distances for graph vertices is proposed. This class contains parametric families of distances which reduce to the shortest-path, weighted shortest-path, and the resistance distances at the limiting values of the family parameters. The main property of the class is that all distances it comprises are graph-geodetic: d(i,j)+d(j,k)=d(i,k) d ( i , j ) + d ( j , k ) = d ( i , k ) if and only if every path from i i to k k passes through j j . The construction of the class is based on the matrix forest theorem and the transition inequality.
resistance distance matrix forest theorem shortest path distance forest distance spanning rooted forest transitional measure graph bottleneck identity regularized laplacian kernel