Research On Link Prediction Based On Topology Of Network

The complex system can be presented by the complex network in the real world.The individual presented by the node,and edges present the relationships between the nodes.People research the inherent law of real world by complex network,and get some solutions of practical problem.Link prediction is the most important research topic of the complex network,Link prediction can be used to predict the links not found at present based on the node attributes and topology of network to reveal the unfound information of network.Because of the huge practical value in different fields,it has drawn a lot of attention of scientist from different fields and become the hot research topic at present.Link prediction can be mainly divided into two methods: based on node attributes and based on topology of network.The method based on node attributes can predict the node pairs in complex network well,but it must be combined with machine learning,and has to determine the combination of different parameters for different networks in order to achieve the best results,and it is difficult to attain node attributes for many situations,in the social networks,some attributes of nodes can not be obtained and is fake,meanwhile,Ensuring the attributes which are help to link prediction is very different.The method based on the topology of network is easy by comparison,the information of topology are also easy to attain,and the algorithms of link prediction based on topology can be applied universal.In the second chapter,third chapter and fourth chapter of his letter,we focus on the link prediction algorithms based on the topology of network.The main algorithms based on topology of network include CN、AA、RA 、LP and so on.The Katz index consider all paths between nodes,in the real network,there existent many information in the paths whose steps more than two.In real network,the paths more than two steps contain a lot of information,and it can help improve the precision of link prediction algorithm to certain extent,but considering the all paths steps more than two not means getting a better prediction effect,after analyzing the effect of all paths to link prediction between a node pair,we find the precision is better when we consider the paths steps equal or less than 3.On this basis,we put forward an algorithm called LEPD based on local effective paths in second chapter of this letter.After implemention of 12 real networks,we find LEPD is better than other 9 classical algorithms,and the precision can be improvement a lot.By simply counting the number of common neighbors and degree of common neighbors,The CN、AA and RA can’t distinguish the different role of the common neighbors,we propose an improved algorithm based on the na?ve Bayesian model in third chapter,this algorithm overcome the drawbacks that simply count the number of common neighbors and can’t distinguish the role of common neighbors by CN、AA、RA.Assigning values to the nodes in paths steps equal or less than 3 between node pairs by na?ve Bayesian model can distinguish different role of nodes well.After implemention of 4 real networks,the algorithms based on na?ve Bayesian model can get a better result than classical algorithms(CN,AA,RA and LP).In the second chapter and third chapter,the algorithms proposed by us mainly focus on the undirected networks.The real network can be well presented by the undirected networks,but,in many real systems,the relationship between node pair is not all the same.For instance,on social network,some friends are our close friends,and we always contact with them,but,to some friends we contact rarely.The close relationship and estranged relationship can be well presented by directed networks,therefore in the fourth chapter of this letter,after analyzing the effect of out degrees and in degrees on generating links in directed network,we propose a link prediction algorithm based on the node effectiveness of network.After comparing with other four algorithms in four real networks,the simulation result shows that our algorithms get a great improvement than other classical algorithms.