The graph bottleneck identity

DOI10.1016/j.aam.2010.11.001zbMath1232.05064arXiv1003.3904OpenAlexW1626832437MaRDI QIDQ719327

Pavel Yu. Chebotarev

Publication date: 10 October 2011

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

vertexgraph distancestransitional measuregraph bottleneck identitymatrix forest theoremregularized Laplacian kernelspanning converging forestvertex proximity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20)

Related Items (8)

Simple expressions for the long walk distance ⋮ A class of graph-geodetic distances generalizing the shortest-path and the resistance distances ⋮ The walk distances in graphs ⋮ The Smith normal form of product distance matrices ⋮ Protometrics ⋮ Similarities on graphs: kernels versus proximity measures ⋮ Nonlocal pagerank ⋮ Semi-supervised learning with regularized Laplacian

Cites Work

• Matroids and linking systems
• A class of graph-geodetic distances generalizing the shortest-path and the resistance distances
• A matrix-based measure of inter-node walk relatedness in a network
• Distances and volumina for graphs
• The matrix-forest theorem and measuring relations in small social groups
• Forest matrices around the Laplacian matrix
• On proximity measures for graph vertices
• Spanning forests and the golden ratio
• Modern multidimensional scaling. Theory and applications.
• On the distance matrix of a directed graph
• Learning Theory and Kernel Machines
• Self-Avoiding Paths and the Adjacency Matrix of a Graph
• Geometry of cuts and metrics
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The graph bottleneck identity