Link prediction in graphs using simhash
Creators: name: Κοσμάνος, Κλέαρχος Βάιου
Publisher: name: Aristotle University of Thessaloniki
Year: 2024
Subjects: Πρόβλεψη ακμών
Γράφος
Simhash
Link prediction
Graph

description: Link Prediction is a fundamental problem in network analysis, which aim is given the current snapshot of a graph, to estimate the likelihood of the existence of an edge, in a future status of the graph. From that perspective, existing work that includes methods like Common Neighbors, Jaccard Coefficient and Adamic-Adar is compared with a variant of methods based on simhash techniques. In more details, three different simhash approaches are employed that differ on the features of the graphs that are used in order to calculate a signature for each node that finally will be used to compare the similarity between different nodes. The comparison is done both in non-attributed graphs and attributed graphs that have additional features in their nodes. Different simhash variants use information of the neighborhood of each node to generate each signature. The difference is in the way that this information is gathered. Direct neighbor list of each node, or either paths from random walks executed may be used to create a set of final nodes that will affect the calculation of signatures. Furthermore, in case of attributed graphs, the additional information should be used to further enhance the information contained in signatures and thus evaluation metrics. A series of real-world graphs were used to conduct extensive experiments in order to fine-tune simhash approaches and then compare their results with baseline methods, before concluding in which cases simhash outperforms existing.
description: Η πρόβλεψη ακμών είναι ένα χαρακτηριστικό πρόβλημα στην ανάλυση δικτύων. Ο στόχος του είναι, δεδομένου ενός στιγμιότυπου ενός γραφήματος, η εκτίμηση της πιθανότητας ύπαρξης μιας ακμής σε μια μελλοντική κατάσταση του γραφήματος. Υπάρχουσες μέθοδοι και μετρικές, που περιλαμβάνουν τους Common Neighbors, Jaccard Coefficient και Adamic-Adar συγκρίνονται με τεχνικές που έχουν ως βάση το simhash. Πιο συγκεκριμένα, τρεις διαφορετικές προσεγγίσεις με simhash χρησιμοποιούνται, οι οποίες διαφέρουν στα χαρακτηριστικά του γραφήματος που περιλαμβάνει η κάθε μία, ώστε να υπολογίσουν μια υπογραφή για κάθε κόμβο. Αυτή η υπογραφή των κόμβων τελικά θα χρησιμοποιηθεί για να συγκριθεί η ομοιότητα μεταξύ διαφορετικών κόμβων. Η σύγκριση γίνεται τόσο σε απλά γραφήματα, όσο και σε γραφήματα που εμφανίζουν επιπλέον χαρακτηριστικά στους κόμβους τους (attributed graphs). Η διαφορών μεταξύ των διαφορετικών τεχνικών simhash βρίσκεται στον τρόπο που συγκεντρώνουν πληροφορία από τη γειτονία του κάθε κόμβου, ώστε να υπολογιστεί η υπογραφή του. Ο υπολογισμός γίνεται με βάση ενός συνόλου άλλων κόμβων που είτε υπολογίζεται ως απλά η λίστα των άμεσα γειτονικών κόμβων του, είτε πραγματοποιούνται τυχαίοι περίπατοι για τη συλλογή τους. Επιπλέον, στις περιπτώσεις των attributed graphs, η πρόσθετη πληροφορία των χαρακτηριστικών των κόμβων χρησιμοποιείται για την ενίσχυση της πληροφορίας που περιέχετε στην υπογραφή, προσφέροντας περαιτέρω βελτίωση στις μετρικές αξιολόγησης. Μια σειρά από αληθινά γραφήματα χρησιμοποιήθηκε για την εκτενή διεξαγωγή πειραμάτων με σκοπό τη βελτιστοποίηση των παραμέτρων της κάθε τεχνικής που βασίζεται σε simhash. Τέλος, έγινε και η σύγκριση των αποτελεσμάτων τους και με τις βασικές υπάρχουσες μεθόδους που αναφέρθηκαν, ώστε να διαπιστώσουμε υπό ποιες συνθήκες οι τεχνικές του simhash υπερτερούν σε απόδοση.