A considerable amount of research effort has focused on developing metrics and approaches to assess network vulnerability. However, most of them neglect the network uncertainty arisen due to various reasons such as mobility and dynamics of the network, or noise introduced in data collection process. To this end, we introduce a framework to assess vulnerability of networks with uncertainty, modeling such networks as probabilistic graphs. We adopt expected pairwise connectivity (EPC) as a measure to quantify global connectivity and use it to formulate vulnerability assessment as a stochastic optimization problem. The objective is to identify a few number of critical nodes whose removal minimizes EPC in the residual network. While solutions for stochastic optimization problems are often limited to small networks, we present a practical solution that works for larger networks. The key advantages of our solution include 1) the application of a weighted averaging technique that avoids considering all, exponentially many, possible realizations of probabilistic graphs and 2) a Fully Polynomial Time Randomized Approximation Scheme (FPRAS) to efficiently estimate the EPC with any desired accuracy. Extensive experiments demonstrate significant improvement on performance of our solution over other heuristic approaches.
展开▼
