Optimizing Network Resilience via Vertex Anchoring

Network resilience is a critical ability of a network to maintain its functionality against disturbances. A network is resilient/robust when a large portion of the nodes are to be better engaged in the network, i.e., they are less likely to leave given the changes on the network. Existing studies validate that the engagement of a node can be well captured by its coreness on network topology. Therefore, it is promising to maximize the number of nodes with increasing coreness values. In this paper, we propose and study the follower maximization problem: maximizing the resilience gain (the number of coreness-increased vertices) via anchoring a set of vertices within a given budget. We prove that the problem is NP-hard and W[2]hard, and it is NP-hard to approximate within an 𝑂 (𝑛 1-𝜖 ) factor. We first propose an advanced greedy approach, followed by a timedependent framework designed to quickly find high-quality results. The framework is initialized by the advanced greedy algorithm and incorporates novel techniques for optimizing the search space. The effectiveness and efficiency of our solution are verified with extensive experiments on 8 real-life datasets. Our source codes are available at https://github.com/Tsyxxxka/Follower-Maximization . CCS CONCEPTS • Theory of computation → Graph algorithms analysis.