Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Aλγόριθμoι αντιστοίχισης γράφων

Papamanolis Anastasios

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/E8A3E3FF-49EB-40C9-B34B-7F8BAFD5138A-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.95673-
Γλώσσαen-
Μέγεθος63 pagesen
Μέγεθος1.2 megabytesen
ΤίτλοςGraph alignment algorithmsen
ΤίτλοςAλγόριθμoι αντιστοίχισης γράφωνel
ΔημιουργόςPapamanolis Anastasiosen
ΔημιουργόςΠαπαμανωλης Αναστασιοςel
Συντελεστής [Επιβλέπων Καθηγητής]Liavas Athanasiosen
Συντελεστής [Επιβλέπων Καθηγητής]Λιαβας Αθανασιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Karystinos Georgiosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Καρυστινος Γεωργιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Zervakis Michailen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Ζερβακης Μιχαηλel
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Electrical and Computer Engineeringen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών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 Worken
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2023-04-25-
Ημερομηνία Δημοσίευσης2023-
Θεματική ΚατηγορίαGraph alignmenten
Θεματική ΚατηγορίαGraph matchingen
Θεματική ΚατηγορίαGraph embeddingen
Θεματική ΚατηγορίαSpectral embeddingen
Θεματική ΚατηγορίαData miningen
Βιβλιογραφική ΑναφοράAnastasios Papamanolis, "Graph alignment algorithms", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2023en
Βιβλιογραφική ΑναφοράΑναστάσιος Παπαμανώλης, "Aλγόριθμoι αντιστοίχισης γράφων", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2023el

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά