Studying new classes of graph metrics

Abstract

In data analysis, there is a strong demand for graph metrics that differ from the classical shortest path and resistance distances. Recently, several new classes of graph metrics have been proposed. This paper presents some of them featuring the cutpoint additive distances. These include the path distances, the reliability distance, the walk distances, and the logarithmic forest distances among others. We discuss a number of connections between these and other distances.

Prepared for the Proceedings of GSI2013 - Geometric Science of Information (August 28-30, 2013, Paris). 9 pages, 1 figure

References in corpus (4)

• Developments in the theory of randomized shortest paths with a comparison of graph node distances
• Simple expressions for the long walk distance
• A topological interpretation of the walk distances
• The Sum-over-Forests density index: identifying dense regions in a graph

Cited by in corpus (8)

• A bag-of-paths framework for network data analysis
• Similarities on Graphs: Kernels versus Proximity Measures
• Randomized Shortest Paths with Net Flows and Capacity Constraints
• Hitting Time Quasi-metric and Its Forest Representation
• Covariance and Correlation Kernels on a Graph in the Generalized Bag-of-Paths Formalism
• Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization
• Dissecting graph measure performance for node clustering in LFR parameter space
• How to choose the most appropriate centrality measure? A decision tree approach