  Mechanistic network models specify the mechanisms by which networks grow and
change, allowing researchers to investigate complex systems using both
simulation and analytical techniques. Unfortunately, it is difficult to write
likelihoods for instances of graphs generated with mechanistic models because
of a combinatorial explosion in outcomes of repeated applications of the
mechanism. Thus it is near impossible to estimate the parameters using maximum
likelihood estimation. In this paper, we propose treating node sequence in a
growing network model as an additional parameter, or as a missing random
variable, and maximizing over the resulting likelihood. We develop this
framework in the context of a simple mechanistic network model, used to study
gene duplication and divergence, and test a variety of algorithms for
maximizing the likelihood in simulated graphs. We also run the best-performing
algorithm on a human protein-protein interaction network and four non-human
protein-protein interaction networks. Although we focus on a specific
mechanistic network model here, the proposed framework is more generally
applicable to reversible models.
