Efficient Graph Similarity Assessment Method Based on Vectors of Topological Indices
Match Communications in Mathematical and in Computer Chemistry · 16.03.2026 · 1 (97) · 5
DOI: 10.46793/match.97-1.01926 ↗Kurz gefasst
Fachartikel in der Zeitschrift Match Communications in Mathematical and in Computer Chemistry, online erschienen am 16.03.2026. Verfasst von Matthias Dehmer und 3 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: The Slovenian Research and Innovation Agency.
Abstract (Originalsprache)
Measuring similarity between complex objects is a fundamental task in many scientific fields. When objects are represented as graphs, graph similarity/distance measures offer a powerful framework for quantifying structural resemblance. Those comparative measures play a key role in domains such as network science, chemoinformatics, and social network analysis. While methods like graph edit distance and graph kernels are widely used, they can be computationally intensive or fail to capture fine structural variations, since they require graphs without any structural uncertainty. Another class of methods is based on using topological indices to encode structural information of the graphs, followed by the application of distance or similarity measures for real numbers to obtain corresponding graph-level metrics. In this paper, we introduce a novel class of distance/similarity measures which are based on multiple topological indices. In many cases, they can be computed in polynomial time, which makes our method computationally efficient in practice. We demonstrate its effectiveness through comparisons and show that it captures subtle structural information meaningfully. Additionally, we explore its applicability in two domains: analyzing random graph models in network theory and assessing molecular similarity among isomers in chemoinformatics. These preliminary results suggest that our approach holds promise for graph comparison across disciplines.
Förderung
- The Slovenian Research and Innovation Agency
Zitieren
APA
Dehmer, M., Redžepović, I., Tratnik, N., & Pleteršek, P. Ž. (2026). Efficient Graph Similarity Assessment Method Based on Vectors of Topological Indices. Match Communications in Mathematical and in Computer Chemistry, 1(97), 5. https://doi.org/10.46793/match.97-1.01926
Vancouver
Dehmer M, Redžepović I, Tratnik N, Pleteršek PŽ. Efficient Graph Similarity Assessment Method Based on Vectors of Topological Indices. Match Communications in Mathematical and in Computer Chemistry. 2026;1(97):5. doi:10.46793/match.97-1.01926
BibTeX
@article{Dehmer2026,
author = {Dehmer, Matthias and Redžepović, Izudin and Tratnik, Niko and Pleteršek, Petra Žigert},
title = {Efficient Graph Similarity Assessment Method Based on Vectors of Topological Indices},
journal = {Match Communications in Mathematical and in Computer Chemistry},
year = {2026},
volume = {1},
number = {97},
pages = {5},
doi = {10.46793/match.97-1.01926}
}
EUVIMED