A Fast Algorithm for Moderating Critical Nodes via Edge Removal
This addresses the need for efficient moderation of vulnerable nodes to mitigate malicious diffusions like misinformation, though it is incremental as it builds on existing edge removal methods by incorporating information centrality.
The paper tackles the problem of moderating critical nodes in networks by removing edges to reduce their information centrality, proving it NP-complete and proposing fast approximation algorithms that run in nearly linear time, with experiments on networks over one million nodes showing effectiveness and efficiency.
Critical nodes in networks are extremely vulnerable to malicious attacks to trigger negative cascading events such as the spread of misinformation and diseases. Therefore, effective moderation of critical nodes is very vital for mitigating the potential damages caused by such malicious diffusions. The current moderation methods are computationally expensive. Furthermore, they disregard the fundamental metric of information centrality, which measures the dissemination power of nodes. We investigate the problem of removing $k$ edges from a network to minimize the information centrality of a target node $\lea$ while preserving the network's connectivity. We prove that this problem is computationally challenging: it is NP-complete and its objective function is not supermodular. However, we propose three approximation greedy algorithms using novel techniques such as random walk-based Schur complement approximation and fast sum estimation. One of our algorithms runs in nearly linear time in the number of edges. To complement our theoretical analysis, we conduct a comprehensive set of experiments on synthetic and real networks with over one million nodes. Across various settings, the experimental results illustrate the effectiveness and efficiency of our proposed algorithms.