First passage percolation on the Newman-Watts small world model

Onderzoeksoutput: Boek/rapportRapportAcademic

58 Downloads (Pure)

Uittreksel

The Newman-Watts model is given by taking a cycle graph of n vertices and then adding each possible edge $(i,j), |i-j|\neq 1 \mod n$ with probability $\rho/n$ for some $\rho>0$ constant. In this paper we add i.i.d. exponential edge weights to this graph, and investigate typical distances in the corresponding random metric space given by the least weight paths between vertices. We show that typical distances grow as $\frac1\lambda \log n$ for a $\lambda>0$ and determine the distribution of smaller order terms in terms of limits of branching process random variables. We prove that the number of edges along the shortest weight path follows a Central Limit Theorem, and show that in a corresponding epidemic spread model the fraction of infected vertices follows a deterministic curve with a random shift.
Originele taal-2Engels
Uitgeverijs.n.
Aantal pagina's29
StatusGepubliceerd - 2015

Publicatie series

NaamarXiv
Volume1506.07693 [math.PR]

Vingerafdruk

First-passage Percolation
Small World
Path
Branching process
Graph in graph theory
Central limit theorem
Metric space
Random variable
Model
Cycle
Curve
Term

Citeer dit

@book{88f0f4d98aa14dfbb9f5038df016efe6,
title = "First passage percolation on the Newman-Watts small world model",
abstract = "The Newman-Watts model is given by taking a cycle graph of n vertices and then adding each possible edge $(i,j), |i-j|\neq 1 \mod n$ with probability $\rho/n$ for some $\rho>0$ constant. In this paper we add i.i.d. exponential edge weights to this graph, and investigate typical distances in the corresponding random metric space given by the least weight paths between vertices. We show that typical distances grow as $\frac1\lambda \log n$ for a $\lambda>0$ and determine the distribution of smaller order terms in terms of limits of branching process random variables. We prove that the number of edges along the shortest weight path follows a Central Limit Theorem, and show that in a corresponding epidemic spread model the fraction of infected vertices follows a deterministic curve with a random shift.",
author = "J. Komj{\'a}thy and V. Vadon",
year = "2015",
language = "English",
series = "arXiv",
publisher = "s.n.",

}

First passage percolation on the Newman-Watts small world model. / Komjáthy, J.; Vadon, V.

s.n., 2015. 29 blz. (arXiv; Vol. 1506.07693 [math.PR]).

Onderzoeksoutput: Boek/rapportRapportAcademic

TY - BOOK

T1 - First passage percolation on the Newman-Watts small world model

AU - Komjáthy, J.

AU - Vadon, V.

PY - 2015

Y1 - 2015

N2 - The Newman-Watts model is given by taking a cycle graph of n vertices and then adding each possible edge $(i,j), |i-j|\neq 1 \mod n$ with probability $\rho/n$ for some $\rho>0$ constant. In this paper we add i.i.d. exponential edge weights to this graph, and investigate typical distances in the corresponding random metric space given by the least weight paths between vertices. We show that typical distances grow as $\frac1\lambda \log n$ for a $\lambda>0$ and determine the distribution of smaller order terms in terms of limits of branching process random variables. We prove that the number of edges along the shortest weight path follows a Central Limit Theorem, and show that in a corresponding epidemic spread model the fraction of infected vertices follows a deterministic curve with a random shift.

AB - The Newman-Watts model is given by taking a cycle graph of n vertices and then adding each possible edge $(i,j), |i-j|\neq 1 \mod n$ with probability $\rho/n$ for some $\rho>0$ constant. In this paper we add i.i.d. exponential edge weights to this graph, and investigate typical distances in the corresponding random metric space given by the least weight paths between vertices. We show that typical distances grow as $\frac1\lambda \log n$ for a $\lambda>0$ and determine the distribution of smaller order terms in terms of limits of branching process random variables. We prove that the number of edges along the shortest weight path follows a Central Limit Theorem, and show that in a corresponding epidemic spread model the fraction of infected vertices follows a deterministic curve with a random shift.

M3 - Report

T3 - arXiv

BT - First passage percolation on the Newman-Watts small world model

PB - s.n.

ER -