GLOS: a global and local features oriented link prediction technique in social network

Abstract

The link prediction has attracted majority of researchers from various domains since the beginning of behavioral science. For instance, online social networks such as Twitter, LinkedIn and Facebook change rapidly as new users appear in the graph. For all these networks, the more challenging task is to find and recommend friends to the users. In case of social graph, the foremost objective of link prediction is to predict which new links are likely to be appearing from the actual state of the graph. Varieties of methods have been developed such as probabilistic, maximum likelihood and similarity-based techniques where similarity-based techniques are considered as the best prediction methods. Similarity-based methods uses a strategy, where each pair of nodes assigned a similarity score such that more similar nodes have more chances to connect in a future. Similarity estimation works on the global and local features i.e. path, random walk and neighbors. Local features are those features of node that consider at node level i.e. adjacent neighbors nodes. On the other hand, global features are those type of features that considers at graph level i.e. path between two nodes. Our hypothesis is that the combination of both local and global features is more powerful predictor for link formation. Here in this study, we have evaluated global, local and hybrid similarity measures. Moreover, we also proposed a hybrid approach GLOS. We performed experiments on five different dataset (Astor, CondMat, GrQc, HepPh and HepTh). After the result evaluation, it is found that, hybrid approach GLOS obtained the highest accuracy by 1 on all the dataset, while, global approaches could not produced lowest accuracy on all dataset. On the other hand, HP from local similarity outperformed than rest of the local and global approaches.