Network Immunization Strategy by Eliminating Fringe Nodes: A Percolation Perspective
提出边缘节点集概念，在渗流视角下优化网络免疫策略，通过重构方法衡量节点对巨分量的贡献，降低计算时间并提升效果。
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.