  Numerous networks in the real world change over time, in the sense that nodes
and edges enter and leave the networks. Various dynamic random graph models
have been proposed to explain the macroscopic properties of these systems and
to provide a foundation for statistical inferences and predictions. It is of
interest to have a rigorous way to determine how well these models match
observed networks. We thus ask the following goodness of fit question: given a
sequence of observations/snapshots of a growing random graph, along with a
candidate model M, can we determine whether the snapshots came from M or from
some arbitrary alternative model that is well-separated from M in some natural
metric? We formulate this problem precisely and boil it down to goodness of fit
testing for graph-valued, infinite-state Markov processes and exhibit and
analyze a universal test based on non-stationary sampling for a natural class
of models.
