The Study Of Link Prediction Methods In Complex Networks

The study of complex networks has become a common focus of many branches of science, and link prediction is one of the most important and intersting problems. Link prediction problem aims at estimating the likelihood of the existence of a link between two nodes, based on the information of observed links and the attributes of nodes. Link prediction not noly includes the prediction of existing yet unkown links, but also includes the prediction of links that may appear in the future. The study of this problem has significant meaning and value both in theory and in application.The simplest framework of link prediction mthods are similarity-based algorithm, which are classified into three types:local similarity indices, gloab similarity indices, quasi-local indices. Common Neighbor, Adamic-Adar and Resource Allocation index perform the best among local similarity indices. In this paper, we modify above three local similarity indices, we extend the information of common neighbors on the basis of the original definition of the above three indices. We not only consider the information of one-step length common neighbors between two nodes, but also add the information of two-step common neighbors between two nodes. We change parameters to adjust the weights of the intersections from different length neighbors according to the topological structure of different networks, which can achieve the most accurate predition effect. According to the experimental results of real networks, it demonstrates that the modified indices remarkably improve prediction accuracy than local path index, Katz index, LHN2index and local similarity indices. The modified indices not only predict links accurately and steadily, but also have quick computation speed. Especially as to huge-scale and sparse networks, the modified indices not only improve prediction accuracy on large-scale, but also take distinct advantages in the way of computational speed. Experimental results also demonstrate that the optimal parameter values of a few networks are negative, we utilize k-shell method to analyze the structure of networks’cores, we find that these networks have steady cores, the links of the cores are highly tight. These networks include some interferential information, we use a negative parameter to cripple these interferential information, which can achieve the most accurate prediction effect.Rich cliub is a special phenomenon in complex networks, the nodes with high degree(rich nodes) are more likely to organize into tight and highly-interconnected groups(clubs) than low-degree nodes. There are many methods of judging rich club phenomenon, which usually need to be compared with a multitude of random models with the same degree distribution, these processes are rather cockamamie. As an application of our modified indices, in this paper, we find the optimal parameters to adjust the weights of the intersections from different length neighbors, if the optimal parameter values are negative, we can judge that these networks have obvious rich phenomenon. The method is intuitive and has a simple process,which has a preferable judgement effect.