IEEE Trans Cybern. 2021 Jul;51(7):3752-3766. doi: 10.1109/TCYB.2020.2975530. Epub 2021 Jun 23.
The control of virus spreading over complex networks with a limited budget has attracted much attention but remains challenging. This article aims at addressing the combinatorial, discrete resource allocation problems (RAPs) in virus spreading control. To meet the challenges of increasing network scales and improve the solving efficiency, an evolutionary divide-and-conquer algorithm is proposed, namely, a coevolutionary algorithm with network-community-based decomposition (NCD-CEA). It is characterized by the community-based dividing technique and cooperative coevolution conquering thought. First, to reduce the time complexity, NCD-CEA divides a network into multiple communities by a modified community detection method such that the most relevant variables in the solution space are clustered together. The problem and the global swarm are subsequently decomposed into subproblems and subswarms with low-dimensional embeddings. Second, to obtain high-quality solutions, an alternative evolutionary approach is designed by promoting the evolution of subswarms and the global swarm, in turn, with subsolutions evaluated by local fitness functions and global solutions evaluated by a global fitness function. Extensive experiments on different networks show that NCD-CEA has a competitive performance in solving RAPs. This article advances toward controlling virus spreading over large-scale networks.
在具有有限预算的复杂网络上控制病毒传播引起了广泛关注，但仍然具有挑战性。本文旨在解决病毒传播控制中的组合式、离散资源分配问题（RAPs）。为了应对不断增加的网络规模的挑战并提高求解效率，提出了一种进化式分治算法，即基于网络社区分解的协同进化算法（NCD-CEA）。它的特点是基于社区的划分技术和协作式协同进化思想。首先，为了降低时间复杂度，NCD-CEA 通过一种改进的社区检测方法将网络划分为多个社区，以便将解空间中的最相关变量聚类在一起。然后，将问题和全局群体分解为具有低维嵌入的子问题和子群体。其次，为了获得高质量的解决方案，设计了一种替代的进化方法，通过依次促进子群体和全局群体的进化，使用局部适应度函数评估子解，使用全局适应度函数评估全局解。在不同网络上的广泛实验表明，NCD-CEA 在解决 RAPs 方面具有竞争性能。本文推进了在大规模网络上控制病毒传播的研究。
