Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/E8A3E3FF-49EB-40C9-B34B-7F8BAFD5138A | - |
| Αναγνωριστικό | https://doi.org/10.26233/heallink.tuc.95673 | - |
| Γλώσσα | en | - |
| Μέγεθος | 63 pages | en |
| Μέγεθος | 1.2 megabytes | en |
| Τίτλος | Graph alignment algorithms | en |
| Τίτλος | Aλγόριθμoι αντιστοίχισης γράφων | el |
| Δημιουργός | Papamanolis Anastasios | en |
| Δημιουργός | Παπαμανωλης Αναστασιος | el |
| Συντελεστής [Επιβλέπων Καθηγητής] | Liavas Athanasios | en |
| Συντελεστής [Επιβλέπων Καθηγητής] | Λιαβας Αθανασιος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Karystinos Georgios | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Καρυστινος Γεωργιος | el |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Zervakis Michail | en |
| Συντελεστής [Μέλος Εξεταστικής Επιτροπής] | Ζερβακης Μιχαηλ | el |
| Εκδότης | Πολυτεχνείο Κρήτης | el |
| Εκδότης | Technical University of Crete | en |
| Ακαδημαϊκή Μονάδα | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Ακαδημαϊκή Μονάδα | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Περίληψη | Graph alignment is a computational problem which aims to find a correspondence between vertices of graphs that minimizes their node and edge disagreements. This problem arises in many fields, such as computational biology, where finding conserved functional components between species can lead to gene-disease associations or drug discoveries, social sciences, where unveiling unique users on different platforms can remove bots, and computer vision for recognising objects. Compared with the exact graph (sub)isomorphism problem often considered in a theoretical setting, the inexact graph alignment problem is often cast as a Quadratic Assignment Problem (QAP), which has attracted significant research interest. This thesis presents a comprehensive review of the recent research activity concerning the global pairwise one-to-one alignment, detailing the methodologies and formulations of four state-of-the-art graph alignment algorithms. Specifically, Umeyama’s method solves the orthogonal relaxation of the QAP by using spectral embeddings, IsoRank applies random walks with restarts on the normalized Kronecker product graph, LowRank-Align solves a rank-k approximation of the orthogonal relaxation of the QAP using an alternating optimization framework, and CONE-Align uses embeddings obtained with the NetMF method and aligns their subspaces using a Wasserstein-Procrustes framework. To evaluate these algorithms, a standard experimental setup is adopted. A graph, G1, is aligned with a “noisy” and permuted version of itself, G2, in order to create an instance of the graph alignment problem. The noise level is the percentage of extra edges in G2 with respect to the total edges in G1. Only simple (unweighted, undirected, with no loops or multiple edges) graphs are considered. Several widely-used quality measures are used, such as the Node Correctness (NC), the Edge Correctness (EC), the Induced Conserved Structure (ICS), the Symmetric Substructure Score (S3), the Matched Neighborhood Consistency (MNC), and the wall time. The experiments suggest that CONE-Align performs well for both synthetic and real- world networks, LowRank-Align performs well in some occasions, Umeyama’s method has moderate performance, but steady over datasets, and IsoRank is the overall worst. As for the quality measures, MNC and S3 seem to be the most fair. | en |
| Τύπος | Διπλωματική Εργασία | el |
| Τύπος | Diploma Work | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2023-04-25 | - |
| Ημερομηνία Δημοσίευσης | 2023 | - |
| Θεματική Κατηγορία | Graph alignment | en |
| Θεματική Κατηγορία | Graph matching | en |
| Θεματική Κατηγορία | Graph embedding | en |
| Θεματική Κατηγορία | Spectral embedding | en |
| Θεματική Κατηγορία | Data mining | en |
| Βιβλιογραφική Αναφορά | Anastasios Papamanolis, "Graph alignment algorithms", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2023 | en |
| Βιβλιογραφική Αναφορά | Αναστάσιος Παπαμανώλης, "Aλγόριθμoι αντιστοίχισης γράφων", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2023 | el |
Copyright © DIAS 2013
