Polynomial growth in degree-dependent first passage percolation on spatial random graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912054415196160 |
|---|---|
| author | Komjáthy, Júlia Lapinskas, John Lengler, Johannes Schaller, Ulysse |
| author_facet | Komjáthy, Júlia Lapinskas, John Lengler, Johannes Schaller, Ulysse |
| contents | In this paper we study a version of (non-Markovian) first passage percolation on graphs, where the transmission time between two connected vertices is non-iid, but increases by a penalty factor polynomial in their expected degrees. Based on the exponent of the penalty-polynomial, this makes it increasingly harder to transmit to and from high-degree vertices. This choice is motivated by awareness or time-limitations. For the iid part of the transmission times we allow any nonnegative distribution with regularly varying behaviour at $0$. For the underlying graph models we choose spatial random graphs that have power-law degree distributions, so that the effect of the penalisation becomes visible: (finite and infinite) Geometric Inhomogeneous Random Graphs, and Scale-Free Percolation. In these spatial models, the connection probability between two vertices depends on their spatial distance and on their expected degrees. We prove that upon increasing the penalty exponent, the transmission time between two far away vertices $x,y$ sweeps through four universal phases even for a single underlying graph: explosive (tight transmission times), polylogarithmic, polynomial but sublinear ($|x-y|^{η_0+o(1)}$ for an explicit $η_0<1$), and linear ($Θ(|x-y|)$) in their Euclidean distance. Further, none of these phases are restricted to phase boundaries, and those are non-trivial in the main model parameters: the tail of the degree-distribution, a long-range parameter, and the exponent of regular variation of the iid part of the transmission times. In this paper we present proofs of lower bounds for the latter two phases and the upper bound for the linear phase. These complement the matching upper bounds for the polynomial regime in our companion paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_11880 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Polynomial growth in degree-dependent first passage percolation on spatial random graphs Komjáthy, Júlia Lapinskas, John Lengler, Johannes Schaller, Ulysse Probability Social and Information Networks Combinatorics Populations and Evolution 05C82, 60K35, 60K50, 82B43, 91D30, 91D25 In this paper we study a version of (non-Markovian) first passage percolation on graphs, where the transmission time between two connected vertices is non-iid, but increases by a penalty factor polynomial in their expected degrees. Based on the exponent of the penalty-polynomial, this makes it increasingly harder to transmit to and from high-degree vertices. This choice is motivated by awareness or time-limitations. For the iid part of the transmission times we allow any nonnegative distribution with regularly varying behaviour at $0$. For the underlying graph models we choose spatial random graphs that have power-law degree distributions, so that the effect of the penalisation becomes visible: (finite and infinite) Geometric Inhomogeneous Random Graphs, and Scale-Free Percolation. In these spatial models, the connection probability between two vertices depends on their spatial distance and on their expected degrees. We prove that upon increasing the penalty exponent, the transmission time between two far away vertices $x,y$ sweeps through four universal phases even for a single underlying graph: explosive (tight transmission times), polylogarithmic, polynomial but sublinear ($|x-y|^{η_0+o(1)}$ for an explicit $η_0<1$), and linear ($Θ(|x-y|)$) in their Euclidean distance. Further, none of these phases are restricted to phase boundaries, and those are non-trivial in the main model parameters: the tail of the degree-distribution, a long-range parameter, and the exponent of regular variation of the iid part of the transmission times. In this paper we present proofs of lower bounds for the latter two phases and the upper bound for the linear phase. These complement the matching upper bounds for the polynomial regime in our companion paper. |
| title | Polynomial growth in degree-dependent first passage percolation on spatial random graphs |
| topic | Probability Social and Information Networks Combinatorics Populations and Evolution 05C82, 60K35, 60K50, 82B43, 91D30, 91D25 |
| url | https://arxiv.org/abs/2309.11880 |