A scalable method for link prediction in large real world networks

Link prediction has become an important task, especially with the rise of large-scale, complex and dynamic networks. The emerging research area of network dynamics and evolution is directly related to predicting new interactions between objects, a possibility in the near future. Recent studies show that the precision of link prediction can be improved to a great extent by including community information in the prediction methods. As traditional community-based link prediction algorithms can run only on stand-alone computers, they are not well suited for most of the large networks. Graph parallelization can be one solution to such problems. Bulk Synchronous Parallel (BSP) programming model is a recently emerged framework for parallelizing graph algorithms. In this paper, we propose a hybrid similarity measure for link prediction in real world networks. We also propose a scalable method for community structure-based link prediction on large networks. This method uses a parallel label propagation algorithm for community detection and a parallel community information-based Adamic-Adar measure for link prediction. We have developed these algorithms using Bulk Synchronous Parallel programming model and tested them with large networks of various domains.