Nonparametric weighted stochastic block models

We present a Bayesian formulation of weighted stochastic block models that can be used to infer the large-scale modular structure of weighted networks, including their hierarchical organization. Our method is nonparametric, and thus does not require the prior knowledge of the number of groups or other dimensions of the model, which are instead inferred from data. We give a comprehensive treatment of different kinds of edge weights (i.e., continuous or discrete, signed or unsigned, bounded or unbounded), as well as arbitrary weight transformations, and describe an unsupervised model selection approach to choose the best network description. We illustrate the application of our method to a variety of empirical weighted networks, such as global migrations, voting patterns in congress, and neural connections in the human brain.

Figure 1

(a) Fit of the unweighted SBM for UN migration data, using the threshold approach described in the text. The edges are routed according the inferred hierarchy (shown in blue), using an edge-bundling algorithm by Holten [18], and the edge sources are marked with a green color. (b) Fit of the weighted SBM for the same data with the migrant stocks included, as shown by the edge colors and in the legend.

Figure 2

Overall distribution of the number of migrations for the UN data. The solid line shows the inferred distribution according to the weighted SBM using geometric distributions. The dashed line shows the best fit of a single geometric distribution.

Figure 3

(a) Fit of the weighted SBM for a matrix of vote correlations between deputies of the lower house of the Brazilian congress. The group boundaries are shown by horizontal and vertical lines. (b) Same as in (a) but using the layout of Fig. 1 that shows the entire hierarchical division. (c) Overall distribution of vote correlations. The solid line shows the inferred distribution according to the weighted SBM using transformed normal distributions. The dashed line shows the best fit using the same model, but on the shuffled data with the same empirical distribution.

Figure 4

(a) Inferred SBM for the human connectome, using electrical connectivity and fractional anisotropy as edge covariates. The text labels show the most frequent anatomical annotation inside each group at the lowest hierarchical level. (b) Empirical and fitted distribution of electrical connectivity of the edges. (c) Empirical and fitted distribution of fractional anisotropy of the edges.

Figure 5

(a) Group assortativity $q_r$ [Eq. (19)] for the lowest level of the hierarchy in Fig. 4, with groups labeled using the most frequent anatomical annotation. Blue circle (red square) markers correspond to the left (right) hemisphere. On the right axis is shown a histogram of the $q_r$ values, with a horizontal line marking the average $Q={\sum }_r{q}_r/B\approx 0.13$. The inset shows the modularity value $Q_l$ as a function of the hierarchy level $l$. (b) Dispersion of $q_r$ values for groups that share the same anatomical annotation, as labeled in the $x$ axis.

Figure 6

The marginal distribution of each individual covariate $x$ in the unsigned microcanonical model, given by Eq. (30), approaches asymptotically the exponential distribution as the number of values $N$ increases, and if the mean $\overline{x}=\mu /N$ is kept fixed.

Figure 7

The marginal distribution of each individual covariate $x$ in the signed microcanonical model, given by Eq. (52), approaches asymptotically the normal distribution as the number of values $N$ increases, and if the mean $\overline{x}=\mu /N$ and variance ${\sigma }^2=\nu /N-{\overline{x}}^2$ are kept fixed.

Figure 8

The marginal distribution of each individual covariate $x$ in the discrete microcanonical model, given by Eq. (69), approaches asymptotically the geometric distribution as the number of values $N$ increases, and the mean value $\mu /N$ is kept fixed.

Figure 9

The marginal distribution of each individual covariate $x$ in the discrete microcanonical model, given by Eq. (77), approaches asymptotically the binomial distribution as the number of values $N$ increases, and the mean $\overline{x}=\mu /N$ is kept fixed.

Figure 10

The marginal distribution of each individual covariate $x$ in the discrete microcanonical model, given by Eq. (90), approaches asymptotically the Poisson distribution as the number of values $N$ increases, and the mean $\overline{x}=\mu /N$ is kept fixed.

Figure 11

Overall distribution of the electrical connectivity of the human brain data. The solid line shows the inferred distribution according to the weighted SBM using two models for the edge covariates, as shown in the legend.