Research On The Methods To Search Important Nodes Of Complex Networks

Important nodes have critical influence on the structure of complex networks. Effectively locating important nodes in real networks may have imperative meaning in the aspects of network maintenance, network character study and so on. In this work, two important nodes searching methods are proposed from the perspective of topological structure and combining with biological information in PPI (Protein-Protein Interaction) network.Diameter is a very important topological parameter among various network topological indicators. However, it is seldom utilized in important node searching methods. In this study, the nodes on the diameter paths are defined as central nodes and a Diameter Center Detection (DCD) method is proposed to search the central nodes. The DCD method is applied to three deterministic networks, a series of small-world networks, scale-free networks, a star network with a long tail and five real networks, respectively. The experimental results show that the central nodes searched by DCD have advantages among the whole network in the evaluations of various centrality measures, e.g. betweenness centrality (BC), closeness centrality (CC), degree centrality (DC) and ?-shell decomposition results. In addition, after deleting central nodes, the network structure changes a lot on the perspective from both diameter and giant component. Moreover, the experimental results show that the edge deleting policy based on DCD is effective in the way that deleting fewer edges disrupting more node pair connectivity. The time complexity of the method is lower than Floyd algorithm for sparse networks because the central nodes are searched based on bread-first search and Bellman criterion instead of finding all the possible paths.It is proved that the precision of prediction combining with biological knowledge can be improved comparing with purely topological methods. However, most of these methods contain only one kind of biological information. And the intrinsic noises caused by false positives and false negatives of PPI also affect the accuracy of prediction. In this work, an effective essential protein prediction method by scoring prior proteins and weighting candidates is proposed, which is called as IDSSP. Firstly, every protein is assigned with a score according to several kinds of biological knowledge in STRING and those with highest scores are treated as prior proteins. Then candidates for essential proteins are chosen by assigning weights to the neighbors of all prior proteins in DIP. By combining DIP with STRING, the interactions have high credibility. The experimental results on Saccharomyces cerevisiae show that the proposed methods outperform the state-of-the-art methods CPPK, CEPPK and UDoNC in most cases. In addition, the prior proteins do not need to be essential proteins in our method.