Optimal shattering of complex networks
Abstract We consider optimal attacks or immunization schemes on different models of random graphs. We derive bounds for the minimum number of nodes needed to be removed from a network such that all remaining components are fragments of negligible size.We obtain bounds for different regimes of random...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2019-11-01
|
| Series: | Applied Network Science |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1007/s41109-019-0205-5 |
| Summary: | Abstract We consider optimal attacks or immunization schemes on different models of random graphs. We derive bounds for the minimum number of nodes needed to be removed from a network such that all remaining components are fragments of negligible size.We obtain bounds for different regimes of random regular graphs, Erdős-Rényi random graphs, and scale free networks, some of which are tight. We show that the performance of attacks by degree is bounded away from optimality.Finally we present a polynomial time attack algorithm and prove its optimal performance in certain cases. |
|---|---|
| ISSN: | 2364-8228 |