Source-linked AI summary
Percolation of localized attack on complex networks
Shuai Shao, Xuqing Huang, H Eugene Stanley, Shlomo Havlin
TL;DR
The paper addresses how complex networks withstand localized attacks, which are not adequately represented by random or hub-targeted attack models. It develops a percolation framework and applies it to network robustness, including real-world networks. In those tests, localized attacks collapse networks after much smaller node failures than random attacks.
Problem
Localized attacks affecting neighboring nodes are insufficiently captured by the predominantly studied random and hub-targeted attack models, despite their relevance to real-world network damage.
Method
The paper develops a percolation framework that models localized attacks through staged removal of attacked nodes and links connecting them to the remaining network.
Results
30% airline-network and 55% peer-to-peer-network node failure can cause collapse under localized attack, versus 98% and 90% under random attack.
Takeaways & Limitations
Localized attack is significantly more harmful to the tested real-world scale-free networks than random attack.
Abstract
from arXiv · showhide
The robustness of complex networks against node failure and malicious attack has been of interest for decades, while most of the research has focused on random attack or hub-targeted attack. In many real-world scenarios, however, attacks are neither random nor hub-targeted, but localized, where a group of neighboring nodes in a network are attacked and fail. In this paper we develop a percolation framework to analytically and numerically study the robustness of complex networks against such localized attack. In particular, we investigate this robustness in Erdős-Rényi networks, random-regular networks, and scale-free networks. Our results provide insight into how to better protect networks, enhance cybersecurity, and facilitate the design of more robust infrastructures.
(Supplementary Information)
The supplementary-information passage identifies the authors, affiliations, and document date.
- The paper lists Shuai Shao, Xuqing Huang, H. Eugene Stanley, and Shlomo Havlin as authors.
- The authors are affiliated with Boston University and Bar-Ilan University.
- The document is dated December 11, 2014.
I. THEORETICAL DERIVATION OF THE GENERATING FUNCTION OF THE REMAINING NETWORK AFTER LOCALIZED ATTACK
The framework derives the remaining network after localized attack in two stages: node removal followed by removal of links leading into the attacked region. It uses generating functions to characterize the resulting degree distribution and network structure.
- Two-stage derivation: The localized attack derivation first removes nodes in the attacked area while retaining links to remaining nodes, then removes those links.
- Remaining-node distribution: The remaining-node degree distribution is represented by Pp(k), with Ap(k) tracking the number of remaining nodes of degree k.
- Generating-function derivation: Differentiating the governing relation and solving it yields the average degree and generating function of the remaining network after node removal.
- Link removal: Links from remaining nodes into the removed region are treated as randomly removed because the network is randomly connected.
- Post-attack network: The probability that a remaining-network link ends at an unremoved node defines an effective retained-link fraction, and the resulting generating function describes the post-attack network.
II. ROBUSTNESS OF REAL-WORLD NETWORKS AGAINST LOCALIZED ATTACK
The real-world tests compare localized and random attacks on peer-to-peer and airline networks. Localized attacks collapse both networks after substantially smaller node failures than random attacks.
- Real-world networks: The study tests localized and random attacks on a peer-to-peer computer network and a global airline route network.
- Scale-free interpretation: The real-world networks approximately follow power-law degree distributions, supporting comparison with scale-free-network results.
- Localized attack: 30% node failure collapses the global airline route network, while 55% disables the peer-to-peer computer network under localized attack.
- Random attack: Under random attack, collapse requires 98% node failure in the airline network and 90% in the peer-to-peer network.
- Comparison: Localized attack is significantly more harmful to the tested real-world scale-free networks than random attack.