| 求解网络风险传播问题的近似算法及其性能分析 |
| |
| 引用本文： | 张永铮,;田志宏,;方滨兴,;云晓春.求解网络风险传播问题的近似算法及其性能分析[J].中国科学(E辑),2008(8):1157-1168. |
| |
| 作者姓名： | 张永铮 ;田志宏 ;方滨兴 ;云晓春 |
| |
| 作者单位： | [1]中国科学院计算技术研究所信息智能与信息安全研究中心,北京100190 |
| |
| 基金项目： | 国家自然科学基金（批准号：60703021）、中国高技术研究发展计划（批准号：2007AA01Z444,2007AA010501,2007AA-012474）资助项目 |
| |
| 摘 要： | 在充分阐明风险传播研究意义的基础上，给出了网络风险传播问题的定义，证明了该问题是NP难题，并提出了一个基于邻近传播和最小入度的近似算法——APMI算法，该算法最坏时间复杂度为O（n^3），最差近似比为D（n）．最后通过模拟实验分析了网络规模、网络密度和风险源密度等3方面因素对APMI算法和现有精确算法RH的性能或准确性的影响．实验结果表明：RH算法的性能受网络密度影响很大（呈指数增长），受网络规模和风险源密度的影响较小；APMI算法将RH算法在网络较稠密时的指数时间复杂度降低为多项式时间，而其准确性指标Coefficient仍保持在0．995以上．
|
| 关 键 词： | 风险评估 网络脆弱性 风险传播 近似算法 NP难题 |
| 本文献已被 维普 等数据库收录！ |
|
