Optimizing Network Resilience via Vertex Anchoring
Open Access
- 13 May 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 606-617
Abstract
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 thefollower 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 O(n^1-ε ) factor. We first propose an advanced greedy approach, followed by a time-dependent 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.Keywords
This publication has 40 references indexed in Scilit:
- Minimizing the Influence of Misinformation via Vertex Blocking2023
- Discovering key users for defending network structural stabilityWorld Wide Web, 2021
- The mechanism of collapse of the Friendster network: What can we learn from the core structure of Friendster?Social Network Analysis and Mining, 2017
- Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problemsRAIRO - Theoretical Informatics and Applications, 2016
- Preventing Unraveling in Social Networks: The Anchored $k$-Core ProblemSIAM Journal on Discrete Mathematics, 2015
- To stay or not to stay2013
- Combinatorial Optimization2002
- Size-Estimation Framework with Applications to Transitive Closure and ReachabilityJournal of Computer and System Sciences, 1997
- Smallest-last ordering and clustering and graph coloring algorithmsJournal of the ACM, 1983
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. IJournal of the Society for Industrial and Applied Mathematics, 1962