How Robust is Scale-Free Structure? Phase Transitions in Preferential Attachment Model under Attack?
Abstract
Will an attack on a network affect its structure in a major way? In this work we study this question by investigating a dynamic preferential attachment-type graph in which an attacker interferes with the growth mechanism. We show that our model of an attack exhibits a phase transition. If the skill of the attacker is low, the network preserves its scale-free structure inherited from the underlying preferential attachment structure (even though the tail of the degree distribution becomes lighter due to the attack). When the skill of the attacker increases and crosses a critical boundary, the scale-free property is destroyed. The skill of the attacker is expressed as the probability that, at a given step, the attacker succeeds in preventing adding an edge to the network and, instead, causes a deletion (in a preferential manner) of an edge. In all cases we describe the tail behaviour of the degree distribution.
Related
- Spatial preferential attachment models: robustness revisited
- Persistent Hubs and Sharp Asymptotics in Eigenvector Preferential Attachment Trees
- Asymptotic Normality of the Hill Estimator in Linear Preferential Attachment
- Sublinear multi-type preferential attachment
- Cutoff for Simple Random Walk on Preferential Attachment Graphs
BibTeX
@misc{gong2026robust,
title = {{How Robust is Scale-Free Structure? Phase Transitions in Preferential Attachment Model under Attack?}},
author = {Xiaoyun Gong and Gennady Samorodnitsky},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10839},
eprint = {2609.10839},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10839},
}
RIS
TY - UNPB
TI - How Robust is Scale-Free Structure? Phase Transitions in Preferential Attachment Model under Attack?
AU - Xiaoyun Gong
AU - Gennady Samorodnitsky
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10839
UR - https://arxiv.org/abs/2609.10839
AB - Will an attack on a network affect its structure in a major way? In this work we study this question by investigating a dynamic preferential attachment-type graph in which an attacker interferes with the growth mechanism. We show that our model of an attack exhibits a phase transition. If the skill of the attacker is low, the network preserves its scale-free structure inherited from the underlying preferential attachment structure (even though the tail of the degree distribution becomes lighter due to the attack). When the skill of the attacker increases and crosses a critical boundary, the scale-free property is destroyed. The skill of the attacker is expressed as the probability that, at a given step, the attacker succeeds in preventing adding an edge to the network and, instead, causes a deletion (in a preferential manner) of an edge. In all cases we describe the tail behaviour of the degree distribution.
ER -