Abstract
| Original language | English |
|---|---|
| Pages (from-to) | 1222-1267 |
| Journal | Electronic Journal of Probability |
| Volume | 14 |
| DOIs | |
| Publication status | Published - 3 Jun 2009 |
Fingerprint
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 journal › Article
}
TY - JOUR
T1 - Random networks with sublinear preferential attachment
T2 - degree evolutions
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 -