Date of Award

1-16-2020

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Convolutional Neural Network, Link Prediction, Machine Learning, PLACN, Social Network Analysis

Supervisor

Ziad Kobti

Rights

info:eu-repo/semantics/openAccess

Abstract

Link Prediction (LP) in social networks (SN) is referred to as predicting the likelihood of a link formation in SNs in the near future. There are several types of SNs that are available such as human interaction network, biological network, protein-to-protein interaction network, and so on. Earlier LP researches used heuristics methods, including Common Neighbors, Resource Allocation, and many other similarity score methods. Even though heuristics methods perform better in some types of SNs, their performance is limited in other types of SNs. Finding the best heuristics for a given type of SN is a trial and error process. Recent state-of-the-art research, WLNM and SEAL showed that with deep learning techniques and subgraphing, the heuristics selection could be automated and increase the accuracy of LP. However, WLNM and SEAL have some limitations and still having performance lack in some types of SNs. The objective of this paper is to introduce a novel framework that overcomes the limitations of state-of-the-art methods and improves the accuracy of LP over various types of social networks. We propose a Link Prediction framework called PLACN that analyzes common neighbors based subgraphs using deep learning technique to predict links. PLACN is equipped with two new algorithms that are a subgraph extraction algorithm that efficiently extracts common neighbors of targeted nodes and a proposed new node labeling algorithm based on hop number and average path weight that creates consistent node orders over subgraphs. In addition to the algorithms, we derived a formula based on network properties to find an optimal number node for a given SN. PLACN converts the LP problem into an Image Classification problem and utilizes a Convolutional Neural Network to classify the links. We tested the proposed PLACN on seven different types of real-work networks and compared the performance against heuristics, latent methods, and state-of-the-art methods. Our results show that PLACN outperformed the compared Link Prediction methods while reaching above 96% AUC in tested benchmark social networks.

Download

Share

COinS