Research Of Link Prediction Methods For Complex Networks

Many complex systems in the real world can be modeled as complex networks.The study of complex networks can help us understand the nature of real systems more clearly.Nowadays,the development of the Internet and communication technology has made the sharing of data more convenient.The improvement of data acquisition,storage and computing capabilities has strongly promoted the progress of complex network analysis.Link prediction,as a main research direction in complex network analysis,aims to infer missing or possible links in a network based on the observable node attributes and network structures.Because of its important practical and theoretical values,link prediction has attracted the growing attention of researchers.Most of the existing researches on link prediction focused on single-layer networks.In recent years,some researchers began to study the link prediction problem of multiplex networks.Because they contains more rich contents,link prediction in multiplex networks can help us mine more valuable information.In this thesis,we study the problem in both single-layer and multiplex networks and propose four link prediction methods.(1)Link prediction method based on correlation of nodes' connecting patterns.The farther the distance between nodes in the network,the weaker the relationship between them.According to this characteristic,the nodes' connection patterns are defined,and the correlation of nodes' connection patterns(CNCP)is calculated by Pearson coefficient.Then,a series of link prediction methods based on CNCP are obtained by combining CNCP with baseline similarity indexes.Experiments on 6 real networks show that the proposed methods are superior to the baseline similarity methods.(2)Link prediction method based on endpoint applicability.To combine more structure or attribute information in link prediction,this method selects the suitable similarity index for each node from a set of given similarity indexes.For a target node pair,the most suitable similarity index of each endpoint is used to calculate the connection probability of the target node pair.Finally,the two connection probabilities are combined to get the final similarity score.Experiments on 9 real networks show that the proposed method has a very outstanding performance in disassortative networks.(3)Supervised link prediction method in multiplex networks.In this method,link prediction is regarded as a binary classification problem of node pairs.In order to construct the feature vectors of node pairs,this method extracts topology information from all layers of the network.Besides adopting a group of classical similarity indexes,such as CN,RA,and JC,we also design two new features,namely friendship of neighbors(FoN)and friendship in auxiliary layers(FAL),for node pairs.Based on these features,classification models are trained and evaluated on 6 different multiplex networks.Experiments show that the prediction performance of this method is better than the compared methods.(4)Multiplex network link prediction method based on regression and conditional probability.This method combines both intralayer and interlayer information to predict missing links in multiplex networks.First,the intralayer probability is calculated by using regression algorithm based on intralayer information.Then,the conditional probability of link existence is calculated by using the auxiliary layer information.Finally,both probabilities are combined to predict links.The experimental results on 8 real networks demonstrate that the prediction performance of this method is better than that of the compared methods.