乔晓东，毛 志，邓宏钟

（国防科技大学 信息系统与管理学院，湖南 长沙 410073）

21 世纪以来，随着信息技术的飞速发展，人类社会加快了网络化进程。从Internet到www，从交通网络到通信网络，从电力网络到物流网络……可以说，我们被网络包围，几乎所有的复杂系统都可以抽象成网络模型，网络已成为人们生产、生活中不可缺少的一部分。

随着网络技术的不断发展与应用，对网络的定量与定性特征的科学理解，已成为网络时代科学研究中一个极其重要的挑战性课题，甚至被称为“网络的新科学”[1]。其中网络可靠性是对网络定量理解的一个非常重要的参数[2]，网络的可靠性也是保证系统正常运行的前提，因此很多先驱都投身研究网络的可靠性问题。网络就是有一些带有连边的节点组成。在网络可靠性的研究中，人们常常用概率图来表示网络，图的点和边都分配给正常运行的概率。早期对网络可靠性的算法研究主要为精确计算，算法包括状态枚举法、容斥原理法、不交积和法、因子分解法、随机过程法等等，这些精确算法随着网络单元数量和复杂程度的增加，计算难度成指数增长。以状态枚举法为例，对于一个不考虑节点失效的含有M条边的无向网络来说，共有2M个状态向量，计算量相当大，即使是计算机也难以在有意义的时间内完成计算，目前网络可靠度的精确算法只适用于规模较小的网络。可靠性度量参数的精确计算被Ball[3]等人证明为NP-hard问题后，研究人员开始了对近似算法的研究。