Discovering Group Collapser for Network Resilience

<p dir="ltr">Network resilience refers to the ability of a network to maintain its functionality despite perturbations, where resilience/robustness is shown when a substantial proportion of its nodes remain engaged even under changes. Such phenomenon is common in real-world networks, such as computing power networks. Previous works demonstrate that the coreness of a user/node effectively captures the dynamics of user engagement. However, most existing works only consider changes in a single coreness value and thus fail to measure the overall network resilience. Subsequent works are either inefficient or do not consider coreness-decreased scenario. In this paper, we propose and study the collapsed follower maximization problem, aiming to maximize the number of coreness-decreased vertices by finding a group collapser (collapsing a set of vertices) with a given budget. We prove that the problem is NP-hard and W[2]-hard parameterized by the budget ��. To address the problem, we first present a Greedy algorithm that iteratively finds the best collapser in each of the budget �� iterations. To further optimize the Greedy algorithm, we propose GreedyOpt, which leverages the shell component structure to accelerate the computation of follower for one collapser and prune the search space. Extensive experimental results on 8 real-world datasets show that the effectiveness and efficiency of our algorithms.</p>