Resource Allocation Method for Virus Spreading Control Based on Multi-granularity Cooperative Coevolution

doi:10.16182/j.issn1004731x.joss.24-0315

Abstract

Abstract:

According to the principle of simplifying a complex problem into sub-problems for solution, a resource allocation method for virus spreading control based on multi-granularity cooperative coevolution (MGCC) was proposed. According to the characteristics of human's social network structures, MGCC decomposed the network into sub-networks with different scales according to different decomposition granularities. A contribution-based decomposition granularity selection strategy was proposed. Historical archives were used to record the contribution of different decomposition granularities to optimization, and the appropriate decomposition granularity was selected according to the optimization status. A projection-based constraint repairing strategy was designed to ensure the feasibility of solutions. The results show that MGCC can decompose complex social network structures and ensure resource allocation by combining different evolutionary operators, improving the effectiveness of evolutionary operators in solving the resource allocation problem for virus spreading control.

Key words: virus spreading control, network spreading, cooperative coevolution, evolutionary computation, resource allocation

CLC Number:

TP391.9

Shi Xuanli, Chen Weineng, Song An, Zhao Tianfang. Resource Allocation Method for Virus Spreading Control Based on Multi-granularity Cooperative Coevolution[J]. Journal of System Simulation, 2025, 37(8): 2043-2060.

Figures/Tables 12

Fig. 1

Fig. 2

Fig. 3

Table 1

Table 2

Fig. 4

Table 3

Comparative experiments of MGCC with different granularities

网络	指标	MGCC_CSO	CSO_g2	CSO_g3	CSO_g4	MGCC_DE	DE_g2	DE_g3	DE_g4
Net_01	mean	0.487 0	0.499 8	0.504 2	0.496 8	0.462 3	0.518 9	0.485 2	0.463 1
	std	1.73×10^-2	2.28×10^-2	2.33×10^-2	2.26×10^-2	2.47×10^-2	2.50×10^-2	3.40×10^-2	2.52×10^-2
	p-value	—	4.68×10^-2(+)	3.67×10^-3(+)	1.26×10^-1(≈)	—	2.67×10^-9(+)	7.96×10^-3(+)	9.00×10^-1(≈)
Net_02	mean	0.449 8	0.473 6	0.466 7	0.477 5	0.416 4	0.481 7	0.464 7	0.438 1
	std	2.27×10^-2	2.86×10^-2	2.48×10^-2	2.61×10^-2	2.46×10^-2	3.26×10^-2	3.48×10^-2	2.51×10^-2
	p-value	—	9.52×10^-4(+)	1.17×10^-2(+)	1.25×10^-4(+)	—	3.82×10^-9(+)	8.20×10^-7(+)	7.70×10^-4(+)
Net_03	mean	0.474 8	0.489 7	0.496 1	0.491 5	0.453 9	0.511 6	0.473 2	0.463 7
	std	2.63×10^-2	1.97×10^-2	2.19×10^-2	2.72×10^-2	3.33×10^-2	2.74×10^-2	2.83×10^-2	3.06×10^-2
	p-value	—	1.76×10^-2(+)	2.16×10^-3(+)	2.51×10^-2(+)	—	4.69×10^-8(+)	3.39×10^-2(+)	3.11×10^-1(+)
Net_04	mean	0.473 1	0.500 3	0.493 3	0.500 6	0.439 9	0.504 3	0.483 8	0.458 3
	std	2.11×10^-2	2.64×10^-2	2.63×10^-2	2.58×10^-2	3.16×10^-2	2.81×10^-2	3.18×10^-2	2.77×10^-2
	p-value	—	1.17×10^-4(+)	3.50×10^-3(+)	9.79×10^-5(+)	—	7.77×10^-9(+)	6.28×10^-6(+)	1.99×10^-2(+)
Net_05	mean	0.466 8	0.492 7	0.492 1	0.493 8	0.452 0	0.507 1	0.490 2	0.466 1
	std	1.97×10^-2	2.58×10^-2	1.96×10^-2	2.81×10^-2	2.50×10^-2	3.31×10^-2	1.91×10^-2	2.23×10^-2
	p-value	—	1.41×10^-4(+)	2.77×10^-5(+)	2.68×10^-4(+)	—	1.60×10^-7(+)	1.16×10^-7(+)	1.38×10^-2(+)
Net_06	mean	0.472 5	0.479 9	0.477 4	0.477 3	0.428 5	0.483 5	0.463 0	0.440 1
	std	2.54×10^-2	3.06×10^-2	2.19×10^-2	2.28×10^-2	2.45×10^-2	2.70×10^-2	2.78×10^-2	2.93×10^-2
	p-value	—	2.46×10^-1(≈)	6.31×10^-1(≈)	6.10×10^-1(≈)	—	8.48×10^-9(+)	1.53×10^-5(+)	1.54×10^-1(≈)
Net_07	mean	0.518 3	0.530 4	0.542 9	0.526 7	0.491 0	0.543 1	0.532 5	0.497 3
	std	2.23×10^-2	2.34×10^-2	2.54×10^-2	2.45×10^-2	2.65×10^-2	3.28×10^-2	2.50×10^-2	2.95×10^-2
	p-value	—	1.54×10^-1(≈)	5.56×10^-4(+)	3.71×10^-1(≈)	—	2.38×10^-7(+)	1.39×10^-6(+)	2.84×10^-1(≈)
Net_08	mean	0.480 5	0.497 3	0.506 8	0.503 8	0.447 6	0.508 0	0.501 3	0.463 1
	std	2.42×10^-2	2.69×10^-2	2.75×10^-2	2.71×10^-2	2.88×10^-2	3.29×10^-2	2.52×10^-2	2.80×10^-2
	p-value	—	3.39×10^-2(+)	1.06×10^-3(+)	1.52×10^-3(+)	—	5.09×10^-8(+)	1.70×10^-8(+)	9.05×10^-2(≈)
Net_09	mean	0.535 6	0.553 8	0.553 8	0.548 8	0.489 3	0.558 3	0.543 9	0.517 3
	std	2.14×10^-2	3.02×10^-2	2.59×10^-2	2.70×10^-2	2.92×10^-2	3.90×10^-2	3.27×10^-2	3.10×10^-2
	p-value	—	1.17×10^-2(+)	1.50×10^-2(+)	7.98×10^-2(≈)	—	1.31×10^-8(+)	2.38×10^-7(+)	1.17×10^-3(+)
Net_10	mean	0.479 5	0.500 1	0.515 0	0.505 4	0.450 5	0.513 9	0.503 3	0.476 0
	std	2.77×10^-2	2.48×10^-2	2.74×10^-2	2.28×10^-2	2.31×10^-2	2.83×10^-2	3.36×10^-2	2.67×10^-2
	p-value	—	4.03×10^-3(+)	2.13×10^-5(+)	7.66×10^-5(+)	—	8.89×10^-10(+)	7.09×10^-8(+)	3.99×10^-4(+)
w/l/d		—	8/0/2	9/0/1	6/0/4	—	10/0/0	10/0/0	6/0/4

Table 3

Fig. 5

Table 4

Table 5

Fig. 6

Fig. 7

References 49

[1]	Lakshmi Priyadarsini S, Suresh M, Huisingh D. What Can We Learn from Previous Pandemics to Reduce the Frequency of Emerging Infectious Diseases Like COVID-19?[J]. Global Transitions, 2020, 2: 202-220.
[2]	朱炳宇, 刘朕, 张景祥. 融合Grad-CAM和卷积神经网络的COVID-19检测算法[J]. 计算机科学与探索, 2022, 16(9): 2108-2120.
	Zhu Bingyu, Liu Zhen, Zhang Jingxiang. COVID-19 Detection Algorithm Combining Grad-CAM and Convolutional Neural Network[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(9): 2108-2120.
[3]	Feng Shuo, Feng Zebang, Ling Chen, et al. Prediction of the COVID-19 Epidemic Trends Based on SEIR and AI Models[J]. PLOS One, 2021, 16(1): e0245101.
[4]	Muhammad Naveed Aman, Javaid Uzair, Sikdar Biplab. IoT-proctor: A Secure and Lightweight Device Patching Framework for Mitigating Malware Spread in IoT Networks[J]. IEEE Systems Journal, 2022, 16(3): 3468-3479.
[5]	Doshi Ronak, Ramesh Ajay, Rao Shrisha. Modeling Influencer Marketing Campaigns in Social Networks[J]. IEEE Transactions on Computational Social Systems, 2023, 10(1): 322-334.
[6]	Zhao Tianfang, Chen Weineng, Liew A W C, et al. A Binary Particle Swarm Optimizer with Priority Planning and Hierarchical Learning for Networked Epidemic Control[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(8): 5090-5104.
[7]	Preciado V M, Zargham M, Enyioha C, et al. Optimal Resource Allocation for Network Protection Against Spreading Processes[J]. IEEE Transactions on Control of Network Systems, 2014, 1(1): 99-108.
[8]	Agrawal A, Diamond S, Boyd S. Disciplined Geometric Programming[J]. Optimization Letters, 2019, 13(5): 961-976.
[9]	Deng Zhenhua, Xiaohong Nian, Hu Chen. Distributed Algorithm Design for Nonsmooth Resource Allocation Problems[J]. IEEE Transactions on Cybernetics, 2020, 50(7): 3208-3217.
[10]	Wang Xiaoxuan, Yang Shaofu, Guo Zhenyuan, et al. A Distributed Dynamical System for Optimal Resource Allocation Over State-dependent Networks[J]. IEEE Transactions on Network Science and Engineering, 2022, 9(4): 2940-2951.
[11]	周涛, 傅忠谦, 牛永伟, 等. 复杂网络上传播动力学研究综述[J]. 自然科学进展, 2005, 15(5): 513-518.
[12]	樊长佳, 杜炎秋, 梁笛, 等. COVID-19期间上海市应急医疗资源配置建模与仿真[J]. 系统仿真学报, 2022, 34(1): 93-103.
	Fan Changjia, Du Yanqiu, Liang Di, et al. Modeling and Simulation of Emergency Medical Resources Allocation in Shanghai during COVID-19[J]. Journal of System Simulation, 2022, 34(1): 93-103.
[13]	Sun Lu, Wan Liangtian, Liu Kaihui, et al. Cooperative-evolution-based WPT Resource Allocation for Large-scale Cognitive Industrial IoT[J]. IEEE Transactions on Industrial Informatics, 2020, 16(8): 5401-5411.
[14]	Zhao Tianfang, Chen Weineng, Kwong S, et al. Evolutionary Divide-and-conquer Algorithm for Virus Spreading Control Over Networks[J]. IEEE Transactions on Cybernetics, 2021, 51(7): 3752-3766.
[15]	Cheng Ran, Jin Yaochu. A Competitive Swarm Optimizer for Large Scale Optimization[J]. IEEE Transactions on Cybernetics, 2015, 45(2): 191-204.
[16]	Opara Karol R, Arabas Jarosław. Differential Evolution: A Survey of Theoretical Analyses[J]. Swarm and Evolutionary Computation, 2019, 44: 546-558.
[17]	宋玉蓉, 鲍裕霖, 李汝琦. 意识扩散和SEIR病毒的双层网络传播模型[J]. 系统仿真学报, 2022, 34(11): 2437-2447.
	Song Yurong, Bao Yulin, Li Ruqi. A Two-layer Network Propagation Model of Awareness Diffusion and SEIR Epidemic[J]. Journal of System Simulation, 2022, 34(11): 2437-2447.
[18]	王磊, 孙晋海, 李拓键. 基于SIS模型的锻炼获益感知传播建模与仿真[J]. 系统仿真学报, 2022, 34(12): 2566-2574.
	Wang Lei, Sun Jinhai, Li Tuojian. SIS-based Modeling and Simulation Analysis on Exercise Benefit Perception Transmission[J]. Journal of System Simulation, 2022, 34(12): 2566-2574.
[19]	Luo Wuqiong, Wee Peng Tay, Leng Mei. How to Identify an Infection Source with Limited Observations[J]. IEEE Journal of Selected Topics in Signal Processing, 2014, 8(4): 586-597.
[20]	She Baike, Liu Ji, Sundaram S, et al. On a Networked SIS Epidemic Model with Cooperative and Antagonistic Opinion Dynamics[J]. IEEE Transactions on Control of Network Systems, 2022, 9(3): 1154-1165.
[21]	He Zaiyin, Abbes Abderrahmane, Jahanshahi Hadi, et al. Fractional-order Discrete-time SIR Epidemic Model with Vaccination: Chaos and Complexity[J]. Mathematics, 2022, 10(2): 165.
[22]	Yang Zifeng, Zeng Zhiqi, Wang Ke, et al. Modified SEIR and AI Prediction of the Epidemics Trend of COVID-19 in China Under Public Health Interventions[J]. Journal of Thoracic Disease, 2020, 12(3): 165-174.
[23]	Zhou Xueyong, Cui Jingan. Analysis of Stability and Bifurcation for an SEIV Epidemic Model with Vaccination and Nonlinear Incidence Rate[J]. Nonlinear Dynamics, 2011, 63(4): 639-653.
[24]	Potter M A, Kenneth A de Jong. Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents[J]. Evolutionary Computation, 2000, 8(1): 1-29.
[25]	Xu Biao, Gong Dunwei, Zhang Yong, et al. Cooperative Co-evolutionary Algorithm for Multi-objective Optimization Problems with Changing Decision Variables[J]. Information Sciences, 2022, 607: 278-296.
[26]	Yang Qiang, Chen Weineng, Gu Tianlong, et al. A Distributed Swarm Optimizer with Adaptive Communication for Large-scale Optimization[J]. IEEE Transactions on Cybernetics, 2020, 50(7): 3393-3408.
[27]	Mohammad Nabi Omidvar, Li Xiaodong, Yao Xin. Cooperative Co-evolution with Delta Grouping for Large Scale Non-separable Function Optimization[C]//IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 2010: 1-8.
[28]	Yang Zhenyu, Tang Ke, Yao Xin. Multilevel Cooperative Coevolution for Large Scale Optimization[C]//2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence). Piscataway: IEEE, 2008: 1663-1670.
[29]	Song An, Yang Qiang, Chen Weineng, et al. A Random-based Dynamic Grouping Strategy for Large Scale Multi-objective Optimization[C]//2016 IEEE Congress on Evolutionary Computation (CEC). Piscataway: IEEE, 2016: 468-475.
[30]	Munetomo M, Goldberg D E. A Genetic Algorithm Using Linkage Identification by Nonlinearity Check[C]//IEEE SMC'99 Conference Proceedings. 1999 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No.99CH37028). Piscataway: IEEE, 1999: 595-600.
[31]	Omidvar M N, Yang Ming, Mei Yi, et al. DG2: A Faster and More Accurate Differential Grouping for Large-scale Black-box Optimization[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(6): 929-942.
[32]	Omidvar M N, Li Xiaodong, Mei Yi, et al. Cooperative Co-evolution with Differential Grouping for Large Scale Optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 378-393.
[33]	Sun Yuan, Kirley Michael, Saman Kumara Halgamuge. Extended Differential Grouping for Large Scale Global Optimization with Direct and Indirect Variable Interactions[C]//Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2015: 313-320.
[34]	Jia Yahui, Mei Yi, Zhang Mengjie. Contribution-based Cooperative Co-evolution for Nonseparable Large-scale Problems with Overlapping Subcomponents[J]. IEEE Transactions on Cybernetics, 2022, 52(6): 4246-4259.
[35]	Jia Yahui, Chen Weineng, Gu Tianlong, et al. Distributed Cooperative Co-evolution with Adaptive Computing Resource Allocation for Large Scale Optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(2): 188-202.
[36]	Liu Haiyan, Wang Yuping, Fan Ninglei. A Hybrid Deep Grouping Algorithm for Large Scale Global Optimization[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(6): 1112-1124.
[37]	Omidvar M N, Kazimipour Borhan, Li Xiaodong, et al. CBCC3——A Contribution-based Cooperative Co-evolutionary Algorithm with Improved Exploration/Exploitation Balance[C]//2016 IEEE Congress on Evolutionary Computation (CEC). Piscataway: IEEE, 2016: 3541-3548.
[38]	Ma Xiaoliang, Li Xiaodong, Zhang Qingfu, et al. A Survey on Cooperative Co-evolutionary Algorithms[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(3): 421-441.
[39]	Yang Ming, Omidvar M N, Li Changhe, et al. Efficient Resource Allocation in Cooperative Co-evolution for Large-scale Global Optimization[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(4): 493-505.
[40]	Karypis George, Kumar Vipin. Multilevelk-way Partitioning Scheme for Irregular Graphs[J]. Journal of Parallel and Distributed Computing, 1998, 48(1): 96-129.
[41]	Nowzari C, Preciado V M, Pappas G J. Optimal Resource Allocation for Control of Networked Epidemic Models[J]. IEEE Transactions on Control of Network Systems, 2017, 4(2): 159-169.
[42]	Mei Wenjun, Mohagheghi S, Zampieri Sandro, et al. On the Dynamics of Deterministic Epidemic Propagation Over Networks[J]. Annual Reviews in Control, 2017, 44: 116-128.
[43]	Wu Zuqing, Shi Chao, Ping Jialun, et al. Contributions of the Vector-channel at Finite Isospin Chemical Potential with the Self-consistent Mean Field Approximation[J]. Physical Review D, 2020, 101(7): 074008.
[44]	van Mieghem Piet, Omic Jasmina, Kooij Robert. Virus Spread in Networks[J]. IEEE/ACM Transactions on Networking, 2009, 17(1): 1-14.
[45]	刘琛, 林盈, 胡晓敏. 差分演化算法各种更新策略的对比分析[J]. 计算机科学与探索, 2013, 7(11): 983-993.
	Liu Chen, Lin Ying, Hu Xiaomin. Analyses and Comparisons of Different Update Strategies for Differential Evolution[J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(11): 983-993.
[46]	Zegura E W, Calvert K L, Bhattacharjee S. How to Model an Internetwork[C]//Proceedings of IEEE INFOCOM'96. Conference on Computer Communications. Piscataway: IEEE, 1996: 594-602.
[47]	Song An, Chen Weineng, Gong Yuejiao, et al. A Divide-and-conquer Evolutionary Algorithm for Large-scale Virtual Network Embedding[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(3): 566-580.
[48]	Fischer Andreas, Juan Felipe Botero, Michael Till Beck, et al. Virtual Network Embedding: A Survey[J]. IEEE Communications Surveys & Tutorials, 2013, 15(4): 1888-1906.
[49]	Song An, Chen Weineng, Luo Xiaonan, et al. Scheduling Workflows with Composite Tasks: A Nested Particle Swarm Optimization Approach[J]. IEEE Transactions on Services Computing, 2022, 15(2): 1074-1088.

网络	指标	MGCC_ CSO	MGCC_ CSO_2	MGCC_ DE	MGCC_ DE_2	网络	指标	MGCC_ CSO	MGCC_ CSO_2	MGCC_ DE	MGCC_ DE_2
Net_01	mean	0.487 5	0.510 8	0.462 4	0.543 2	Net_06	mean	0.472 9	0.491 9	0.428 7	0.518 2
	std	1.71×10^-2	3.06×10^-2	2.47×10^-2	3.21×10^-2		std	2.56×10^-2	2.03×10^-2	2.45×10^-2	3.24×10^-2
	p-value	2.24×10^-7(+)		8.57×10^-72(+)			p-value	8.80×10^-6(+)		1.70×10^-76(+)
Net_02	mean	0.450 0	0.487 6	0.416 5	0.511 2	Net_07	mean	0.518 7	0.540 4	0.491 1	0.560 6
	std	2.28×10^-2	2.61×10^-2	2.46×10^-2	2.97×10^-2		std	2.23×10^-2	2.88×10^-2	2.65×10^-2	3.12×10^-2
	p-value	1.58×10^-14(+)		1.25×10^-82(+)			p-value	5.93×10^-7(+)		8.37×10^-67(+)
Net_03	mean	0.474 9	0.512 3	0.454 1	0.536 3	Net_08	mean	0.480 8	0.499 7	0.447 7	0.514 0
	std	2.64×10^-2	2.50×10^-2	3.33×10^-2	2.98×10^-2		std	2.41×10^-2	2.17×10^-2	2.87×10^-2	3.10×10^-2
	p-value	5.16×10^-12(+)		5.86×10^-71(+)			p-value	9.89×10^-6(+)		9.51×10^-62(+)
Net_04	mean	0.473 4	0.503 8	0.440 0	0.530 5	Net_09	mean	0.536 0	0.573 0	0.489 4	0.591 7
	std	2.12×10^-2	2.77×10^-2	3.15×10^-2	2.19×10^-2		std	2.12×10^-2	3.36×10^-2	2.92×10^-2	3.54×10^-2
	p-value	7.89×10^-11(+)		8.07×10^-78(+)			p-value	3.84×10^-11(+)		6.29×10^-77(+)
Net_05	mean	0.467 2	0.506 1	0.452 1	0.537 0	Net_10	mean	0.479 9	0.515 1	0.450 6	0.539 7
	std	1.97×10^-2	2.76×10^-2	2.50×10^-2	2.75×10^-2		std	2.78×10^-2	2.66×10^-2	2.31×10^-2	3.42×10^-2
	p-value	4.18×10^-16(+)		3.29×10^-76(+)			p-value	1.17×10^-10(+)		2.69×10^-75(+)

算法	congress-Twitter			US_Airport_top500
算法	mean	std	p-value	mean	std	p-value
MGCC_CSO	3.812 8	0.094 1	—	1.624 3	0.149 6	—
CSO	3.872 6	0.139 3	1.54×10^-16(+)	1.695 6	0.079 3	5.61×10^-33(+)
CSO_g2	3.846 9	0.102 7	4.07×10^-5(+)	1.641 8	0.188 2	6.48×10^-9(+)
CSO_g3	3.892 5	0.175 8	1.02×10^-18(+)	1.690 9	0.220 0	1.88×10^-28(+)
CSO_g4	3.834 7	0.158 2	1.23×10^-2(+)	1.666 5	0.174 1	4.51×10^-16(+)
CSO_g5	3.908 8	0.132 4	7.55×10^-21(+)	1.723 5	0.108 1	3.38×10^-42(+)
CSO_g10	3.907 6	0.151 6	3.15×10^-20(+)	1.716 2	0.214 8	9.01×10^-44(+)
CSO_g15	3.889 9	0.134 5	2.65×10^-17(+)	1.660 7	0.151 7	2.47×10^-17(+)
CSO_g20	3.888 2	0.157 3	3.81×10^-14(+)	1.657 0	0.170 7	4.07×10^-11(+)
w/l/d	8/0/0			8/0/0
MGCC_DE	3.448 2	0.112 1	—	1.582 7	0.084 8	—
DE	3.493 6	0.110 3	1.03×10^-4(+)	1.678 9	0.100 5	4.12×10^-27(+)
DE_g2	3.396 5	0.111 9	1.81×10^-6(-)	1.608 5	0.161 5	1.41×10^-5(+)
DE_g3	3.525 8	0.093 2	4.51×10^-5(+)	1.600 1	0.146 5	0.000 462(+)
DE_g4	3.517 3	0.159 0	3.45×10^-4(+)	1.588 4	0.115 2	0.647 967(≈)
DE_g5	3.401 0	0.126 2	5.13×10^-3(+)	1.618 3	0.138 1	1.32×10^-8(+)
DE_g10	3.477 5	0.230 0	2.32×10^-1(+)	1.647 1	0.109 2	5.71×10^-14(+)
DE_g15	3.420 4	0.130 9	3.67×10^-3(-)	1.535 7	0.133 2	1.39×10^-8(-)
DE_g20	3.535 1	0.219 1	2.16×10^-8(+)	1.660 8	0.142 4	1.19×10^-23(+)
w/l/d	6/2/0			6/1/1