A Topological Interpretation of the Walk Distances

Pavel Chebotarev () and Michel Deza ()
Additional contact information
Pavel Chebotarev: Institute of Control Sciences of the Russian Academy of Sciences
Michel Deza: LIGA, Ecole Normale Superieure, Laboratoire de Geometrie Appliquee

Chapter Chapter 7 in Distance Geometry, 2013, pp 121-135 from Springer

Abstract: Abstract The walk distances in graphs have no direct interpretation in terms of walk weights, since they are introduced via the logarithmsof walk weights. Only in the limiting cases where the logarithms vanish such representations follow straightforwardly. The interpretation proposed in this chapter rests on the identity $$\ln \det B = tr \ln B$$ applied to the cofactors of the matrix $$I - tA,$$ where Ais the weighted adjacency matrix of a weighted multigraph and tis a sufficiently small positive parameter. In addition, this interpretation is based on the power series expansion of the logarithm of a matrix. Kasteleyn (Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics. Academic Press, London, 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.

Keywords: Graph distances; Walk distances; Transitional measure; Network (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-5128-0_7

Ordering information: This item can be ordered from
http://www.springer.com/9781461451280

DOI: 10.1007/978-1-4614-5128-0_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().