Inferring network structures using hierarchical exponential random graph models

Networks are broadly used to represent the interaction relationships between entities in a wide range of scientific fields. Ensembles of networks are employed to provide multiple network observations from the same set of entities. These observations may capture different features of the relationships: some ensembles exhibit group structures; some ensembles are collected over time; other ensembles have more individual differences. Statistical models for ensembles of networks should describe not only the dependency structure within each network, but also the variations of the structural patterns across networks.

Exponential random graph models (ERGMs) provide a highly flexible way to study the complex dependency structures within networks. We aim to develop novel methodologies that utilise ERGMs to infer the underlying structures of ensembles of networks from the following three aspects: (1) identifying and characterising groups of networks that are similar with respect to the effects of local connectivity patterns and covariates of interest on shaping the global structure of networks; (2) modelling the evolution of networks over time by representing the associated parameters using a piecewise linear function; (3) analysing the individual characteristics of each network and the population structures of the whole ensemble in terms of the block structure, homophily, transitivity and other local structural properties.

For identifying the group structure of ensembles and the block structure of networks, we employ a Bayesian nonparametric prior on an infinite sample space, instead of requiring a fixed number of groups in advance as in the existing models. In this way, the number of mixture models can grow along with the data size. This appealing property enables our models to fit the data better. Moreover, for the ensembles of networks with a time order, we utilise a fused lasso penalty to encourage similarities on the parameter estimation of the consecutive networks as they tend to share similar connectivity patterns.

The inference of ERGMs under a Bayesian nonparametric framework is very challenging due to the fact that we have an infinite number of intractable ERGM likelihood functions in the model. Besides, the dependency among edges within the same block and the unknown number of blocks also significantly increase the difficulty of recovering the unknown block structure. What's more, the correlation between dynamic networks also requires us to work on all the possible edges of the ensemble simultaneously, posing a big challenge for the algorithm.

To solve these issues, we develop five algorithms for the model estimation: (1) a novel Metropolis-Hastings algorithm to sample from the intractable posterior distribution of ERGMs with multiple networks using an intermediate importance sampling technique; (2) a new Metropolis-within-slice sampling algorithm to perform full Bayesian inference on infinite mixtures of ERGMs; (3) a pseudo likelihood based Metropolis-within-slice sampling algorithm to learn the group structure of ensembles fast and adaptively; (4) an alternating direction method of multipliers (ADMM) algorithm for the fast estimation of dynamic ensembles using a matrix decomposition technique; (5) a Metropolis-within-Gibbs sampling algorithm for the population analysis of structural patterns with an approximated stick-breaking prior.