Critical nodes reveal peculiar features of human essential genes and protein interactome Networkbased ranking methods (e.g., centrality analysis) have found extensive use in systems biology and network medicine for the prediction of essential proteins, for the prioritization of drug targets candidates in the treatment of several pathologies and in biomarker discovery, and for human disease genes identification. We here studied the connectivity of the human proteinprotein interaction network (i.e., the interactome) to find the nodes whose removal has the heaviest impact on the network, i.e., maximizes its fragmentation. Such nodes are known as Critical Nodes (CNs). Specifically, we implemented a Critical Node Heuristic (CNH) and compared its performance against other four heuristics based on well known centrality measures. To better understand the structure of the interactome, the CNsu0027 role played in the network, and the different heuristicsu0027 capabilities to grasp biologically relevant nodes, we compared the sets of nodes identified as CNs by each heuristic with two experimentally validated sets of essential genes, i.e., the genes whose removal impact on a given organismu0027s ability to survive. Our results show that classical centrality measures (i.e., closeness centrality, degree) found more essential genes with respect to CNH on the current version of the human interactome, however the removal of such nodes does not have the greatest impact on interactome connectivity, while, interestingly, the genes identified by CNH show peculiar characteristics both from the topological and the biological point of view. Finally, even if a relevant fraction of essential genes is found via the classical centrality measures, the same measures seem to fail in identifying the whole set of essential genes, suggesting once again that some of them are not central in the network, that there may be biases in the current interaction data, and that different, combined graph theoretical and other techniques should be applied for their discovery.

Identification of Essential Proteins Based on Centrality Methods Using Improved Collective Influence Algorithm Collective influence (CI) algorithm based on degree centrality is a very efficient method in the search of vital nodes in the large complex social networks. In this paper, we propose a novel CI method, called CIX frame and employ it to identify essential proteins in proteinprotein interaction (PPI) networks. More concretely, we apply the improved CI algorithm to process some stateoftheart methods which are based on centrality methods, such as DC, BC, CC, EC, SC and NC and so on. To investigate the performance of the CIX frame, some comparison experiments are implemented on the benchmark of two different yeast PPI networks obtained from DIP database and BioGRID database. The simulation results show that the identification accuracy of essential proteins of the most classical centrality methods can be improved by using our proposed CIX frame. It gives us a new insight to study the identification of essential proteins.