Link Prediction Based On Complex Network Structure

In recent years,complex network analysis has become a popular research topic with the rising interdisciplinary research of statistics,physics,sociology and computer science.One of the most interesting orient in complex network analysis is link prediction.The purpose of link prediction is to infer the existence of new relationships or still unknown interactions between pairs of nodes based on network properties.Such technique has been successfully applied to various practical fields,which includes inferring information cascading and providing social recommendation service.In theoretical fields,it can be used to model network evolution mechanisms and learn network representation.With the increasing expansion of network scale,the evolving network and its structure is becoming more and more complicated.Such complexity and heterogeneity greatly reduce the effectiveness of the current link prediction algorithms.So the difficulties and focus for recent algorithms lie in the fact that how to effectively ultilize the complex network structure for link prediction.In addition,with the development of machine learning and data mining techiniques,how to learn the complex network structures also has attracted more and more attention.In this paper,we try to intensively study the link prediction algorithm based on the complex network structure and mainly focus on the na?ve Bayes model,the stochastic block model and the transfer learning techiniques.In summary,we made the following major contributions:(1)A recent proposed link prediction algorithm based on local naive Bayesian(LNB)probability model can simply and effectively measure the contribution of different common neighbors to potential node pairs.However,LNB assumes that each common neighbor has produce a sole effect on the potential link formation and does not reflect the graphical structure of network.Aiming at this problem,a probabilistic Tree Argumented Naive Bayes link prediction algorithm(TAN)is proposed.TAN uses mutual information to measure the potential correlation between common neighbors and effectively solves the independent assumption.The experimental results in artificial networks and real world networks prove the superiority of the proposed algorithm comparing with the baselines.(2)In weighted network,the weighted format of similarity metrics based on local structure are widely used to deal with weighted network link prediction tasks.However,such metrics ignore the different effects of common neighbors and the weighting values associated with links in such local structures.In this paper,we introduce the concept of weighted clustering coefficients to extend the unweigthed naive Bayes link prediction algorithm to the application scenario of weighted complex networks.A large number of experiments on real weight networks proves the effectiveness of our proposed algorithm.(3)Link predictors based on local structure calculate similarity of all possible links in the network.There is no distinction between whether the link is in the same community or between different communities.And it also did not distinguish the place of common neighbors under different communities which influence the formulation of potential node pair.In this article,we propose a community-based algorithm which differentiae potential links and common neighbor's contribution in different view.Firstly,the algorithm divides the links into intraLinks and interLinks for similarity calculation,and then puts forward the concept of community participation and link degree of common neighbors.Experimental evaluation show that our proposed algorithm can effectively improve the predictive performance and can be extended to the local CN and Jaccard metric.(4)In social networks,the communities represents clusters,whose relationships between nodes within the same community are intensive and the links among communities are sparse.In this paper,to solve the shortcomings of current community-based or block-based prediction methods,we propose a link prediction algorithm called MMLP.MMLP maximizes the modularity in a balanced situation by drawing on the classical stochastic block model and social circle discovery algorithm.It first constructs a probabilistic generation process which emphasizes the interLinks.And then it effectively uses the modularity definition to explain the correlation between link prediction and community detection,while associating the integration features and links to learn the weights of different fratures in different communities.A large number of experiments on both synthetic and real network show that MMLP can achieved better results against other baseline methods.(5)The disadvantage of link prediction algorithm for multi-relational heterogeneous networks lies in the explicit use of correlations between dimensions.It means the addition of the probability related to the dimension is directly based on the original homogeneous algorithm,and does not dig deeper into the latent correlation among dimensions.Furthemore,the various features used to calculate the similarity are based on the local structure or the path structure,which are usually domain-related and not general.In order to overcome these shortcomings,this paper propose a community-level algorithm called ITLP for knowledge transfer.More detail,we use the knowledge of the transfer learning on the basis of MMLP to help the prediction of the target dimension sub-network.ITLP not only retains the features of MMLP's relationship between mining community change and link generation,but also extends effectively to multi-relational network link prediction through the idea of transfer learning.Experiments on real multi-relational datasets show the robustness of ITLP.(6)Many similarity-based algorithms ultilize the different weights of common neighbors for link prediction.Nevertheless,these algorithms are usually not capable of incorporating both the macro(global)and micro(local)network characteristics into a unified metric.In addition,even if some of them can integrate all the above characteristics,they are still inefficient,and can not be extended to larger scale dense networks.In order to overcome these shortcomings,a link prediction algorithm based on global influence node identification technique is proposed.This algorithm defines the contribution of different common-neighbors by introducing the ranking score of influential nodes,which effectively integrates the influence of local and global structure.A large number of experiments in unweighted and weighted networks verify that our proposed algorithm can quickly and accurately handle the task of link prediction with largescale dense networks.