Link Prediction in Social Networks

Abstract

In a social network there can be many different kind of links or edges between the nodes. Those could for example be social contacts, hyper-references or phone calls. Link Prediction is the problem of predicting edges that either don't yet exist at the given time t or exist, but have not been discovered, are likely to occur in the near future. We develop approaches to link prediction based on measures for analysing the proximity of nodes in a network. Consider a co-authorship network among scientists, e.g. two scientists who are close in the network will have colleagues in common, so they are more likely to collaborate in the near future. Our goal is to make this intuitive notion precise and to understand which measures of proximity in a network lead to the most accurate link predictions. Link prediction algorithms can be classified into three categories: Node neighbourhood approaches, Path based approaches and Meta approaches. Node neighbourhood approach is based on local features of a network, focusing mainly on the nodes structure(i.e. based on the number of common friends that two users share). The local-based measures are: Common Neighbors, Jaccards coefficient, Adamic/Adar and Preferential Attachment. Path based algorithms considers the ensemble of all paths between two nodes. The Path based algorithms are: Katz, Sim-Rank, Hitting Time and Commute Time, Rooted PageRank, PropFlow and High-Performance Link Prediction. Meta-Approaches alter the data before being passed to one of the path based approaches. The algorithms are: Low-rank approximation, Unseen bigrams and Clustering.