Lowest degree decomposition of complex networks

The identification of vital nodes is a fundamental challenge in network science. Motivated by the nested nature of real networks, we propose a decomposition method termed Lowest Degree Decomposition (LDD). This method iteratively prunes the nodes with the lowest degree at each step, revealing a refined structural hierarchy. We rigorously prove that LDD is a subdivision of the famous k-core decomposition. We further propose the so-called LDD+ index that integrates the normalized ranking scores of the target node and its immediate neighbors subject to the LDD index. Extensive numerical experiments on epidemic spreading, synchronization, and nonlinear mutualistic dynamics demonstrate that the LDD+ index can more accurately locate the most influential spreaders, the most efficient controllers, and the most vulnerable species than k-core decomposition and other well established indices. In addition to identifying vital nodes, LDD can also be used as a powerful tool in network visualization and a novel criterion in network modeling.