Research Of Link Prediction Algorithm Based On Local Structure In Complex Networks

Many research fields in real world can be described by complex networks,where nodes represent the objects and links denote the relationship between the objects.The research on the modeling mechanism and modeling process of complex networks can explain the common rules of the complex systems hidden in the nature,society and biology.The study of complex networks has important significance on explore the formation and evolvement of the networks.And,the link prediction as one of the most important research directions of complex networks,it has attracts increasing attention from many researchers.Link prediction aims at estimating the likelihood of the existence of links between nodes,based on observed links and the attributes of nodes.Many prediction algorithms are proposed with the development of the link prediction problem.Among them,the link prediction algorithms based on node similarity have been widely studied.However,it is not enough to study the link prediction problem using the local structure information.The local structure of the network has a great influence on improving the performance of the link prediction algorithm.The research on the local structure characteristics is of great significance to improve the prediction effect of the link prediction algorithm.In this dissertation,we make a deep research on the link prediction algorithm based on the local structure of the networks.The main contents include the following three aspects:Firstly,as one of the basic local structure,triadic closure has the characteristics of structural balance and stability.By calculating the weight of each node in the network according to the triadic closure,and the weights are used in the node similarity index,and proposed three similarity indexes of TWCN,TWAA,TWRA and the other three of TWCN*,TWAA*,TWRA*with adjustment parameter.And the PWNW algorithm and PWNW_α were proposed based on this new similarity indices.Experimental results show that the PWNW_α algorithm has more advantages in prediction accuracy.This results demonstrate that the information of tradic closure can effectively improve the prediction accuracy of the prediction algorithm.Moreover,we find a very interesting phenomenon that the network with more triadic closure nodes tend to be more stability by analyzing the experiment results.In other words a network with less triadic closure nodes are less stable,and it is more likely to establish a new link with others.This phenomenon is also consistent with some related phenomenon in sociology on weak relations to generate links.Secondly,clustering coefficient can be calculated by using the number of the node’s tradic closure and the degree of node.It can reflect the cluster ability of node.Clustering coefficient,as an important node topological property,it can not only reflect the compactness of local structure,but also play an important role in generating links.Traditional link prediction approach is to measure the similarity between two nodes through using the number of their common neighborhoods and their degrees.However,the relationship between nodes is not only related to the number and degree of neighbor nodes,but also has a close relationship with the local structure of nodes.Based on this idea,a new link prediction algorithm based on node degree and node clustering coefficient is proposed.Called NDCC algorithm.The similarity between two nodes is calculated by the degree and clustering coefficient of common neighborhoods.The algorithm not only makes the best of networks’ localstructure,but also can reflect the difference between common neighborhood nodes.Compared with several algorithms,the results show that the NDCC algorithm has a good advantage in prediction accuracy.Thirdly,many prediction algorithms only consider the common neighbor nodes between the predicted nodes,which can only reflect the network structure within the two steps from the target nodes.The disadvantage of this algorithms is that they have no ability to predict the node pairs that have no common neighbor nodes in the networks.The new links will not be limited by this neighbor structure.In order to solve this problem,the predictive ability of the prediction algorithm can be improved by using the sociological theories that the relationships within three degrees are the strong ties which can trigger behaviors.This behaviors can provide more opportunities for unconnected nodes.As the very important topological properties in the networks,nodes degree and nodes clustering coefficient are well suited to describe the tightness of the connections between nodes,which have a great impact on the network structure.Based on these two aspects,we propose a novel link prediction algorithm,which is based on the node topological property and strong ties.Called TPSR algorithm.This algorithm not only takes into account the topological attribute information of nodes(node’s degree and node’s clustering coefficient),but also utilize the strong ties.Compared with several traditional algorithms,the proposed algorithm has a greater prediction range and stronger prediction ability.