Node Reliability: Approximation, Upper Bounds, and Applications to Network Robustness
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918100469809152 |
|---|---|
| author | Liu, Xinhan Kooij, Robert Van Mieghem, Piet |
| author_facet | Liu, Xinhan Kooij, Robert Van Mieghem, Piet |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07636 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Node Reliability: Approximation, Upper Bounds, and Applications to Network Robustness Liu, Xinhan Kooij, Robert Van Mieghem, Piet Systems and Control Probability 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. |
| title | Node Reliability: Approximation, Upper Bounds, and Applications to Network Robustness |
| topic | Systems and Control Probability |
| url | https://arxiv.org/abs/2411.07636 |