Leveraging Zero Tail in Neighbourhood for Link Prediction

For link prediction, Common Neighbours (CN) ranking measures allow to discover quality links between nodes in a social network, assessing the likelihood of a new link based on the neighbours frontier of the already existing nodes. A zero rank value is often given to a large number of pairs of nodes, which have no common neighbours, that instead can be potentially good candidates for a quality assessment. With the aim of improving the quality of the ranking for link prediction, in this work we propose a general technique to evaluate the likelihood of a linkage, iteratively applying a given ranking measure to the Quasi-Common Neighbours (QCN) of the node pair, i.e. iteratively considering paths between nodes, which include more than one traversing step. Experiments held on a number of datasets already accepted in literature show that QCNAA, our QCN measure derived from the well know Adamic-Adar (AA), effectively improves the quality of link prediction methods, keeping the prediction capability of the original AA measure. This approach, being general and usable with any CN measure, has many different applications, e.g. trust management, terrorism prevention, disambiguation in co-authorship networks.