EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Efficient Graph Similarity Assessment Method Based on Vectors of Topological Indices

Matthias Dehmer, Izudin Redžepović, Niko Tratnik, Petra Žigert Pleteršek

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →