A node degree dependent random perturbation method for prediction of missing links in the network

摘要

In present study, I proposed a node degree dependent random perturbation algorithm for prediction of missing links in the network. In the algorithm, I assume that a node with more existing links harbors more missing links. There are two rules. Rule 1 means that a randomly chosen node tends to connect to the node with greater degree. Rule 2 means that a link tends to be created between two nodes with greater degrees. Missing links of some tumor related networks (pathways) are predicted. The results prove that the prediction efficiency and percentage of correctly predicted links against predicted missing links with the algorithm increases as the increase of network complexity. The required number for finding true missing links in the predicted list reduces as the increase of network complexity. Prediction efficiency is complexity-depedent only. Matlab codes of the algorithm are given also. Finally, prospect of prediction for missing links is briefly reviewed. So far all prediction methods based on static topological structure only (represented by adjacency matrix) seems to be low efficient. Network evolution based, node similarity based, and sampling based (correlation based) methods are expected to be the most promising in the future.