Covariance and Correlation Kernels on a Graph in the Generalized Bag-of-Paths Formalism
arXiv:1902.03002 · doi:10.1093/comnet/cnaa026
Abstract
This work derives closed-form expressions computing the expectation of co-presence and of number of co-occurrences of nodes on paths sampled from a network according to general path weights (a bag of paths). The underlying idea is that two nodes are considered as similar when they often appear together on (preferably short) paths of the network. The different expressions are obtained for both regular and hitting paths and serve as a basis for computing new covariance and correlation measures between nodes, which are valid positive semi-definite kernels on a graph. Experiments on semi-supervised classification problems show that the introduced similarity measures provide competitive results compared to other state-of-the-art distance and similarity measures between nodes.
References in corpus (15)
- Modularity and community structure in networks
- DeepWalk: Online Learning of Social Representations
- Vertex similarity in networks
- Communicability in complex networks
- Semantic Similarity from Natural Language and Ontology Analysis
- Forest matrices around the Laplacian matrix
- Two betweenness centrality measures based on Randomized Shortest Paths
- 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
- The Matrix-Forest Theorem and Measuring Relations in Small Social Groups
- A bag-of-paths framework for network data analysis
- The Walk Distances in Graphs
- A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs
- Studying new classes of graph metrics
- In-Network Neighborhood-Based Node Similarity Measure: A Unified Parametric Model