A class of graph-geodetic distances generalizing the shortest-path and the resistance distances

DOI10.1016/j.dam.2010.11.017zbMath1209.05068arXiv0810.2717MaRDI QIDQ628311

Pavel Yu. Chebotarev

Publication date: 10 March 2011

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

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

zbMATH Keywords

resistance distance; shortest path distance; transitional measure; forest distance; graph bottleneck identity; matrix forest theorem; regularized Laplacian kernel; spanning rooted forest

Mathematics Subject Classification ID

05C38: Paths and cycles

05C12: Distance in graphs

Related Items

Effective Resistance Preserving Directed Graph Symmetrization, Nonlocal pagerank, Refinement of Metrics: Erd\H{o}s Number, a Case Study, Simple expressions for the long walk distance, Hyperspherical embedding of graphs and networks in communicability spaces, The communicability distance in graphs, The walk distances in graphs, An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification, The graph bottleneck identity, The Smith normal form of product distance matrices, Interpolating between random walks and optimal transportation routes: flow with multiple sources and targets, Developments in the theory of randomized shortest paths with a comparison of graph node distances, Sparse randomized shortest paths routing with Tsallis divergence regularization, A simple extension of the bag-of-paths model weighting path lengths by a Poisson distribution, Randomized shortest paths with net flows and capacity constraints, Metric and ultrametric inequalities for directed graphs, Semi-Lipschitz functions and machine learning for discrete dynamical systems on graphs, A bag-of-paths framework for network data analysis, Tuned communicability metrics in networks. The case of alternative routes for urban traffic, Unsupervised representation learning with minimax distance measures, Learning representations from dendrograms, Similarities on graphs: kernels versus proximity measures, A recursion formula for resistance distances and its applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The graph bottleneck identity
• Resistance distance and the normalized Laplacian spectrum
• Distances and volumina for graphs
• Random walks on graphs
• The matrix-forest theorem and measuring relations in small social groups
• Forest matrices around the Laplacian matrix
• On proximity measures for graph vertices
• On the properties of von Neumann kernels for link analysis
• Spanning forests and the golden ratio
• An Electrical Lemma
• On the distance matrix of a directed graph
• Learning Theory and Kernel Machines
• Metric and ultrametric spaces of resistances
• Metric and ultrametric spaces of resistances
• Encyclopedia of Distances
• Geometry of cuts and metrics