论文标题
不确定图中有效的网络可靠性计算
Efficient Network Reliability Computation in Uncertain Graphs
论文作者
论文摘要
网络可靠性是评估不确定图中给定顶点之间连接性的重要指标。由于网络可靠性问题被称为＃p-complete，因此现有研究使用了近似技术。在本文中，我们提出了一种新的基于抽样的方法，可有效，准确地近似网络可靠性。我们的方法通过减少基于分层抽样的样品数量来提高效率。从理论上讲，我们可以通过使用网络可靠性的下限和上限来提高近似值的准确性，即使它减少了样品数量。为了有效计算边界，我们开发了一个扩展的BDD，称为S2BDD。在构造S2BDD时，我们的方法采用动态编程来有效地采样可能的图形。我们对真实数据集的实验表明，我们的方法的速度比现有的基于采样的方法的速度高出51.2倍。
Network reliability is an important metric to evaluate the connectivity among given vertices in uncertain graphs. Since the network reliability problem is known as #P-complete, existing studies have used approximation techniques. In this paper, we propose a new sampling-based approach that efficiently and accurately approximates network reliability. Our approach improves efficiency by reducing the number of samples based on stratified sampling. We theoretically guarantee that our approach improves the accuracy of approximation by using lower and upper bounds of network reliability, even though it reduces the number of samples. To efficiently compute the bounds, we develop an extended BDD, called S2BDD. During constructing the S2BDD, our approach employs dynamic programming for efficiently sampling possible graphs. Our experiment with real datasets demonstrates that our approach is up to 51.2 times faster than the existing sampling-based approach with higher accuracy.
