Vulnerability of robust preferential attachment networks

M. Eckhoff, P Morters

Research output: Contribution to journalArticle

8 Citations (Scopus)
58 Downloads (Pure)

Abstract

Scale-free networks with small power law exponent are known to be robust, meaning that their qualitative topological structure cannot be altered by random removal of even a large proportion of nodes. By contrast, it has been argued in the science literature that such networks are highly vulnerable to a targeted attack, and removing a small number of key nodes in the network will dramatically change the topological structure. Here we analyse a class of preferential attachment networks in the robust regime and prove four main results supporting this claim: After removal of an arbitrarily small proportion $\ > 0$ of the oldest nodes (1) the asymptotic degree distribution has exponential instead of power law tails; (2) the largest degree in the network drops from being of the order of a power of the network size n to being just logarithmic in $n$; (3) the typical distances in the network increase from order log$\log n$ to $\order log n$; and (4) the network becomes vulnerable to random removal of nodes. Importantly, all our results explicitly quantify the dependence on the proportion $\varepsilon$of removed vertices. For example, we show that the critical proportion of nodes that have to be retained for survival of the giant component undergoes a steep increase as $\ moves away from zero, and a comparison of this result with similar ones for other networks reveals the existence of two different universality classes of robust network models. The key technique in our proofs is a local approximation of the network by a branching random walk with two killing boundaries, and an understanding of the particle genealogies in this process, which enters into estimates for the spectral radius of an associated operator

Original languageEnglish
Article number57
Pages (from-to)1-47
JournalElectronic Journal of Probability
Volume19
DOIs
Publication statusPublished - 5 Jul 2014

Fingerprint

Preferential Attachment
Vulnerability
Proportion
Vertex of a graph
Topological Structure
Power Law
Genealogy
Branching Random Walk
Giant Component
Local Approximation
Scale-free Networks
Degree Distribution
Spectral Radius
Universality
Network Model
Asymptotic distribution
Tail
Logarithmic
Quantify
Exponent

Cite this

Vulnerability of robust preferential attachment networks. / Eckhoff, M.; Morters, P.

In: Electronic Journal of Probability, Vol. 19, 57, 05.07.2014, p. 1-47.

Research output: Contribution to journalArticle

Eckhoff, M. ; Morters, P. / Vulnerability of robust preferential attachment networks. In: Electronic Journal of Probability. 2014 ; Vol. 19. pp. 1-47.
@article{f5b78832382143d18e72bdc4a237a453,
title = "Vulnerability of robust preferential attachment networks",
abstract = "Scale-free networks with small power law exponent are known to be robust, meaning that their qualitative topological structure cannot be altered by random removal of even a large proportion of nodes. By contrast, it has been argued in the science literature that such networks are highly vulnerable to a targeted attack, and removing a small number of key nodes in the network will dramatically change the topological structure. Here we analyse a class of preferential attachment networks in the robust regime and prove four main results supporting this claim: After removal of an arbitrarily small proportion $\ > 0$ of the oldest nodes (1) the asymptotic degree distribution has exponential instead of power law tails; (2) the largest degree in the network drops from being of the order of a power of the network size n to being just logarithmic in $n$; (3) the typical distances in the network increase from order log$\log n$ to $\order log n$; and (4) the network becomes vulnerable to random removal of nodes. Importantly, all our results explicitly quantify the dependence on the proportion $\varepsilon$of removed vertices. For example, we show that the critical proportion of nodes that have to be retained for survival of the giant component undergoes a steep increase as $\ moves away from zero, and a comparison of this result with similar ones for other networks reveals the existence of two different universality classes of robust network models. The key technique in our proofs is a local approximation of the network by a branching random walk with two killing boundaries, and an understanding of the particle genealogies in this process, which enters into estimates for the spectral radius of an associated operator",
author = "M. Eckhoff and P Morters",
year = "2014",
month = "7",
day = "5",
doi = "10.1214/EJP.v19-2974",
language = "English",
volume = "19",
pages = "1--47",
journal = "Electronic Journal of Probability",
issn = "1083-6489",
publisher = "Institute of Mathematical Statistics",

}

TY - JOUR

T1 - Vulnerability of robust preferential attachment networks

AU - Eckhoff, M.

AU - Morters, P

PY - 2014/7/5

Y1 - 2014/7/5

N2 - Scale-free networks with small power law exponent are known to be robust, meaning that their qualitative topological structure cannot be altered by random removal of even a large proportion of nodes. By contrast, it has been argued in the science literature that such networks are highly vulnerable to a targeted attack, and removing a small number of key nodes in the network will dramatically change the topological structure. Here we analyse a class of preferential attachment networks in the robust regime and prove four main results supporting this claim: After removal of an arbitrarily small proportion $\ > 0$ of the oldest nodes (1) the asymptotic degree distribution has exponential instead of power law tails; (2) the largest degree in the network drops from being of the order of a power of the network size n to being just logarithmic in $n$; (3) the typical distances in the network increase from order log$\log n$ to $\order log n$; and (4) the network becomes vulnerable to random removal of nodes. Importantly, all our results explicitly quantify the dependence on the proportion $\varepsilon$of removed vertices. For example, we show that the critical proportion of nodes that have to be retained for survival of the giant component undergoes a steep increase as $\ moves away from zero, and a comparison of this result with similar ones for other networks reveals the existence of two different universality classes of robust network models. The key technique in our proofs is a local approximation of the network by a branching random walk with two killing boundaries, and an understanding of the particle genealogies in this process, which enters into estimates for the spectral radius of an associated operator

AB - Scale-free networks with small power law exponent are known to be robust, meaning that their qualitative topological structure cannot be altered by random removal of even a large proportion of nodes. By contrast, it has been argued in the science literature that such networks are highly vulnerable to a targeted attack, and removing a small number of key nodes in the network will dramatically change the topological structure. Here we analyse a class of preferential attachment networks in the robust regime and prove four main results supporting this claim: After removal of an arbitrarily small proportion $\ > 0$ of the oldest nodes (1) the asymptotic degree distribution has exponential instead of power law tails; (2) the largest degree in the network drops from being of the order of a power of the network size n to being just logarithmic in $n$; (3) the typical distances in the network increase from order log$\log n$ to $\order log n$; and (4) the network becomes vulnerable to random removal of nodes. Importantly, all our results explicitly quantify the dependence on the proportion $\varepsilon$of removed vertices. For example, we show that the critical proportion of nodes that have to be retained for survival of the giant component undergoes a steep increase as $\ moves away from zero, and a comparison of this result with similar ones for other networks reveals the existence of two different universality classes of robust network models. The key technique in our proofs is a local approximation of the network by a branching random walk with two killing boundaries, and an understanding of the particle genealogies in this process, which enters into estimates for the spectral radius of an associated operator

UR - http://www.scopus.com/inward/record.url?scp=84903886541&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1214/EJP.v19-2974

U2 - 10.1214/EJP.v19-2974

DO - 10.1214/EJP.v19-2974

M3 - Article

VL - 19

SP - 1

EP - 47

JO - Electronic Journal of Probability

JF - Electronic Journal of Probability

SN - 1083-6489

M1 - 57

ER -