Link Prediction Based on Community Information and Its Parallelization

Link prediction refers to predicting the likelihood of the existence of an unknown link or a future link based on the observed information. It plays an important role in complex network analysis. Classical similarity indices based on common neighbor nodes consider that each common neighbor has the same effect to the link likelihood. However, in real networks, the contribution of common neighbor nodes belonging to different communities may be different. This paper proposes a new link prediction algorithm with an adjustable parameter based on community information (CI). Applying the proposed algorithm to nine similarity indices, a family of CI-based indices, referred to as CI forms, is proposed. We empirically investigate the impact of the CI on the accuracy of link prediction with nine classical indices. The experiments on ten real-world networks show that, compared with tradition local indices, the proposed CI forms have better overall prediction performance. Furthermore, a parallelization algorithm is developed to apply the proposed CI-based link prediction algorithm to large-scale complex networks using Spark GraphX. The experiment results show that the proposed parallel algorithm significantly improves the computing efficiency of link prediction.