Node Degree and Neighbourhood Tightness based Link Prediction in Social Networks

Abstract

Link prediction is one of the fundamental issues in social network analysis. It is a mechanism to predict the existence of unobserved links from known structural similarity metrics. Variety of link prediction techniques exist that can be broadly categorized into two classes. First, a machine learning based approach where connection prediction is transferred into a learning problem of supervised logistic regression, SVM, and random forest or non-supervised learning algorithm deploying Bayesian network. Second, adopts complex network methods to predict the connections based on nodes similarity estimated via nature of nodes and network structure. There are various relationships in social networks, forming many groups and these common neighbours have a great impact on links. In this paper, unlike traditional link prediction methods that neglect to consider aggregation degree of common neighbours, we propose an improved link prediction approach called Common Neighbour Tightness (CNT) based on local information of the nodes and neighbourhood tightness. We consider the common neighbour as a whole and weigh them with local information. Stronger the relationship means closer the common neighbour nodes are to each other. We perform experiments on a set of real datasets and compare them with traditional indicators to validate the effectiveness of our approach for link prediction in social networks.