Systematic assessment of the quality of fit of the stochastic block model for empirical networks

We perform a systematic analysis of the quality of fit of the stochastic block model (SBM) for 275 empirical networks spanning a wide range of domains and orders of size magnitude. We employ posterior predictive model checking as a criterion to assess the quality of fit, which involves comparing networks generated by the inferred model with the empirical network, according to a set of network descriptors. We observe that the SBM is capable of providing an accurate description for the majority of networks considered, but falls short of saturating all modeling requirements. In particular, networks possessing a large diameter and slow-mixing random walks tend to be badly described by the SBM. However, contrary to what is often assumed, networks with a high abundance of triangles can be well described by the SBM in many cases. We demonstrate that simple network descriptors can be used to evaluate whether or not the SBM can provide a sufficiently accurate representation, potentially pointing to possible model extensions that can systematically improve the expressiveness of this class of models.

Figure 1

Examples of posterior predictive distributions for some descriptors (see Table 1 for definitions) using the DCSBM, together with $z$ score and relative deviation. The solid black line shows the empirical value of the descriptor $f\left(\mathit{G}\right)$, and the dashed green line the mean of the predictive posterior distribution. In (a) and (b) we see examples where employing both criteria reveal unambiguously good and bad agreements, respectively, between data and model. However, in (c) we see a situation where despite a substantial disagreement with respect to the relative deviation, the $z$ score indicates that the model cannot be discarded as a plausible explanation for the data. In (d) we see a situation where the $z$ score points to decisive rejection of the model, but the small relative deviation allows us to accept it as an accurate approximation.

Figure 2

(Top) Number of nodes and edges for the networks in the corpus used in this work and their domain composition (inset). (Bottom) Distribution of descriptor values for the networks in the corpus. The horizontal line marks the median values.

Figure 3

Distribution of relative deviation (top), $z$ score (middle), and fraction of networks reproduced (bottom) for (a) the configuration model and (b) the DCSBM, according to their respective predictive posterior distributions for each descriptor. We also show the median and mean of the absolute values for all descriptors for each network. The solid blue lines mark the negative and positive median values, and the dashed red line marks the values of $\left|\mathrm{\Delta }\right|=0.05$ and $\left|z\right|=3$. The fraction of networks reproduced correspond to those that have the absolute value of either $\mathrm{\Delta }$ or $z$ below these thresholds. The points in green color correspond to the networks that are not reproduced according to this combined criterion.

Figure 4

Relative deviation and $z$-score values for the global and mean local clustering coefficients, $C_g$ and $C_l$, as well as diameter and characteristic time of a random walk, $⌀$ and $\tau$, as a function of their empirical values, for every network in the corpus, when using the DCSBM. The dashed red line marks the values of $\left|\mathrm{\Delta }\right|=0.05$ and $\left|z\right|=3$. The size of the symbol corresponds to the logarithm of the number of edges in the network, and the darkness to the mean degree.

Figure 5

Absolute value of the relative deviation (top), $z$ score (middle) and fraction of reproduced descriptors (bottom), as a function of the number of edges, for every network in the corpus. The dashed red line marks the values of $\left|\mathrm{\Delta }\right|=0.05$ and $\left|z\right|=3$. The fraction of descriptors reproduced correspond to those that have the value of either $\mathrm{\Delta }$ or $z$ below these thresholds. The points in green color correspond to the descriptors that are not reproduced according to this combined criterion.

Figure 6

Fraction of reproduced networks according to their domain, considering the (a) median and (b) mean values of either the $z$ score, the relative deviations, or their combined values, for both models (as shown in the legend). When the combined values are used, this means that a model is deemed compatible with a network when we obtain either $\left|\mathrm{\Delta }\right|<0.05$ or $\left|z\right|<3$.

Figure 7

Predictiveness of the quality of fit of the generative models considered, according to the empirical descriptor values, framed as a binary classification problem, as described in the text. (a) ROC curve for a leave-one-out random-forest classifier, (b) Gini feature importance for the configuration model, (c) same as (b) but for the DCSBM. Panels (d) and (e) show the best ROC AUC obtained for a set of descriptors of a given size, for the configuration model and DSCBM, respectively. Panels (f) and (g) show the same as (d) and (e), respectively, but with the number of edges excluded from the analysis.

Figure 8

Absolute value of the $z$ score versus absolute value of relative deviation, for every descriptor value and network in the corpus, according to (a) the configuration model and (b) the DCSBM. The dashed lines mark the values $\left|z\right|=3$ and $\left|\mathrm{\Delta }\right|=0.05$, and the histograms the marginal distributions. The solid blue lines mark the median values.

Figure 9

(a) Kendall's correlation coefficient $\tau$ between pairs of descriptor values across all networks in the corpus. Panels (b) and (c) show the same but for $z$ score and relative deviation values, respectively, according to the DCSBM. The insets show the correlation between coefficients from each respective panel and panel (a).