Node Reliability: Approximation, Upper Bounds, and Applications to Network Robustness
This paper discusses the reliability of a graph in which the links are perfectly reliable but the nodes may fail with certain probability p. Calculating graph node reliability is an NP-Hard problem. We introduce an efficient and accurate Monte Carlo method and a stochastic approximation for the node reliability polynomial based solely on the degree distribution. We provide the formulas for the node reliability polynomial of both Erdos-Renyi graphs and Random Geometric graphs. The phase transition in the node reliability of Erdos-Renyi graphs is also discussed. Additionally, we propose two increasingly accurate upper bounds for the node reliability polynomial solely based on the graph's degree distributions. The advantages and disadvantages of these two upper bounds are thoroughly compared. Beyond the computation of node reliability polynomials, we also estimate the number of cut sets and present a solution to the reliability-based network enhancement problem.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On best approximation by multivariate ridge functions with applications to generalized translation networks
We prove sharp upper and lower bounds for the approximation of Sobolev functions by sums of multivariate ridge functions, i.e., functions of the form $\mathbb{R}^d \ni x \mapsto \sum_{k=1}^n h_k(A_k x) \in \mathbb{R}$ wi…
Nearly Tight Bounds For Differentially Private Multiway Cut
Finding min $s$-$t$ cuts in graphs is a basic algorithmic tool, with applications in image segmentation, community detection, reinforcement learning, and data clustering. In this problem, we are given two nodes as termin…
Covering Numbers for Deep ReLU Networks with Applications to Function Approximation and Nonparametric Regression
Covering numbers of families of (deep) ReLU networks have been used to characterize their approximation-theoretic performance, upper-bound the prediction error they incur in nonparametric regression, and quantify their c…
QuantizationregressionUniversality and Approximation Rates of Graph Neural Networks with Random Features
We investigate message-passing graph neural networks with random node features. Random node features are known to enhance the expressiveness of graph neural networks (GNNs) both theoretically and empirically. Here, we es…
Coordination of DERs for Grid Reliability via Day-ahead Demand-Supply Power Bounds
A previous study has shown that coordinating DERs to protect the distribution grid can significantly reduce the infrastructure upgrades needed to address future increases in DER and electrification penetrations. Implemen…