  A class of random graph models is considered, combining features of
exponential-family models and latent structure models, with the goal of
retaining the strengths of both of them while reducing the weaknesses of each
of them. An open problem is how to estimate such models from large networks. A
novel approach to large-scale estimation is proposed, taking advantage of the
local structure of such models for the purpose of local computing. The main
idea is that random graphs with local dependence can be decomposed into
subgraphs, which enables parallel computing on subgraphs and suggests a
two-step estimation approach. The first step estimates the local structure
underlying random graphs. The second step estimates parameters given the
estimated local structure of random graphs. Both steps can be implemented in
parallel, which enables large-scale estimation. The advantages of the two-step
estimation approach are demonstrated by simulation studies with up to 10,000
nodes and an application to a large Amazon product recommendation network with
more than 10,000 products.
