Identifying vital nodes by Achlioptas process

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 (11)

• Efficient Immunization Strategies for Computer Networks and Populations
• Vital nodes identification in complex networks
• Mitigation of Malicious Attacks on Networks
• 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
• Articulation Points in Complex Networks
• Stability of a Giant Connected Component in a Complex Network
• Network growth approach to macroevolution