Lowest Degree Decomposition of Complex Networks
arXiv:2002.05358
Abstract
The heterogeneous structure implies that a very few nodes may play the critical role in maintaining structural and functional properties of a large-scale network. Identifying these vital nodes is one of the most important tasks in network science, which allow us to better conduct successful social advertisements, immunize a network against epidemics, discover drug target candidates and essential proteins, and prevent cascading breakdowns in power grids, financial markets and ecological systems. Inspired by the nested nature of real networks, we propose a decomposition method where at each step the nodes with the lowest degree are pruned. We have strictly proved that this so-called lowest degree decomposition (LDD) is a subdivision of the famous k-core decomposition. Extensive numerical analyses on epidemic spreading, synchronization and nonlinear mutualistic dynamics show that the LDD can more accurately find out the most influential spreaders, the most efficient controllers and the most vulnerable species than k-core decomposition and other well-known indices. The present method only makes use of local topological information, and thus has high potential to become a powerful tool for network analysis.
arXiv comment12 pages, 2 figures, 4 tables
References in corpus (16)
- Emergence of scaling in random networks
- Epidemic spreading in scale-free networks
- Cooperative Game Theory Approaches for Network Partitioning
- Epidemic processes in complex networks
- Identification of influential spreaders in complex networks
- The Dynamics of Viral Marketing
- Structural Vulnerability of the North American Power Grid
- Influence maximization in complex networks through optimal percolation
- Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
- Leaders in Social Networks, the Delicious Case
- Thresholds for epidemic spreading in networks
- k-core organization of complex networks
- Ranking spreaders by decomposing complex networks
- Spreading dynamics in complex networks
- The k-core as a predictor of structural collapse in mutualistic ecosystems
- Spin glass approach to the feedback vertex set problem