Efficient Continuous Network Dismantling
提出EDIS框架，基于网络渗流理论，通过局部目标函数和候选选择方法，在百万节点网络中秒级找到关键节点集，用于抑制病毒或虚假信息传播。
A great number of studies have demonstrated that many complex systems could benefit a lot from complex networks, through either a direct modeling on which dynamics among agents could be investigated in a global view or an indirect representation by the aid of that the leading factors could be captured more clearly. Hence, in the context of networks, this article copes with the continuous network dismantling problem which aims to find the key node set whose removal would break down a given network more thoroughly and thus is more capable of suppressing virus or misinformation. To achieve this goal effectively and efficiently, we propose the external-degree and internal-size component suppression (EDIS) framework based on the network percolation, where we constrain the search space by a well-designed local goal function and candidate selection approach such that EDIS could obtain better results than the-state-of-the-art in networks of millions of nodes in seconds. We also contribute two strategies with time complexity <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathcal {O}}(m\log _{\vartheta } m)$ </tex-math></inline-formula> and space complexity <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathcal {O}}(m)$ </tex-math></inline-formula>, of networks of m edges, under such framework by well studying the evolving characteristics of the associated connected components as nodes are occupied, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\vartheta \gt 1$ </tex-math></inline-formula> is a hyperparameter. Our results on 12 empirical networks from various domains demonstrate that the proposed method has far better performance than the-state-of-the-art over both effectiveness and computing time. Our study could play important roles in many real-world scenarios, such as the containment of misinformation or epidemics, the distribution of resources or vaccine, the decision of which group of individuals set to quarantine, or the detection of the resilience of a network-based system under intentional attacks.