The statistical analysis of complex networks is a challenging task, given
that appropriate statistical models and efficient computational procedures are
required in order for structures to be learned. One line of research has aimed
at developing mixture models for random graphs, and this strategy has been
successful in revealing structures in social and biological networks. The
principle of these models is to assume that the distribution of the edge values
follows a parametric distribution, conditionally on a latent structure which is
used to detect connectivity patterns. However, these methods suffer from
relatively slow estimation procedures, since dependencies are complex and do
not necessarily allow for computational simplifications. In this paper we adapt
online estimation strategies, originally developed for the EM algorithm, to the
case of models for which the probability of the missing data conditionally on
the available observations is not tractable. Our work focuses on two methods,
the first based on the SAEM algorithm, and the second on variational methods.
We perform a simulation to compare these two algorithms with existing
approaches, and we use the method to decipher the structure of the US political
websites network. We show that our online EM-based algorithms offer a good
trade-off between precision and speed, when estimating parameters for mixture
distributions in the context of random graphs.