First passage percolation in sparse random graphs with boundary weights

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Standard

First passage percolation in sparse random graphs with boundary weights. / Leskelä, Lasse; Ngo, Hoa.

julkaisussa: Journal of Applied Probability, Vuosikerta 56, Nro 2, 30.07.2019, s. 458-471.

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Harvard

APA

Vancouver

Author

Bibtex - Lataa

@article{d9894d85da2645d09c7689139bf54799,
title = "First passage percolation in sparse random graphs with boundary weights",
abstract = "A large and sparse random graph with independent exponentially distributed link weights can be used to model the propagation of messages or diseases in a network with an unknown connectivity structure. In this article we study an extended setting where also the nodes of the graph are equipped with nonnegative random weights which are used to model the effect of boundary delays across paths in the network. Our main results provide approximative formulas for typical first passage times, typical flooding times, and maximum flooding times in the extended setting, over a time scale logarithmic with respect to the network size.",
author = "Lasse Leskel{\"a} and Hoa Ngo",
year = "2019",
month = "7",
day = "30",
doi = "10.1017/jpr.2019.30",
language = "English",
volume = "56",
pages = "458--471",
journal = "Journal of Applied Probability",
issn = "0021-9002",
publisher = "University of Sheffield",
number = "2",

}

RIS - Lataa

TY - JOUR

T1 - First passage percolation in sparse random graphs with boundary weights

AU - Leskelä, Lasse

AU - Ngo, Hoa

PY - 2019/7/30

Y1 - 2019/7/30

N2 - A large and sparse random graph with independent exponentially distributed link weights can be used to model the propagation of messages or diseases in a network with an unknown connectivity structure. In this article we study an extended setting where also the nodes of the graph are equipped with nonnegative random weights which are used to model the effect of boundary delays across paths in the network. Our main results provide approximative formulas for typical first passage times, typical flooding times, and maximum flooding times in the extended setting, over a time scale logarithmic with respect to the network size.

AB - A large and sparse random graph with independent exponentially distributed link weights can be used to model the propagation of messages or diseases in a network with an unknown connectivity structure. In this article we study an extended setting where also the nodes of the graph are equipped with nonnegative random weights which are used to model the effect of boundary delays across paths in the network. Our main results provide approximative formulas for typical first passage times, typical flooding times, and maximum flooding times in the extended setting, over a time scale logarithmic with respect to the network size.

U2 - 10.1017/jpr.2019.30

DO - 10.1017/jpr.2019.30

M3 - Article

VL - 56

SP - 458

EP - 471

JO - Journal of Applied Probability

JF - Journal of Applied Probability

SN - 0021-9002

IS - 2

ER -

ID: 33636837