Research of Motif-Based Similarity for Link Prediction Problem

Abstract

The link prediction problem in the network concerns to predict the existence of links between node pairs, which is a research hotspot in different scenarios with network applications. Methods of predicting links based on network topology and structures provide a number of measurements to reveal the underlying relationship between two nodes. In this paper, a motif-based similarity index for link prediction is proposed to calculate the similarity score of two nodes concerning their local environment, which takes advantage of existing similarity definitions and the motifs. This motif-based similarity can be generalized to more complicated cases by considering different motifs and keeps the same level of computational complexity with the existing indexes. Experimental results on 9 public benchmark datasets and 1 randomly generated dataset show the effectiveness of our proposed index, and accuracies on several datasets are significantly improved. The performance of motif-based similarity suggests that considering typical motifs on networks could improve the precisions of link prediction tasks, and exploring specific structure characteristics on networks will point out an important and effective direction for more research with network methods applied.

Keywords

• Link prediction
• similarity score
• motif
• high-order structure