Clustering of heterogeneous populations of networks

Statistical methods for reconstructing networks from repeated measurements typically assume that all measurements are generated from the same underlying network structure. This need not be the case, however. People's social networks might be different on weekdays and weekends, for instance. Brain networks may differ between healthy patients and those with dementia or other conditions. Here we describe a Bayesian analysis framework for such data that allows for the fact that network measurements may be reflective of multiple possible structures. We define a finite mixture model of the measurement process and derive a Gibbs sampling procedure that samples exactly from the full posterior distribution of model parameters. The end result is a clustering of the measured networks into groups with similar structure. We demonstrate the method on both real and synthetic network populations.

Figure 1

Contour map of a population of networks generated from the heterogeneous model of Eq. (8), as embedded in a two-dimensional space using multidimensional scaling. Darker colors indicate a higher density of networks and the three peaks correspond to the modes used in the model, which are illustrated at the top. For this simple example, we draw networks from each of the three modes with identical probability and use the same true- and false-positive rates for all modes, namely, ${\alpha }_u=0.9$ and ${\beta }_u=0.1$ for $u=1$, 2, 3. As illustrated at the bottom of the figure, a network resembling mode 3 sits close to that mode in the low-dimensional space.

Figure 2

Recovery performance for (a) the partitions $\mathit{Z}$, (b) the model parameters $\mathit{\theta }$, and (c) the modes $\mathcal{A}$, for a bimodal population of networks drawn from the modes 1 and 3 shown in Fig. 1 with ${\pi }_1={\pi }_2=\frac{1}{2}$, across a range of flip probabilities (Eq. (26)) and population sizes $N$. Panel (d) shows how much the model updates its certainty about the modes $\mathcal{A}$ using the data.

Figure 3

Results for the reality mining proximity networks described in the text, in which proximity measurements were binned in day-long intervals. (a) Modal networks $\widehat{\mathcal{A}}$ with edge widths proportional to the estimates ${\widehat{A}}_{ij}^{\left(u\right)}$. (b) The fraction of networks in each cluster that were sampled on a particular day of the week (left) and during a particular month (right). (c) Average posterior log-probability [Eq. (10)] across Gibbs samples as a function of the number of clusters $K$.