Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs

Júlia Komjáthy, Bas Lodewijks

Research output: Contribution to journalArticle

Abstract

In this paper we study weighted distances in scale-free spatial network models: hyperbolic random graphs, geometric inhomogeneous random graphs and scale-free percolation. In hyperbolic random graphs, n=Θ(eR∕2)vertices are sampled independently from the hyperbolic disk with radius R and two vertices are connected either when they are within hyperbolic distance R, or independently with a probability depending on the hyperbolic distance. In geometric inhomogeneous random graphs, and in scale-free percolation, each vertex is given an independent weight and location from an underlying measured metric space and Zd, respectively, and two vertices are connected independently with a probability that is a function of their distance and their weights. We assign independent and identically distributed (i.i.d.)weights to the edges of the obtained random graphs, and investigate the weighted distance (the length of the shortest weighted path)between two uniformly chosen vertices, called typical weighted distance. In scale-free percolation, we study the weighted distance from the origin of vertex-sequences with norm tending to infinity. In particular, we study the case when the parameters are so that the degree distribution in the graph follows a power law with exponent τ∈(2,3)(infinite variance), and the edge-weight distribution is such that it produces an explosive age-dependent branching process with power-law offspring distribution, that is, the branching process produces infinitely many individuals in finite time. We show that in all three models, typical distances within the giant/infinite component converge in distribution, that is, no re-scaling is necessary. This solves an open question in Hofstad and Komjáthy (2017). The main tools of our proof are to develop elaborate couplings of the models to infinite versions, to follow the shortest paths to infinity and then to connect these paths by using weight-dependent percolation on the graphs, that is, we delete edges attached to vertices with higher weight with higher probability. We realise the percolation using the edge-weights: only very short edges connected to high weight vertices are allowed to stay, hence establishing arbitrarily short upper bounds for connections.

LanguageEnglish
JournalStochastic Processes and their Applications
Early online date14 May 2019
DOIs
StatusE-pub ahead of print - 14 May 2019

Keywords

  • First passage percolation
  • Hyperbolic random graphs
  • Scale-free property
  • Small world property
  • Spatial network models
  • Typical distances

ASJC Scopus subject areas

  • Statistics and Probability
  • Modelling and Simulation
  • Applied Mathematics

Cite this

@article{96447ec0d8be4bda8e37d568fdd2db04,
title = "Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs",
abstract = "In this paper we study weighted distances in scale-free spatial network models: hyperbolic random graphs, geometric inhomogeneous random graphs and scale-free percolation. In hyperbolic random graphs, n=Θ(eR∕2)vertices are sampled independently from the hyperbolic disk with radius R and two vertices are connected either when they are within hyperbolic distance R, or independently with a probability depending on the hyperbolic distance. In geometric inhomogeneous random graphs, and in scale-free percolation, each vertex is given an independent weight and location from an underlying measured metric space and Zd, respectively, and two vertices are connected independently with a probability that is a function of their distance and their weights. We assign independent and identically distributed (i.i.d.)weights to the edges of the obtained random graphs, and investigate the weighted distance (the length of the shortest weighted path)between two uniformly chosen vertices, called typical weighted distance. In scale-free percolation, we study the weighted distance from the origin of vertex-sequences with norm tending to infinity. In particular, we study the case when the parameters are so that the degree distribution in the graph follows a power law with exponent τ∈(2,3)(infinite variance), and the edge-weight distribution is such that it produces an explosive age-dependent branching process with power-law offspring distribution, that is, the branching process produces infinitely many individuals in finite time. We show that in all three models, typical distances within the giant/infinite component converge in distribution, that is, no re-scaling is necessary. This solves an open question in Hofstad and Komj{\'a}thy (2017). The main tools of our proof are to develop elaborate couplings of the models to infinite versions, to follow the shortest paths to infinity and then to connect these paths by using weight-dependent percolation on the graphs, that is, we delete edges attached to vertices with higher weight with higher probability. We realise the percolation using the edge-weights: only very short edges connected to high weight vertices are allowed to stay, hence establishing arbitrarily short upper bounds for connections.",
keywords = "First passage percolation, Hyperbolic random graphs, Scale-free property, Small world property, Spatial network models, Typical distances",
author = "J{\'u}lia Komj{\'a}thy and Bas Lodewijks",
year = "2019",
month = "5",
day = "14",
doi = "10.1016/j.spa.2019.04.014",
language = "English",
journal = "Stochastic Processes and their Applications",
issn = "0304-4149",
publisher = "Elsevier",

}

TY - JOUR

T1 - Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs

AU - Komjáthy, Júlia

AU - Lodewijks, Bas

PY - 2019/5/14

Y1 - 2019/5/14

N2 - In this paper we study weighted distances in scale-free spatial network models: hyperbolic random graphs, geometric inhomogeneous random graphs and scale-free percolation. In hyperbolic random graphs, n=Θ(eR∕2)vertices are sampled independently from the hyperbolic disk with radius R and two vertices are connected either when they are within hyperbolic distance R, or independently with a probability depending on the hyperbolic distance. In geometric inhomogeneous random graphs, and in scale-free percolation, each vertex is given an independent weight and location from an underlying measured metric space and Zd, respectively, and two vertices are connected independently with a probability that is a function of their distance and their weights. We assign independent and identically distributed (i.i.d.)weights to the edges of the obtained random graphs, and investigate the weighted distance (the length of the shortest weighted path)between two uniformly chosen vertices, called typical weighted distance. In scale-free percolation, we study the weighted distance from the origin of vertex-sequences with norm tending to infinity. In particular, we study the case when the parameters are so that the degree distribution in the graph follows a power law with exponent τ∈(2,3)(infinite variance), and the edge-weight distribution is such that it produces an explosive age-dependent branching process with power-law offspring distribution, that is, the branching process produces infinitely many individuals in finite time. We show that in all three models, typical distances within the giant/infinite component converge in distribution, that is, no re-scaling is necessary. This solves an open question in Hofstad and Komjáthy (2017). The main tools of our proof are to develop elaborate couplings of the models to infinite versions, to follow the shortest paths to infinity and then to connect these paths by using weight-dependent percolation on the graphs, that is, we delete edges attached to vertices with higher weight with higher probability. We realise the percolation using the edge-weights: only very short edges connected to high weight vertices are allowed to stay, hence establishing arbitrarily short upper bounds for connections.

AB - In this paper we study weighted distances in scale-free spatial network models: hyperbolic random graphs, geometric inhomogeneous random graphs and scale-free percolation. In hyperbolic random graphs, n=Θ(eR∕2)vertices are sampled independently from the hyperbolic disk with radius R and two vertices are connected either when they are within hyperbolic distance R, or independently with a probability depending on the hyperbolic distance. In geometric inhomogeneous random graphs, and in scale-free percolation, each vertex is given an independent weight and location from an underlying measured metric space and Zd, respectively, and two vertices are connected independently with a probability that is a function of their distance and their weights. We assign independent and identically distributed (i.i.d.)weights to the edges of the obtained random graphs, and investigate the weighted distance (the length of the shortest weighted path)between two uniformly chosen vertices, called typical weighted distance. In scale-free percolation, we study the weighted distance from the origin of vertex-sequences with norm tending to infinity. In particular, we study the case when the parameters are so that the degree distribution in the graph follows a power law with exponent τ∈(2,3)(infinite variance), and the edge-weight distribution is such that it produces an explosive age-dependent branching process with power-law offspring distribution, that is, the branching process produces infinitely many individuals in finite time. We show that in all three models, typical distances within the giant/infinite component converge in distribution, that is, no re-scaling is necessary. This solves an open question in Hofstad and Komjáthy (2017). The main tools of our proof are to develop elaborate couplings of the models to infinite versions, to follow the shortest paths to infinity and then to connect these paths by using weight-dependent percolation on the graphs, that is, we delete edges attached to vertices with higher weight with higher probability. We realise the percolation using the edge-weights: only very short edges connected to high weight vertices are allowed to stay, hence establishing arbitrarily short upper bounds for connections.

KW - First passage percolation

KW - Hyperbolic random graphs

KW - Scale-free property

KW - Small world property

KW - Spatial network models

KW - Typical distances

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

U2 - 10.1016/j.spa.2019.04.014

DO - 10.1016/j.spa.2019.04.014

M3 - Article

JO - Stochastic Processes and their Applications

T2 - Stochastic Processes and their Applications

JF - Stochastic Processes and their Applications

SN - 0304-4149

ER -