Similarities on graphs: Kernels versus proximity measures

2018/02/17 by Konstantin Avrachenkov, Pavel Chebotarev, Dmytro Rubanov · 24 citations
Computer Science · Mathematics · Physics and Astronomy · #Artificial intelligence #Bayesian Modeling and Causal Inference #Combinatorics #Complex Network Analysis Techniques #Computer science #Mathematics #Opinion Dynamics and Social Influence #Similarity (geometry) #math.CO #math.MG #msc:05C12 #msc:05C50 #msc:91C20

paper · pdf · doi:10.1016/j.ejc.2018.02.002

published in European Journal of Combinatorics 80, 47-56 (Elsevier BV) · 16 pages

arxiv created 2018/02/17 · openalex publication_date 2018/02/23 · arxiv updated 2018/08/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We analytically study proximity and distance properties of various kernels and similarity measures on graphs. This helps to understand the mathematical nature of such measures and can potentially be useful for recommending the adoption of specific similarity measures in data analysis.

Citations

• Spectral graph theory [CBMS Conference on Recent Advances in Spectral Graph Theory held at California State University at Fresno, June 6 - 10. 1994]
• Kernels and Regularization on Graphs
• Metric spaces and positive definite functions
• A New Status Index Derived from Sociometric Analysis
• Remarks to Maurice Frechet's Article ``Sur La Definition Axiomatique D'Une Classe D'Espace Distances Vectoriellement Applicable Sur L'Espace De Hilbert
• Do logarithmic proximity measures outperform plain ones in graph\n clustering?