Distributed Link Prediction in Large Scale Graphs using Apache Spark
Creators: name: Θεοδοσίου, Αναστάσιος Δημητρίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2019
Subjects: Πρόβλεψη Συνδέσμων
Μηχανική Μάθηση
Apache Spark
Link Prediction
Machine Learning

description: Social networks such as Facebook, Instagram, Twitter and LinkedIn, are widely known for their development and acceptance by users, allowing them to share digital content (links, photos, videos), expressing or sharing their opinions, and to expand their social circle by making new friends. All of these kinds of interactions that users are involved in, lead to the development and expansion of social networks over time. Social networks support users by providing them predictions for new friendship, based on their existing network, but also on their preferences resulting from their interaction with the network which they are building in stages. Link predication methods attempt to predict the possibility of a future connection between two nodes on a given network. There is a large scope of application for link prediction techniques. Some such examples are, in biological networks, in e-commerce (see Amazon), in the security domain but also in the social networks, thus providing various services to serve the users of each network. Because of the huge amount of data collected today, there is a need for some scalable approaches to the problem of link prediction. The purpose of this diploma thesis, is to experiment and use various machine learning techniques, both supervised and unsupervised, to predict links to an academic paper network using Apache Spark to handle large data volumes and Scala, as the programming language. More specifically, in the first part of the thesis, we study the prediction of links based on supervised machine learning techniques. The problem is treated as binary classification and data preprocessing techniques are implemented. These data, as mentioned above, are a collection of academic documents in CSV format. For each paper we know the following features. The title, date of publication, a list of authors, the magazine or the conference in which was published as well as the abstract of the paper. Through these features, we create new features which will be used as input data in a classifier. A total number of 7 different models were used which were evaluated at the end and a comparison was made between the different classifier. In the second half of the work, the same problem was studied from a different perspective. At this point, unsupervised machine learning techniques were used to predict new network connections, but this time we relied on the similarity and the structure of each node's data. Two different approaches were used to tackle the problem, with the first one to compare all records with all other documents, and based on a similarity threshold we had set, the predictions were resulted. The process of brute force check, was quite time consuming, although it yielded results with almost 100% of accuracy. The second technique involved the implementation of the locality sensitive hashing algorithm in conjunction with Min Hashing to predict the same links but this time based on the Jaccard distance rather than the Jaccard Index. The comparison of these two techniques showed that the second technique, although providing less accuracy, was much faster.
description: Τα κοινωνικά δίκτυα όπως το Facebook, Instagram, Twitter αλλά και το LinkedIn, γνωρίζουν μεγάλη ανάπτυξη και αποδοχή από τους χρήστες, καθώς τους δίνουν την δυνατότητα να διαμοιράζονται ψηφιακό περιεχόμενο (συνδέσμους, φωτογραφίες, βίντεο), να εκφράζουν ή να μοιράζονται την γνώμη τους και να επεκτείνουν τον κοινωνικό τους κύκλο, κάνοντας νέους φίλους. Όλα αυτά τα είδη αλληλεπιδράσεων που οι χρήστες συμμετέχουν, οδηγούν στην εξέλιξη και επέκταση των κοινωνικών δικτύων, με την πάροδο του χρόνου. Τα κοινωνικά δίκτυα, υποστηρίζουν τους χρήστες παρέχοντάς τους προτάσεις για νέους συνδέσμους φιλίας, βασισμένες στο υπάρχων δίκτυό τους αλλά και σε προτιμήσεις τους που προκύπτουν από την αλληλεπίδρασή τους με το δίκτυο που χτίζουν σταδιακά. Οι μέθοδοι πρόβλεψης συνδέσμων, προσπαθούν να προβλέψουν την πιθανότητα μιας μελλοντικής σύνδεσης μεταξύ δύο κόμβων σε ένα δεδομένο δίκτυο. Υπάρχει ένα μεγάλο πεδίο εφαρμογής των τεχνικών πρόβλεψης νέων συνδέσμων. Μερικά τέτοια παραδείγματα είναι, σε βιολογικά δίκτυα, στον ηλεκτρονικό εμπόριο (βλέπε Amazon), στην περιοχή της ασφάλειας αλλά και στα κοινωνικά δίκτυα παρέχοντας έτσι διάφορες υπηρεσίες για την εξυπηρέτηση των χρηστών του κάθε δικτύου. Λόγω του τεράστιου όγκου δεδομένων που συλλέγεται σήμερα, δημιουργείται η ανάγκη για κλιμακούμενες προσεγγίσεις στο πρόβλημα της πρόβλεψης συνδέσμων. Αντικείμενο αυτής της διπλωματικής, είναι ο πειραματισμός και η χρήση διαφόρων τεχνικών μηχανικής μάθησης, τόσο επιβλεπόμενες όσο και μη, με στόχο τη πρόβλεψη συνδέσμων σε ένα δίκτυο ακαδημαϊκών εγγράφων (paper) με την χρήση του Apache Spark για την διαχείριση του μεγάλου όγκου δεδομένων και την Scala, ως γλώσσα προγραμματισμού. Πιο συγκεκριμένα, στο πρώτο κομμάτι της εργασίας, μελετούμε την πρόβλεψη συνδέσμων βασισμένοι σε τεχνικές επιβλεπόμενης μηχανικής μάθησης. Το πρόβλημα αντιμετωπίζεται ως δυαδική ταξινόμηση και υλοποιούνται τεχνικές προ επεξεργασίας των δεδομένων. Τα δεδομένα αυτά όπως αναφέρθηκε και παραπάνω, αποτελούν μια συλλογή από ακαδημαϊκά έγγραφα σε μορφή CSV. Για κάθε κόμβο (paper) γνωρίζουμε τα εξής χαρακτηριστικά. Τον τίτλο, την ημερομηνία δημοσίευσης, μια λίστα με τους συγγραφής, το περιοδικό η συνέδριο που δημοσιεύθηκε καθώς και την περίληψη του εγγράφου. Μέσω αυτών των χαρακτηριστικών, δημιουργούμε τα features προ πρόκειται αν χρησιμοποιηθούν ως δεδομένα εισόδου, σε έναν classifier. Χρησιμοποιήθηκαν στο σύνολο 7 διαφορετικά μοντέλα τα οποία αξιολογήθηκαν στο τέλος και πραγματοποιήθηκε μια σύγκριση μεταξύ των διαφόρων classifier. Στο δεύτερο μισό της εργασίας, μελετήθηκε το ίδιο πρόβλημα από μια διαφορετική σκοπιά. Σε αυτό το σημείο χρησιμοποιήθηκαν τεχνικές μη επιβλεπόμενης μηχανικής μάθησης για την πρόβλεψη νέων συνδέσεων στον δίκτυο προς εξέταση αλλά αυτή την φορά βασιστήκαμε στην ομοιότητα και την δομή των δεδομένων του κάθε κόμβου. Χρησιμοποιήθηκαν δύο διαφορετικές προσεγγίσεις στην αντιμετώπιση του προβλήματος, με την πρώτη να αφορά την σύγκριση όλο των εγγραφών με όλα τα άλλα έγγραφα και βασιζόμενοι σε ένα όριο ομοιότητας που θέσαμε, έγινε η πρόβλεψη των συνέσεων. Η διαδικασία του brute force ελέγχου, ήταν αρκετά χρονοβόρα παρόλο που παρείχε αποτελέσματα με σχεδόν 100% ακρίβεια. Η δεύτερη τεχνική αφορούσε την εφαρμογή του αλγορίθμου locality sensitive hashing σε συνδυασμό με το Min Hashing για την πρόβλεψη των ίδιων συνέσεων αλλά αυτή την φορά με βάση το Jaccard distance και όχι το Jaccard Index. Η σύγκριση αυτών των δύο τεχνικών έδειξε πως η δεύτερη τεχνική παρόλο που παρείχε μικρότερη ακρίβεια αποτελεσμάτων, ήταν αρκετά πιο γρήγορη.