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.

网络中的关键节点对恶意攻击非常脆弱，容易引发负面级联事件，例如信息传播和疾病传播。因此，对关键节点进行有效的监管对于减轻此类恶意扩散造成的潜在损害非常重要。我们研究了从网络中删除k个边以最小化目标节点信息中心度而保持网络连通性的问题，并提出了三种近似贪婪算法，使用了基于随机游走的舒尔补近似和快速求和估计等新技术。我们的算法中的一种在边的数量下达到了几乎线性的运行时间。通过综合性的实验，在超过一百万个节点的合成和真实网络上，实验结果证明了我们提出的算法的有效性和效率。

一种通过边缘删除调整关键节点的快速算法