Pattern-based Link Prediction In Complex Networks

Complex network, as the fundamental network model, has been widely adopted in various scenarios in everyday life and researches. Great amount of valuable information is under exploited through kinds of strategies, among which link prediction gains the most attention. Based on the analysis of observable network, link prediction aims to build complicated mathematical model to predict the existence of missing links and future links. Undoubtedly, the employment of link prediction plays an important role in exploring the underlying mechanism of complex networks. Conventional link prediction algorithms mainly focus on the analysis of topological structure of networks to uncover the hidden information. However, most of them ignore the multidimensional attributes knowledge related to nodes or edges, which matters a lot to the forming links in complex networks. So, we try to employ the multidimensional attributes to conventional link prediction model and propose the attributed-based link prediction problem.Due to the fact that most of node pairs in complex networks are unlinked, which can't be employed by traditional learning method, we propose a link pattern mining algorithm, inspired by PU learning (Positive and Unlabeled Learning), and can extract and filter discriminative link patterns in complex networks. These link patterns present the overall factor that is closely related to the links of nodes. Then, the link pattern strength estimation algorithm is proposed based on graph aggregation and finally we present the pattern-based local random walk model for link prediction. Our proposed model differs from conventional random walk models mainly in the construction of transition matrix. We aims at personalize the matrix according to the link patterns of each edge and reallocate the closer node pairs with a generally higher transition probability.Experiments are conducted on UCI data sets, political blogs data set and Sina microblog dataset. The results demonstrate the following conclusions. (1) The proposed pattern mining algorithm can exactly extract and filter more discriminative patterns, and can undercover the hidden factors that contributes to the link formation. (2) Our proposed pattern-based link prediction model can fully take advantage of various attributes knowledge and personalize the transition matrix more accurately. (3) The results of real-world networks shows that pattern-based link prediction model performs significantly against conventional link prediction algorithms and classification-based strategies.