Late acceptance-based heuristic algorithms for identifying critical nodes of weighted graphs

Identifying important nodes in complex networks based on extended degree and E-shell hierarchy decomposition

The identification of important nodes is a hot topic in complex networks. Many methods have been proposed in different fields for solving this problem. Most previous work emphasized the role of a single feature and, as a result, rarely made full use of multiple items. This paper proposes a new method that utilizes multiple characteristics of nodes for the evaluation of their importance. First, an extended degree is defined to improve the classical degree. And E-shell hierarchy decomposition is put forward for determining nodes' position through the network's hierarchical structure. Then, based on the combination of these two components, a hybrid characteristic centrality and its extended version are proposed for evaluating the importance of nodes. Extensive experiments are conducted in six real networks, and the susceptible-infected-recovered model and monotonicity criterion are introduced to test the performance of the new approach. The comparison results demonstrate that the proposed new approach exposes more competitive advantages in both accuracy and resolution compared to the other five approaches.