Studying new classes of graph metrics
arXiv:1305.7514 · doi:10.1007/978-3-642-40020-9_21
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.
arXiv commentPrepared for the Proceedings of GSI2013 - Geometric Science of Information (August 28-30, 2013, Paris). 9 pages, 1 figure
References in corpus (8)
- Developments in the theory of randomized shortest paths with a comparison of graph node distances
- A Class of Graph-Geodetic Distances Generalizing the Shortest-Path and the Resistance Distances
- Spanning Forests and the Golden Ratio
- The Walk Distances in Graphs
- The graph bottleneck identity
- 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