Network Immunization Strategy by Eliminating Fringe Nodes: A Percolation Perspective

Abstract

To date, many strategies involving graph theory have been proposed to solve the targeted immunization problem. Among them, the well-known relationship-related (RR) method makes use of the sum rule and the product rule from the perspective of the network explosive percolation. However, the RR method needs to carefully consider all nodes within a network, leading to high computational time. To close this gap, we propose the fringe node set: it is applied to an immunization strategy such as RR to remove noncritical nodes before optimizing the node sequence. Besides adapting this algorithm for strategies, such as RR and degree centrality strategy, we further propose a novel reconstruction method (RM) under the percolation perspective, which ranks critical nodes by measuring their contribution to the giant component in the network reconstruction or node reoccupying process. Experimental results based on our proposed identification method have demonstrated the feasibility of using the fringe node set. The competitive advantage of our proposed RM is also demonstrated in comparison with other existing methods.