Heavy-tailed configuration models at criticality

Research output: Contribution to journalArticleAcademic

38 Downloads (Pure)

Abstract

We study the critical behavior of the component sizes for the configuration model when the tail of the degree distribution of a randomly chosen vertex is a regularly-varying function with exponent τ−1, where τ∈(3,4). The component sizes are shown to be of the order n(τ−2)/(τ−1)L(n)−1 for some slowly-varying function L(⋅). We show that the re-scaled ordered component sizes converge in distribution to the ordered excursions of a thinned L\'evy process. This proves that the scaling limits for the component sizes for these heavy-tailed configuration models are in a different universality class compared to the Erd\H{o}s-R\'enyi random graphs. Also the joint re-scaled vector of ordered component sizes and their surplus edges is shown to have a distributional limit under a strong topology. Our proof resolves a conjecture by Joseph, Ann. Appl. Probab. (2014) about the scaling limits of uniform simple graphs with i.i.d degrees in the critical window, and sheds light on the relation between the scaling limits obtained by Joseph and this paper, which appear to be quite different. Further, we use percolation to study the evolution of the component sizes and the surplus edges within the critical scaling window, which is shown to converge in finite dimension to the augmented multiplicative coalescent process introduced by Bhamidi et. al., Probab. Theory Related Fields (2014). The main results of this paper are proved under rather general assumptions on the vertex degrees. We also discuss how these assumptions are satisfied by some of the frameworks that have been studied previously.
Original languageEnglish
Article numberarXiv:1612.00650
Number of pages39
JournalarXiv
Publication statusPublished - 2016

Fingerprint

Criticality
Configuration
Scaling Limit
Regularly Varying Function
Model
Slowly Varying Function
Converge
Excursion
Vertex Degree
Degree Distribution
Critical Behavior
Simple Graph
Random Graphs
Universality
Tail
Resolve
Multiplicative
Exponent
Scaling
Topology

Cite this

@article{3162c334792246f8be072a945653f2ca,
title = "Heavy-tailed configuration models at criticality",
abstract = "We study the critical behavior of the component sizes for the configuration model when the tail of the degree distribution of a randomly chosen vertex is a regularly-varying function with exponent τ−1, where τ∈(3,4). The component sizes are shown to be of the order n(τ−2)/(τ−1)L(n)−1 for some slowly-varying function L(⋅). We show that the re-scaled ordered component sizes converge in distribution to the ordered excursions of a thinned L\'evy process. This proves that the scaling limits for the component sizes for these heavy-tailed configuration models are in a different universality class compared to the Erd\H{o}s-R\'enyi random graphs. Also the joint re-scaled vector of ordered component sizes and their surplus edges is shown to have a distributional limit under a strong topology. Our proof resolves a conjecture by Joseph, Ann. Appl. Probab. (2014) about the scaling limits of uniform simple graphs with i.i.d degrees in the critical window, and sheds light on the relation between the scaling limits obtained by Joseph and this paper, which appear to be quite different. Further, we use percolation to study the evolution of the component sizes and the surplus edges within the critical scaling window, which is shown to converge in finite dimension to the augmented multiplicative coalescent process introduced by Bhamidi et. al., Probab. Theory Related Fields (2014). The main results of this paper are proved under rather general assumptions on the vertex degrees. We also discuss how these assumptions are satisfied by some of the frameworks that have been studied previously.",
author = "S. Dhara and {van der Hofstad}, R.W. and {van Leeuwaarden}, J.S.H. and S. Sen",
year = "2016",
language = "English",
journal = "arXiv",
publisher = "Cornell University Library",

}

Heavy-tailed configuration models at criticality. / Dhara, S.; van der Hofstad, R.W.; van Leeuwaarden, J.S.H.; Sen, S.

In: arXiv, 2016.

Research output: Contribution to journalArticleAcademic

TY - JOUR

T1 - Heavy-tailed configuration models at criticality

AU - Dhara, S.

AU - van der Hofstad, R.W.

AU - van Leeuwaarden, J.S.H.

AU - Sen, S.

PY - 2016

Y1 - 2016

N2 - We study the critical behavior of the component sizes for the configuration model when the tail of the degree distribution of a randomly chosen vertex is a regularly-varying function with exponent τ−1, where τ∈(3,4). The component sizes are shown to be of the order n(τ−2)/(τ−1)L(n)−1 for some slowly-varying function L(⋅). We show that the re-scaled ordered component sizes converge in distribution to the ordered excursions of a thinned L\'evy process. This proves that the scaling limits for the component sizes for these heavy-tailed configuration models are in a different universality class compared to the Erd\H{o}s-R\'enyi random graphs. Also the joint re-scaled vector of ordered component sizes and their surplus edges is shown to have a distributional limit under a strong topology. Our proof resolves a conjecture by Joseph, Ann. Appl. Probab. (2014) about the scaling limits of uniform simple graphs with i.i.d degrees in the critical window, and sheds light on the relation between the scaling limits obtained by Joseph and this paper, which appear to be quite different. Further, we use percolation to study the evolution of the component sizes and the surplus edges within the critical scaling window, which is shown to converge in finite dimension to the augmented multiplicative coalescent process introduced by Bhamidi et. al., Probab. Theory Related Fields (2014). The main results of this paper are proved under rather general assumptions on the vertex degrees. We also discuss how these assumptions are satisfied by some of the frameworks that have been studied previously.

AB - We study the critical behavior of the component sizes for the configuration model when the tail of the degree distribution of a randomly chosen vertex is a regularly-varying function with exponent τ−1, where τ∈(3,4). The component sizes are shown to be of the order n(τ−2)/(τ−1)L(n)−1 for some slowly-varying function L(⋅). We show that the re-scaled ordered component sizes converge in distribution to the ordered excursions of a thinned L\'evy process. This proves that the scaling limits for the component sizes for these heavy-tailed configuration models are in a different universality class compared to the Erd\H{o}s-R\'enyi random graphs. Also the joint re-scaled vector of ordered component sizes and their surplus edges is shown to have a distributional limit under a strong topology. Our proof resolves a conjecture by Joseph, Ann. Appl. Probab. (2014) about the scaling limits of uniform simple graphs with i.i.d degrees in the critical window, and sheds light on the relation between the scaling limits obtained by Joseph and this paper, which appear to be quite different. Further, we use percolation to study the evolution of the component sizes and the surplus edges within the critical scaling window, which is shown to converge in finite dimension to the augmented multiplicative coalescent process introduced by Bhamidi et. al., Probab. Theory Related Fields (2014). The main results of this paper are proved under rather general assumptions on the vertex degrees. We also discuss how these assumptions are satisfied by some of the frameworks that have been studied previously.

M3 - Article

JO - arXiv

JF - arXiv

M1 - arXiv:1612.00650

ER -