Local neighbourhoods for first-passage percolation on the configuration model

Steffen Dereich, Marcel Ortgiese

Research output: Contribution to journalArticle

8 Downloads (Pure)

Abstract

We consider first-passage percolation on the configuration model. Once the network has been generated each edge is assigned an i.i.d. weight modeling the passage time of a message along this edge. Then independently two vertices are chosen uniformly at random, a sender and a recipient, and all edges along the geodesic connecting the two vertices are coloured in red (in the case that both vertices are in the same component). In this article we prove local limit theorems for the coloured graph around the recipient in the spirit of Benjamini and Schramm. We consider the explosive regime, in which case the random distances are of finite order, and the Malthusian regime, in which case the random distances are of logarithmic order.
Original languageEnglish
Pages (from-to)485–501
Number of pages17
JournalJournal of Statistical Physics
Volume173
Issue number3-4
Early online date7 Apr 2018
DOIs
Publication statusPublished - 19 Nov 2018

Fingerprint

First-passage Percolation
apexes
Configuration
configurations
Passage Time
Colored Graph
Local Limit Theorem
messages
Geodesic
Logarithmic
theorems
Model
Modeling

Keywords

  • Branching processes
  • Configuration model
  • First passage percolation
  • Geodesics
  • Local limit
  • Random graphs

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics

Cite this

Local neighbourhoods for first-passage percolation on the configuration model. / Dereich, Steffen; Ortgiese, Marcel.

In: Journal of Statistical Physics, Vol. 173, No. 3-4, 19.11.2018, p. 485–501.

Research output: Contribution to journalArticle

@article{c11a1f7d9ca04b929be3a9a7e34416a4,
title = "Local neighbourhoods for first-passage percolation on the configuration model",
abstract = "We consider first-passage percolation on the configuration model. Once the network has been generated each edge is assigned an i.i.d. weight modeling the passage time of a message along this edge. Then independently two vertices are chosen uniformly at random, a sender and a recipient, and all edges along the geodesic connecting the two vertices are coloured in red (in the case that both vertices are in the same component). In this article we prove local limit theorems for the coloured graph around the recipient in the spirit of Benjamini and Schramm. We consider the explosive regime, in which case the random distances are of finite order, and the Malthusian regime, in which case the random distances are of logarithmic order.",
keywords = "Branching processes, Configuration model, First passage percolation, Geodesics, Local limit, Random graphs",
author = "Steffen Dereich and Marcel Ortgiese",
year = "2018",
month = "11",
day = "19",
doi = "10.1007/s10955-018-2028-7",
language = "English",
volume = "173",
pages = "485–501",
journal = "Journal of Statistical Physics",
issn = "0022-4715",
publisher = "Springer New York",
number = "3-4",

}

TY - JOUR

T1 - Local neighbourhoods for first-passage percolation on the configuration model

AU - Dereich, Steffen

AU - Ortgiese, Marcel

PY - 2018/11/19

Y1 - 2018/11/19

N2 - We consider first-passage percolation on the configuration model. Once the network has been generated each edge is assigned an i.i.d. weight modeling the passage time of a message along this edge. Then independently two vertices are chosen uniformly at random, a sender and a recipient, and all edges along the geodesic connecting the two vertices are coloured in red (in the case that both vertices are in the same component). In this article we prove local limit theorems for the coloured graph around the recipient in the spirit of Benjamini and Schramm. We consider the explosive regime, in which case the random distances are of finite order, and the Malthusian regime, in which case the random distances are of logarithmic order.

AB - We consider first-passage percolation on the configuration model. Once the network has been generated each edge is assigned an i.i.d. weight modeling the passage time of a message along this edge. Then independently two vertices are chosen uniformly at random, a sender and a recipient, and all edges along the geodesic connecting the two vertices are coloured in red (in the case that both vertices are in the same component). In this article we prove local limit theorems for the coloured graph around the recipient in the spirit of Benjamini and Schramm. We consider the explosive regime, in which case the random distances are of finite order, and the Malthusian regime, in which case the random distances are of logarithmic order.

KW - Branching processes

KW - Configuration model

KW - First passage percolation

KW - Geodesics

KW - Local limit

KW - Random graphs

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

U2 - 10.1007/s10955-018-2028-7

DO - 10.1007/s10955-018-2028-7

M3 - Article

VL - 173

SP - 485

EP - 501

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

SN - 0022-4715

IS - 3-4

ER -