# A Fast Algorithm for Moderating Critical Nodes via Edge Removal

arXiv: https://arxiv.org/abs/2309.06392 · HTML: https://mlsanity.com/paper/2309.06392/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 77 references that are in the map.
- First posted on arXiv 9 Sep 2023.

## Builds on (most cited first, 19 of 19)

- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [Guarantees for Greedy Maximization of Non-submodular Functions with Applications](https://mlsanity.com/paper/1703.02100/) (2017)
- [CED: Credible Early Detection of Social Media Rumors](https://mlsanity.com/paper/1811.04175/) (2018)
- [Vital nodes identification in complex networks](https://mlsanity.com/paper/1607.01134/) (2016)
- [Graph Vulnerability and Robustness: A Survey](https://mlsanity.com/paper/2105.00419/) (2021)
- [Generalized Network Dismantling](https://mlsanity.com/paper/1801.01357/) (2018)
- [Sparsified Cholesky and Multigrid Solvers for Connection Laplacians](https://mlsanity.com/paper/1512.01892/) (2015)
- [Local Algorithms for Estimating Effective Resistance](https://mlsanity.com/paper/2106.03476/) (2021)
- [An Efficient Randomized Algorithm for Rumor Blocking in Online Social Networks](https://mlsanity.com/paper/1701.02368/) (2017)
- [Fully Dynamic Spectral Vertex Sparsifiers and Applications](https://mlsanity.com/paper/1906.10530/) (2019)
- [Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees](https://mlsanity.com/paper/1705.00985/) (2017)
- [Current Flow Group Closeness Centrality for Complex Networks](https://mlsanity.com/paper/1802.02556/) (2018)
- [Improving information centrality of a node in complex networks by adding edges](https://mlsanity.com/paper/1804.06540/) (2018)
- [Better Sum Estimation via Weighted Sampling](https://mlsanity.com/paper/2110.14948/) (2021)
- [Scalable Adversarial Attack Algorithms on Influence Maximization](https://mlsanity.com/paper/2209.00892/) (2022)
- [Measures and Optimization for Robustness and Vulnerability in Disconnected Networks](https://mlsanity.com/paper/2306.08253/) (2023)
- [Scale-free Loopy Structure is Resistant to Noise in Consensus Dynamics in Complex Networks](https://mlsanity.com/paper/1801.00535/) (2018)
- [Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover Time](https://mlsanity.com/paper/2302.06372/) (2023)

## Built on by (most cited first, 3 of 3)

- [Promoting Fairness in Information Access within Social Networks](https://mlsanity.com/paper/2512.14711/) (2025)
- [Efficient Edge Rewiring Strategies for Enhancing PageRank Fairness](https://mlsanity.com/paper/2602.02512/) (2026)
- [A Generalisation of Voter Model: Influential Nodes and Convergence Properties](https://mlsanity.com/paper/2411.04564/) (2024)

## Abstract (arXiv)

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.