Typical distances in ultrasmall random networks

Steffen Dereich, Christian Mönch, Peter Morters

Research output: Contribution to journalArticle

12 Citations (Scopus)
65 Downloads (Pure)

Abstract

We show that in preferential attachment models with power-law exponent τ ∈ (2, 3) the distance between randomly chosen vertices in the giant component is asymptotically equal to (4 + o(1))log log N / (-log(τ - 2)), where N denotes the number of nodes. This is twice the value obtained for the configuration model with the same power-law exponent. The extra factor reveals the different structure of typical shortest paths in preferential attachment graphs.
Original languageEnglish
Pages (from-to)583-601
JournalAdvances in Applied Probability
Volume44
Issue number2
DOIs
Publication statusPublished - Jun 2012

Fingerprint

Preferential Attachment
Random Networks
Power Law
Exponent
Giant Component
Shortest path
Denote
Configuration
Graph in graph theory
Vertex of a graph
Model

Cite this

Typical distances in ultrasmall random networks. / Dereich, Steffen; Mönch, Christian; Morters, Peter.

In: Advances in Applied Probability, Vol. 44, No. 2, 06.2012, p. 583-601.

Research output: Contribution to journalArticle

Dereich, Steffen ; Mönch, Christian ; Morters, Peter. / Typical distances in ultrasmall random networks. In: Advances in Applied Probability. 2012 ; Vol. 44, No. 2. pp. 583-601.
@article{bd53b0ced1c64f70a43f2e601bd1a521,
title = "Typical distances in ultrasmall random networks",
abstract = "We show that in preferential attachment models with power-law exponent τ ∈ (2, 3) the distance between randomly chosen vertices in the giant component is asymptotically equal to (4 + o(1))log log N / (-log(τ - 2)), where N denotes the number of nodes. This is twice the value obtained for the configuration model with the same power-law exponent. The extra factor reveals the different structure of typical shortest paths in preferential attachment graphs.",
author = "Steffen Dereich and Christian M{\"o}nch and Peter Morters",
year = "2012",
month = "6",
doi = "10.1239/aap/1339878725",
language = "English",
volume = "44",
pages = "583--601",
journal = "Advances in Applied Probability",
issn = "0001-8678",
publisher = "University of Sheffield",
number = "2",

}

TY - JOUR

T1 - Typical distances in ultrasmall random networks

AU - Dereich, Steffen

AU - Mönch, Christian

AU - Morters, Peter

PY - 2012/6

Y1 - 2012/6

N2 - We show that in preferential attachment models with power-law exponent τ ∈ (2, 3) the distance between randomly chosen vertices in the giant component is asymptotically equal to (4 + o(1))log log N / (-log(τ - 2)), where N denotes the number of nodes. This is twice the value obtained for the configuration model with the same power-law exponent. The extra factor reveals the different structure of typical shortest paths in preferential attachment graphs.

AB - We show that in preferential attachment models with power-law exponent τ ∈ (2, 3) the distance between randomly chosen vertices in the giant component is asymptotically equal to (4 + o(1))log log N / (-log(τ - 2)), where N denotes the number of nodes. This is twice the value obtained for the configuration model with the same power-law exponent. The extra factor reveals the different structure of typical shortest paths in preferential attachment graphs.

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

UR - http://dx.doi.org/10.1239/aap/1339878725

U2 - 10.1239/aap/1339878725

DO - 10.1239/aap/1339878725

M3 - Article

VL - 44

SP - 583

EP - 601

JO - Advances in Applied Probability

JF - Advances in Applied Probability

SN - 0001-8678

IS - 2

ER -