A topological interpretation of the walk distances

DOI10.1007/978-1-4614-5128-0_7zbMATH Open1269.05028arXiv1111.0284OpenAlexW3105535377MaRDI QIDQ2841702FDOQ2841702

Authors: Pavel Chebotarev, Michel Deza 

Publication date: 29 July 2013

Published in: Distance Geometry (Search for Journal in Brave)

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.

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

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

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)

Cited In (4)

• Title not available (Why is that?)
• An Experimental Study and Comparison of Topological Peeling and Topological Walk
• Simple expressions for the long walk distance
• The walk distances in graphs

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)