Random Walk Models of Network Formation and Sequential Monte Carlo Methods for Graphs

摘要

We introduce a class of network models that insert edges by connecting thestarting and terminal vertices of a random walk on the network graph. Withinthe taxonomy of statistical network models, this class is distinguished bypermitting the location of a new edge to explicitly depend on the structure ofthe graph, but being nonetheless statistically and computationally tractable.In the limit of infinite walk length, the model converges to an extension ofthe preferential attachment model---in this sense, it can be motivatedalternatively by asking what preferential attachment is an approximation to.Theoretical properties, including the limiting degree sequence, are studiedanalytically. If the entire history of the graph is observed, parameters can beestimated by maximum likelihood. If only the final graph is available, itshistory can be imputed using MCMC. We develop a class of sequential Monte Carloalgorithms that are more generally applicable to sequential random graphmodels, and may be of interest in their own right. The model parameters can berecovered from a single graph generated by the model. Applications to dataclarify the role of the random walk length as a length scale of interactionswithin the graph.