  Much work in the study of large deviations for random graph models is focused
on the dense regime where the theory of graphons has emerged as a principal
tool. These tools do not give a good approach to large deviation problems for
random graph models in the sparse regime. The aim of this paper is to study an
approach for large deviation problems in this regime by establishing Large
Deviation Principles (LDP) on suitable path spaces for certain exploration
processes of the associated random graph sequence.
  Our work focuses on the study of one particular class of random graph models,
namely the configuration model; however the general approach of using
exploration processes for studying large deviation properties of sparse random
graph models has broader applicability. The goal is to study asymptotics of
probabilities of non-typical behavior in the large network limit. The first key
step for this is to establish a LDP for an exploration process associated with
the configuration model. A suitable exploration process here turns out to be an
infinite dimensional Markov process with transition probability rates that
diminish to zero in certain parts of the state space. Large deviation
properties of such Markovian models is challenging due to poor regularity
behavior of the associated local rate functions. Next, using the rate function
in the LDP for the exploration process we formulate a calculus of variations
problem associated with the asymptotics of component degree distributions. The
second key ingredient in our study is a careful analysis of the infinite
dimensional Euler-Lagrange equations associated with this calculus of
variations problem. Exact solutions are identified which then provide explicit
formulas for decay rates of probabilities of non-typical component degree
distributions and related quantities.
  Please see the paper for the complete abstract.
