Strong couplings for static locally tree-like random graphs

DOI10.1017/JPR.2022.17MaRDI QIDQ5049908zbMATH OpenOpenAlexFDO

Authors Mariana Olvera-Cravioto

Publication date 14 November 2022

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.10673

zbMATH Keywords

complex networksconfiguration modelGalton-Watson processesinhomogeneous random graphlocal-weak limitsrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: The goal of this paper is to provide a general purpose result for the coupling of exploration processes of random graphs, both undirected and directed, with their local weak limits when this limit is a marked Galton-Watson process. This class includes in particular the configuration model and the family of inhomogeneous random graphs with rank-1 kernel. Vertices in the graph are allowed to have attributes on a general separable metric space and can potentially influence the construction of the graph itself. The coupling holds for any fixed depth of a breadth-first exploration process.

Recommendations

• On local weak limit and subgraph counts for sparse random graphs
• Optimal couplings between sparse block models
• Typical distances in the directed configuration model
• The coupling method for inhomogeneous random intersection graphs.
• Publication:4729111

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Connected components in random graphs with given expected degree sequences
• Directed random graphs with given degree distributions
• Distances in random graphs with finite variance degrees
• Generalized PageRank on directed configuration networks
• Generating simple random graphs with prescribed degree distribution
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• Local weak convergence for PageRank
• On a conditionally Poissonian graph process
• Optimal Transport
• PageRank's behavior under degree correlations
• Processes on unimodular random networks
• Random graph dynamics
• Random graphs and complex networks. Volume 1
• Random graphs.
• The phase transition in inhomogeneous random graphs

Cited in

(3)

• Concentration inequalities from monotone couplings for graphs, walks, trees and branching processes
• Shift-coupling of random rooted graphs and networks
• Local weak limits for collapsed branching processes with random out-degrees

This page was built for publication: Strong couplings for static locally tree-like random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5049908)