Large deviations for the greedy exploration process on configuration models

DOI10.1214/23-ECP541MaRDI QIDQ6177629zbMATH OpenOpenAlexFDO

Authors Bermolen Paola, Goicoechea Valeria, Jonckheere Matthieu

Publication date 17 January 2024

Published in Electronic Communications in Probability (Search for Journal in Brave)

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

zbMATH Keywords

comparison principleconfiguration modelHamilton-Jacobi equationslarge deviationsrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hamilton-Jacobi equations (35F21) Large deviations (60F10)

Abstract: We prove a large deviation principle for the greedy exploration of configuration models, building on a time-discretized version of the method proposed by Bermolen et al. and Brightwell et al. for jointly constructing a random graph from a given degree sequence and its exploration. The proof of this result follows the general strategy to study large deviations of processes proposed by Feng and Kurtz, based on the convergence of non-linear semigroups. We provide an intuitive interpretation of the LD cost function using Cramer's theorem for the average of random variables with appropriate distribution, depending on the degree distribution of explored nodes. The rate function can be expressed in a closed-form formula, and the large deviations trajectories can be obtained through explicit associated optimization problems. We then deduce large deviations results for the size of the independent set constructed by the algorithm. As a particular case, we analyze these results for d-regular graphs.

Recommendations

• Large deviation principle for the greedy exploration algorithm over Erdős-Rényi graphs
• Large deviations of the greedy independent set algorithm on sparse random graphs
• Rare event asymptotics for exploration processes for random graphs
• An introduction to large deviations for random graphs
• Depth first exploration of a configuration model

Cites work

• A PDE approach to some asymptotic problems concerning random differential equations with small noise intensities
• Differential equations for random processes and random graphs
• Generation of Semi-Groups of Nonlinear Transformations on General Banach Spaces
• scientific article; zbMATH DE number 3939236 (Why is no real title available?)
• scientific article; zbMATH DE number 1064647 (Why is no real title available?)
• scientific article; zbMATH DE number 1153603 (Why is no real title available?)
• Large deviation principle for the greedy exploration algorithm over Erdős-Rényi graphs
• Large deviations for finite state Markov jump processes with mean-field interaction via the comparison principle for an associated Hamilton-Jacobi equation
• Large deviations for stochastic processes.
• Random graphs and complex networks. Volume 1
• The greedy independent set in a random graph with given degrees
• The jamming constant of uniform random graphs
• The method of stochastic exponentials for large deviations

Cited in

(1)

• Large deviations of the greedy independent set algorithm on sparse random graphs

This page was built for publication: Large deviations for the greedy exploration process on configuration models

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