Link prediction in networks based on LSH
Creators: name: Λαγιόκαπα, Νίκη Κωνσταντίνου
Publisher: name: Aristotle University of Thessaloniki
Year: 2024
Subjects: Γράφοι
Ομοιότητα κόμβων
Πιθανότητα σύνδεσης όμοιων κόμβων
LSH
MinHash
Link Prediction

description: This thesis explores advanced techniques for analyzing and predicting relationships within complex networks, focusing on methods like MinHash for similarity estimation and common neighbors for link prediction. It compares the output of MinHash with more traditional approaches, such as Jaccard similarity, and investigates the differences between sets derived from biased and unbiased random walks. Additionally, it examines the likelihood that two nodes sharing the same influence are related, providing insights into the average percentage of such connections. A key aspect of this research is the implementation of random walks, which are used to identify the most influential nodes by exploring the graph’s data and leveraging its structure. By performing LSH on the output of these random walks, the most similar nodes can be identified based on their influence. Link prediction is then specifically applied to the LSH buckets to estimate the percentage of connections among the most similar nodes, based on their influence. The research delves into the strengths and challenges of these approaches, particularly across varying graph sizes where computational efficiency and accuracy are crucial. A significant focus is placed on fine-tuning thresholds and parameters within the algorithms, including finding the right balance for the LSH threshold, and evaluating how these settings impact link prediction performance and LSH classification. The findings emphasize the importance of balancing computational trade-offs, such as accuracy versus processing time, and provide practical insights for enhancing graph analysis techniques across various domains. This work not only offers a comprehensive analysis of current methodologies but also paves the way for future advancements in network science.
description: Αυτή η διπλωµατιϰή εργασία εξετάζει προηγµένες τεχνιϰές για την ανάλυση ϰαι την πρόβλεψη σχέσεων µέσα σε πολύπλοϰα δίϰτυα, εστιάζοντας σε µεϑόδους όπως την τεχνιϰή MinHash για την εϰτίµηση οµοιότητας ϰαι την τεχνιϰή Common Neighbors για την πρόβλεψη συνδέσµων. Συγϰρίνει τα αποτελέσµατα του MinHash µε πιο παραδοσιαϰές προσεγγίσεις, όπως η οµοιότητα Jaccard, ϰαι διερευνά τις διαφορές µεταξύ συνόλων που προϰύπτουν από προϰατειληµµένους ϰαι µη προϰατειληµµένους Random Walks. Επιπλέον, εξετάζει την πιϑανότητα δύο ϰόµβοι που µοιράζονται την ίδια επιρροή να συνδέονται, παρέχοντας πληροφορίες σχετιϰά µε το µέσο ποσοστό τέτοιων συνδέσεων. ΄Ενα βασιϰό στοιχείο αυτής της έρευνας είναι η εφαρµογή τυχαίων περιπάτων (RW), οι οποίοι χρησιµοποιούνται για τον εντοπισµό των πιο επιδραστιϰών ϰόµβων µέσω της εξερεύνησης των δεδοµένων του γράφου ϰαι της αξιοποίησης της δοµής του. Με την εϰτέλεση LSH στα αποτελέσµατα αυτών των τυχαίων περιπάτων, οι πιο παρόµοιοι ϰόµβοι µπορούν να εντοπιστούν βάσει της επιρροής τους. Στη συνέχεια, η πρόβλεψη συνδέσµων εφαρµόζεται ειδιϰά στους ϰάδους του LSH για να εϰτιµηϑεί το ποσοστό συνδέσεων µεταξύ των πιο παρόµοιων ϰόµβων βάσει της επιρροής τους. Η έρευνα διερευνά τα πλεονεϰτήµατα ϰαι τις προϰλήσεις αυτών των προσεγγίσεων, ιδιαίτερα σε διαφορετιϰά µεγέϑη γραφηµάτων όπου η υπολογιστιϰή αποδοτιϰότητα ϰαι η αϰρίβεια είναι ϰρίσιµες. Ιδιαίτερη έµφαση δίνεται στην προσαρµογή των ϰατωφλίων ϰαι των παραµέτρων µέσα στους αλγορίϑµους, συµπεριλαµβανοµένης της εξεύρεσης της σωστής ισορροπίας για το ϰατώφλι του LSH, ϰαι στην αξιολόγηση του τρόπου µε τον οποίο αυτές οι ρυϑµίσεις επηρεάζουν την απόδοση της πρόβλεψης συνδέσµων ϰαι της ταξινόµησης LSH. Τα ευρήµατα υπογραµµίζουν τη σηµασία της εξισορρόπησης των υπολογιστιϰών ανταλλαγµάτων, όπως η αϰρίβεια έναντι του χρόνου επεξεργασίας, ϰαι παρέχουν πραϰτιϰές πληροφορίες για τη βελτίωση των τεχνιϰών ανάλυσης γραφηµάτων σε διάφορους τοµείς. Αυτή η εργασία όχι µόνο προσφέρει µια ολοϰληρωµένη ανάλυση των τρεχουσών µεϑοδολογιών, αλλά ϰαι ανοίγει τον δρόµο για µελλοντιϰές εξελίξεις στην επιστήµη των διϰτύων..