Distributed Link Prediction in Large Scale Graphs using Apache Spark
Αναστάσιος Δημητρίου Θεοδοσίου · Aristotle University of Thessaloniki · 2019
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.