A topological interpretation of the walk distances

DOI10.1007/978-1-4614-5128-0_7MaRDI QIDQ2841702zbMATH OpenOpenAlexFDO

Authors Pavel Chebotarev, Michel Deza

Publication date 29 July 2013

Published in Distance Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.0284

zbMATH Keywords

networkgraph distanceswalk distancestransitional measure

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12) Random walks on graphs (05C81)

Abstract: The walk distances in graphs have no direct interpretation in terms of walk weights, since they are introduced via the emph{logarithms} of walk weights. Only in the limiting cases where the logarithms vanish such representations follow straightforwardly. The interpretation proposed in this paper rests on the identity $lndetB=rlnB$ applied to the cofactors of the matrix $I-tA,$ where $A$ is the weighted adjacency matrix of a weighted multigraph and $t$ is a sufficiently small positive parameter. In addition, this interpretation is based on the power series expansion of the logarithm of a matrix. Kasteleyn (1967) was probably the first to apply the foregoing approach to expanding the determinant of $I-A$. We show that using a certain linear transformation the same approach can be extended to the cofactors of $I-tA,$ which provides a topological interpretation of the walk distances.

Recommendations

• The walk distances in graphs
• Simple expressions for the long walk distance
• Walks: a beginner's guide to graphs and matrices
• The forest metrics of a graph and their properties
• Determinant of the distance matrix of a tree with matrix weights

Cited in

(4)

• scientific article; zbMATH DE number 7650283 (Why is no real title available?)
• An Experimental Study and Comparison of Topological Peeling and Topological Walk
• Simple expressions for the long walk distance
• The walk distances in graphs

Describes a project that uses

Uses Software

• WordNet

This page was built for publication: A topological interpretation of the walk distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2841702)