Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs

Júlia Komjáthy (Corresponding author), Bas Lodewijks (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

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.

Original languageEnglish
JournalStochastic Processes and their Applications
DOIs
Publication statusE-pub ahead of print - 14 May 2019

Fingerprint

Random Graphs
Explosion
Explosions
Branching process
Infinity
Random Geometric Graph
Spatial Networks
Infinite Variance
Path
Weight Distribution
Dependent
Power-law Distribution
Spatial Model
Rescaling
Scale-free Networks
Degree Distribution
Graph in graph theory
Vertex of a graph
Shortest path
Identically distributed

Keywords

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

Cite this

@article{276d4b17d01b457aa5286077941e9027,
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",

}

Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs. / Komjáthy, Júlia (Corresponding author); Lodewijks, Bas (Corresponding author).

In: Stochastic Processes and their Applications, 14.05.2019.

Research output: Contribution to journalArticleAcademicpeer-review

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

AN - SCOPUS:85066135827

JO - Stochastic Processes and their Applications

JF - Stochastic Processes and their Applications

SN - 0304-4149

ER -