广播网络病毒进化模型算法研究  

Study of epidemic evolution optimization algorithm in broadcasting networks

作　　者：郭红转[1] 杨艳燕[1] 赵佳佳[2] 任平安[2] 

机构地区：[1]南阳理工学院计算机与信息工程学院,河南南阳473004 [2]陕西师范大学计算机科学学院,西安710062

出　　处：《计算机应用研究》2014年第11期3455-3459,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61070189);河南省科技攻关资助项目(112102210500)

摘　　要：病毒进化优化对计算机或生物病毒在网络系统中的扩散过程进行研究,是在有限网络资源情况下对病毒进化速度进行控制和研究网络用户如何被感染的行为。病毒进化优化通过连通图上的动态概率系统来建模,传统的病毒进化模型中对于病毒的进化模型进行描述时,需要解决一个以非负矩阵的谱半径为优化目标的非凸优化问题。基于此,提出了两类新的近似算法:第一种算法基于连续凸近似,为次优算法,但计算速度较快;第二种为基于分支定界的全局最优计算方法,通过非负矩阵的关键不等式获取全局最优解。通过和传统的进化模型进行仿真实验,仿真实验结果表明,新的算法能够使病毒进化过程收敛到全局最优值,并且在不同网络环境下均具有快速的收敛性能。Epidemic evolution optimization studies the spreading process of a computer or biological virus in a network.It controls the epidemic evolution rate under limited network resources and to study how the network users are to be infected. Epidemic evolution can be modeled by a dynamic probabilistic system over a connected graph.Traditional epidemic evolution models require solving a non-convex optimization problem objected at the spectral radius of a non-negative matrix.To solve this optimization problem,this paper proposed two algorithms.Based on the successive convex approximation,the first one was sub-optimal but computationally fast;the second one could compute the global optimal solution by using branch-and-bound tech-niques that leverage some key tools of non-negative matrix theory.Simulation results based on traditional evolutional models show that the algorithm can make the epidemic evolution process converge to the global optimal,and has a fast convergence rate under different network environments.

关 键 词：病毒进化 谱半径最小化 非负矩阵理论 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]