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