Research On Link Prediction In Complex Networks

The hotspot in the field of complex networks is network evolution modeling, within which, there is a fundamental problem called link prediction. Here, we focus on exploration of link prediction algorithms based on similarity index. We implemented experiments based on data of the real networks, and the result shows that clustering coefficient is an important network topology, which seriously affects the accuracies of algorithms, especially the local similarity indices, such as CN and RA. Generally, most algorithms based on similarity index could give good results in networks of large clustering coefficient. Moreover, these indices that exploit the information of paths, such as Katz and LP, their accuracies will be affected by the length upper limit of paths that they utilize, we found that the optimal upper limit of path-lengths practically equals to the average distance of networks, paths that are longer than average distance contribute little to the prediction, and accuracy of the algorithm may decline if given paths that are longer than average distance. Besides, we found that the algorithms based on random walking, such as LRW and RWR, are more robust to the divergence of networks topologies. Especially, LRW gives satisfied prediction in most networks.We proposed a general model for exploring the behaviors in the process of network evolution. Under the model, we implemented this experiment:we gave the fresh links higher weight, so these fresh links would contribute more in the next step of prediction. And the overall result showed that the accuracy of algorithm increased. So the conclusion is that fresh links affect local evolution of networks more than old links, in practice, the fresh links will induce more links in local network. This result possibly contributes to network evolution modeling.