Random networks with sublinear preferential attachment: degree evolutions

S Dereich, Peter Morters

Research output: Contribution to journalArticle

  • 29 Citations

Abstract

We define a dynamic model of random networks, where new vertices are connected to old ones with a probability proportional to a sublinear function of their degree. We first give a strong limit law for the empirical degree distribution, and then have a closer look at the temporal evolution of the degrees of individual vertices, which we describe in terms of large and moderate deviation principles. Using these results, we expose an interesting phase transition: in cases of strong preference of large degrees, eventually a single vertex emerges forever as vertex of maximal degree, whereas in cases of weak preference, the vertex of maximal degree is changing infinitely often. Loosely speaking, the transition between the two phases occurs in the case when a new edge is attached to an existing vertex with a probability proportional to the root of its current degree.
LanguageEnglish
Pages1222-1267
JournalElectronic Journal of Probability
Volume14
DOIs
StatusPublished - 3 Jun 2009

Fingerprint

Preferential Attachment
Random Networks
Vertex of a graph
Directly proportional
Moderate Deviations
Limit Laws
Empirical Distribution
Degree Distribution
Large Deviations
Dynamic Model
Phase Transition
Roots
Deviation
Phase transition

Keywords

  • dynamic random graphs
  • degree distribution
  • maximal degree
  • sublinear preferential attachment
  • moderate deviation principle
  • large deviation principle
  • Barabasi-Albert model

Cite this

Random networks with sublinear preferential attachment : degree evolutions. / Dereich, S; Morters, Peter.

In: Electronic Journal of Probability, Vol. 14, 03.06.2009, p. 1222-1267.

Research output: Contribution to journalArticle

@article{6542b314054242b59b1a1d488ea3d523,
title = "Random networks with sublinear preferential attachment: degree evolutions",
abstract = "We define a dynamic model of random networks, where new vertices are connected to old ones with a probability proportional to a sublinear function of their degree. We first give a strong limit law for the empirical degree distribution, and then have a closer look at the temporal evolution of the degrees of individual vertices, which we describe in terms of large and moderate deviation principles. Using these results, we expose an interesting phase transition: in cases of strong preference of large degrees, eventually a single vertex emerges forever as vertex of maximal degree, whereas in cases of weak preference, the vertex of maximal degree is changing infinitely often. Loosely speaking, the transition between the two phases occurs in the case when a new edge is attached to an existing vertex with a probability proportional to the root of its current degree.",
keywords = "dynamic random graphs, degree distribution, maximal degree, sublinear preferential attachment, moderate deviation principle, large deviation principle, Barabasi-Albert model",
author = "S Dereich and Peter Morters",
note = "ID number: Article Number 43",
year = "2009",
month = "6",
day = "3",
doi = "10.1214/EJP.v14-647",
language = "English",
volume = "14",
pages = "1222--1267",
journal = "Electronic Journal of Probability",
issn = "1083-6489",
publisher = "Institute of Mathematical Statistics",

}

TY - JOUR

T1 - Random networks with sublinear preferential attachment

T2 - Electronic Journal of Probability

AU - Dereich,S

AU - Morters,Peter

N1 - ID number: Article Number 43

PY - 2009/6/3

Y1 - 2009/6/3

N2 - We define a dynamic model of random networks, where new vertices are connected to old ones with a probability proportional to a sublinear function of their degree. We first give a strong limit law for the empirical degree distribution, and then have a closer look at the temporal evolution of the degrees of individual vertices, which we describe in terms of large and moderate deviation principles. Using these results, we expose an interesting phase transition: in cases of strong preference of large degrees, eventually a single vertex emerges forever as vertex of maximal degree, whereas in cases of weak preference, the vertex of maximal degree is changing infinitely often. Loosely speaking, the transition between the two phases occurs in the case when a new edge is attached to an existing vertex with a probability proportional to the root of its current degree.

AB - We define a dynamic model of random networks, where new vertices are connected to old ones with a probability proportional to a sublinear function of their degree. We first give a strong limit law for the empirical degree distribution, and then have a closer look at the temporal evolution of the degrees of individual vertices, which we describe in terms of large and moderate deviation principles. Using these results, we expose an interesting phase transition: in cases of strong preference of large degrees, eventually a single vertex emerges forever as vertex of maximal degree, whereas in cases of weak preference, the vertex of maximal degree is changing infinitely often. Loosely speaking, the transition between the two phases occurs in the case when a new edge is attached to an existing vertex with a probability proportional to the root of its current degree.

KW - dynamic random graphs

KW - degree distribution

KW - maximal degree

KW - sublinear preferential attachment

KW - moderate deviation principle

KW - large deviation principle

KW - Barabasi-Albert model

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

UR - http://www.math.washington.edu/~ejpecp/

UR - http://dx.doi.org/10.1214/EJP.v14-647

U2 - 10.1214/EJP.v14-647

DO - 10.1214/EJP.v14-647

M3 - Article

VL - 14

SP - 1222

EP - 1267

JO - Electronic Journal of Probability

JF - Electronic Journal of Probability

SN - 1083-6489

ER -