Random networks with sublinear preferential attachment: the giant component

Steffen Dereich, Peter Morters

Research output: Contribution to journalArticle

21 Citations (Scopus)
48 Downloads (Pure)

Abstract

We study a dynamical random network model in which at every construction step a new vertex is introduced and attached to every existing vertex independently with a probability proportional to a concave function f of its current degree. We give a criterion for the existence of a giant component, which is both necessary and sufficient, and which becomes explicit when f is linear. Otherwise it allows the derivation of explicit necessary and sufficient conditions, which are often fairly close. We give an explicit criterion to decide whether the giant component is robust under random removal of edges. We also determine asymptotically the size of the giant component and the empirical distribution of component sizes in terms of the survival probability and size distribution of a multitype branching random walk associated with f.
Original languageEnglish
Pages (from-to)329-384
Number of pages56
JournalAnnals of Probability
Volume41
Issue number1
DOIs
Publication statusPublished - Jan 2013

Fingerprint

Giant Component
Preferential Attachment
Random Networks
Branching Random Walk
Survival Distribution
Multitype
Empirical Distribution
Survival Probability
Concave function
Vertex of a graph
Network Model
Probability Distribution
Directly proportional
Sufficient
Necessary Conditions
Necessary
Sufficient Conditions

Cite this

Random networks with sublinear preferential attachment: the giant component. / Dereich, Steffen; Morters, Peter.

In: Annals of Probability, Vol. 41, No. 1, 01.2013, p. 329-384.

Research output: Contribution to journalArticle

Dereich, Steffen ; Morters, Peter. / Random networks with sublinear preferential attachment: the giant component. In: Annals of Probability. 2013 ; Vol. 41, No. 1. pp. 329-384.
@article{31834fc5e4824c0cbd257d166110a49b,
title = "Random networks with sublinear preferential attachment: the giant component",
abstract = "We study a dynamical random network model in which at every construction step a new vertex is introduced and attached to every existing vertex independently with a probability proportional to a concave function f of its current degree. We give a criterion for the existence of a giant component, which is both necessary and sufficient, and which becomes explicit when f is linear. Otherwise it allows the derivation of explicit necessary and sufficient conditions, which are often fairly close. We give an explicit criterion to decide whether the giant component is robust under random removal of edges. We also determine asymptotically the size of the giant component and the empirical distribution of component sizes in terms of the survival probability and size distribution of a multitype branching random walk associated with f.",
author = "Steffen Dereich and Peter Morters",
year = "2013",
month = "1",
doi = "10.1214/11-AOP697",
language = "English",
volume = "41",
pages = "329--384",
journal = "Annals of Probability",
issn = "0091-1798",
publisher = "Institute of Mathematical Statistics",
number = "1",

}

TY - JOUR

T1 - Random networks with sublinear preferential attachment: the giant component

AU - Dereich, Steffen

AU - Morters, Peter

PY - 2013/1

Y1 - 2013/1

N2 - We study a dynamical random network model in which at every construction step a new vertex is introduced and attached to every existing vertex independently with a probability proportional to a concave function f of its current degree. We give a criterion for the existence of a giant component, which is both necessary and sufficient, and which becomes explicit when f is linear. Otherwise it allows the derivation of explicit necessary and sufficient conditions, which are often fairly close. We give an explicit criterion to decide whether the giant component is robust under random removal of edges. We also determine asymptotically the size of the giant component and the empirical distribution of component sizes in terms of the survival probability and size distribution of a multitype branching random walk associated with f.

AB - We study a dynamical random network model in which at every construction step a new vertex is introduced and attached to every existing vertex independently with a probability proportional to a concave function f of its current degree. We give a criterion for the existence of a giant component, which is both necessary and sufficient, and which becomes explicit when f is linear. Otherwise it allows the derivation of explicit necessary and sufficient conditions, which are often fairly close. We give an explicit criterion to decide whether the giant component is robust under random removal of edges. We also determine asymptotically the size of the giant component and the empirical distribution of component sizes in terms of the survival probability and size distribution of a multitype branching random walk associated with f.

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

UR - http://dx.doi.org/10.1214/11-AOP697

UR - http://projecteuclid.org/euclid.aop/1358951989

U2 - 10.1214/11-AOP697

DO - 10.1214/11-AOP697

M3 - Article

VL - 41

SP - 329

EP - 384

JO - Annals of Probability

JF - Annals of Probability

SN - 0091-1798

IS - 1

ER -