求解网络风险传播问题的近似算法及其性能分析

作     者：张永铮 田志宏 方滨兴 云晓春 

作者机构：中国科学院计算技术研究所信息智能与信息安全研究中心北京100190 

出 版 物：《中国科学（E辑）》 (Science in China(Series E))

年 卷 期：2008年第38卷第8期

页      面：1157-1168页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 0839[工学-网络空间安全] 08[工学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：国家自然科学基金(批准号:60703021) 中国高技术研究发展计划(批准号:2007AA01Z444 2007AA010501 2007AA-01Z474)资助项目 

主　　题：风险评估 网络脆弱性 风险传播 近似算法 NP难题 

摘      要：在充分阐明风险传播研究意义的基础上,给出了网络风险传播问题的定义,证明了该问题是NP难题,并提出了一个基于邻近传播和最小入度的近似算法—APMI算法,该算法最坏时间复杂度为O(n3),最差近似比为O(n).最后通过模拟实验分析了网络规模、网络密度和风险源密度等3方面因素对APMI算法和现有精确算法RH的性能或准确性的影响.实验结果表明:RH算法的性能受网络密度影响很大(呈指数增长),受网络规模和风险源密度的影响较小;APMI算法将RH算法在网络较稠密时的指数时间复杂度降低为多项式时间,而其准确性指标Coefficient仍保持在0.995以上.