Identifying vital nodes by Achlioptas process
arXiv:2102.12101 · doi:10.1088/1367-2630/abe971
Abstract
The vital nodes are the ones that play an important role in the organization of network structure or the dynamical behaviours of networked systems. Previous studies usually applied the node centralities to quantify the importance of nodes. Realizing that the percolation clusters are dominated by local connections in the subcritical phase and by global connections in the supercritical phase, in this paper we propose a new method to identify the vital nodes via a competitive percolation process that is based on an Achlioptas process. Compared with the existing node centrality indices, the new method performs overall better in identifying the vital nodes that maintain network connectivity and facilitate network synchronization when considering different network structure characteristics, such as link density, degree distribution, assortativity, and clustering. We also find that our method is more tolerant of noisy data and missing data. More importantly, compared with the unique ranking list of nodes given by most centrality methods, the randomness of the percolation process expands the possibility space of the optimal solutions, which is of great significance in practical applications.
11 pages, 5 figures
References in corpus (35)
- Emergence of scaling in random networks
- Efficient Behavior of Small-World Networks
- Identification of influential spreaders in complex networks
- Mixing patterns in networks
- Network robustness and fragility: Percolation on random graphs
- Cascade-based attacks on complex networks
- Breakdown of the Internet under intentional attack
- Structural Vulnerability of the North American Power Grid
- Immunization of complex networks
- Influence maximization in complex networks through optimal percolation
- Efficient Immunization Strategies for Computer Networks and Populations
- Vital nodes identification in complex networks
- Growing Scale-Free Networks with Tunable Clustering
- Mitigation of Malicious Attacks on Networks
- Recommender Systems
- Leaders in Social Networks, the Delicious Case
- Missing and spurious interactions and the reconstruction of complex networks
- Cascade control and defense in complex networks
- Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
- Percolation on complex networks: Theory and application
- Resilience to damage of graphs with degree correlations
- Spreading dynamics in complex networks
- Explosive Phenomena in Complex Networks
- Fast and simple decycling and dismantling of networks
- How clustering affects the bond percolation threshold in complex networks
- Articulation Points in Complex Networks
- Optimal percolation on multiplex networks
- Stability of a Giant Connected Component in a Complex Network
- Fluctuations in percolation of sparse complex networks
- Controlling the uncertain response of real multiplex networks to random damage
- Systematic comparison between methods for the detection of influential spreaders in complex networks
- History-dependent percolation on multiplex networks
- Explosive percolation in graphs
- Characterizing cycle structure in complex networks
- Network growth approach to macroevolution