Nonparametric weighted stochastic block models

I. INTRODUCTION

• Weighted SBMs incorporate edge values alongside network adjacency, addressing standard SBMs’ omission of information that can be needed to represent network structure accurately.The model treats edge placement and weights separately, with weights conditioned on endpoint groups.Source: §I · p. 1, §II · pp. 1–2
• Exact integrated likelihoods let the nonparametric model infer the number of groups and other model dimensions from data rather than requiring them in advance.The approach uses microcanonical formulations that permit exact computation of the weight integrals.Source: §I · p. 1, §II · p. 3
• The weighted extension of the nested SBM infers hierarchical modular structure, with structured priors that reduce underfitting and support multilevel network descriptions.The hierarchical model can infer the number of groups and hierarchy depth without overfitting, and supports statistically principled weight-model selection.Source: §I · p. 1, §II · p. 3

II. WEIGHTED SBMS VIA EDGE COVARIATES

• The method accommodates weight models for continuous or discrete, signed or unsigned, bounded or unbounded covariates, including models extended by transformations.Microcanonical weight formulations make the required integrals straightforward to compute without sacrificing descriptive power.Source: §II · p. 3
• MCMC inference uses partition-label proposals and can sample from or maximize the posterior, with each sweep taking O(E) operations independently of the number of groups.The proposals combine local neighborhood and global layer information; agglomerative initialization helps avoid metastable states.Source: §I · p. 1, §II · p. 3

A. Migrations between countries

• The migration analysis uses a directed network of net migrant stocks between 232 countries, assembled by the United Nations in 2015.Each weight is the number moving from one country to another minus the number moving in the reverse direction.Source: A. Migrations between countries · p. 4
• The weighted SBM produces more groups and a finer migration partition, with recognizable regions and distant countries sometimes grouped by similar migration patterns.Countries including France, Canada, and the United Kingdom appear in specific groups; the United States is placed in its own group.Source: A. Migrations between countries · pp. 4–5, Figure 1 · p. 4
• Thresholding net migrant stocks to edge presence discards potentially valuable information, and no single threshold can always reproduce the large-scale structure.The unweighted fit groups geographically distant countries with distinct migration volumes and patterns together.Source: A. Migrations between countries · p. 4
• The inferred mixture of geometric distributions fits the broad migration-weight distribution well, unlike a single best-fit geometric distribution.The empirical distribution is much broader than any single geometric distribution.Source: Figure 2 · p. 4, A. Migrations between countries · p. 5

B. Vote correlations in congress

• The congressional voting hierarchy separates deputies into government and opposition groups, and the weighted SBM fits the bimodal vote-correlation distribution.The groups correspond to party affiliations and are more correlated within than across groups.Source: B. Vote correlations in congress · p. 5
• Shuffling the same vote correlations across deputy pairs yields a best fit with one group, which cannot capture their bimodal distribution.The shuffle preserves the overall weight distribution while removing its alignment with deputy partitions.Source: B. Vote correlations in congress · p. 6

C. The human brain

• The connectome hierarchy divides first into left and right hemispheres, then into smaller groups whose bottom-level divisions correlate with known anatomy.The subdivisions are similar across hemispheres but not identical.Source: C. The human brain · p. 6, Figure 4 · p. 7
• Some anatomical regions are split across groups or hierarchy branches, indicating heterogeneity within regions and suggesting a complementary way to classify anatomy.The figure labels each lowest-level group with its most frequent anatomical annotation.Source: C. The human brain · p. 6, Figure 4 · p. 7

1. Community structure?

• Assortativity is weak overall in the inferred brain modules (Q ≈ 0.13), with local values spanning positive and negative values.The Caudate nucleus is one example of a group with negative local assortativity.Source: §1 · p. 7
• Modularity increases at higher hierarchy levels, suggesting assortativity may matter more for global brain structure than for smaller-scale substructures.Groups sharing an anatomical label can also have different local assortativity.Source: §1 · pp. 7–8

IV. ELEMENTARY MODELS FOR EDGE WEIGHTS

• The weight likelihood completes the hierarchical partition model, with exact integration chosen to accommodate edge covariates of different types.The treatment covers signed or unsigned, continuous or discrete, bounded or unbounded weights; simple-graph notation is used for convenience, with final expressions also valid for multigraphs.Source: §IV · pp. 8–9

A. Continuous unsigned weights

• Positive continuous weights use an exponential distribution with a gamma prior, but that prior is cumbersome to integrate across nested levels.The microcanonical alternative generates covariates asymptotically identically while permitting exact integration.Source: A. Continuous unsigned weights · p. 9

1. Microcanonical distribution

• Conditioning positive covariates on their total sum yields a microcanonical model whose individual marginals approach the exponential distribution as N grows at fixed mean.Using this model for group-level sums makes integration over hierarchical parameters straightforward and supports an exact hierarchical SBM without sacrificing descriptive power.Source: §1 · p. 9

B. Continuous signed weights

• Signed weights use a normal model with fixed average and variance, with a normal-inverse-chi-squared conjugate prior for those parameters.The resulting marginal likelihood leaves four global hyperparameters to determine, and its shape does not readily support a closed-form hierarchy.Source: B. Continuous signed weights · pp. 10–11

1. Microcanonical distribution

• Conditioning signed covariates on their total sum and sum of squares yields a microcanonical model whose individual marginals approach the normal distribution as N grows with mean and variance fixed.This limit gives an easy-to-integrate model without sacrificing descriptive power.Source: §1 · pp. 11–12
• The hierarchy propagates group-level means upward but models scaled variances separately, avoiding extra upper-level covariates and repeated propagation of lower-level changes.The resulting marginal likelihood is well-defined even for zero-variance covariates or groups with a single element.Source: §1 · p. 12

C. Geometric discrete weights

• Discrete non-negative weights with a fixed average have a geometric maximum-entropy distribution.The model then uses a beta conjugate prior for its parameter.Source: C. Geometric discrete weights · p. 13
• Setting both beta-prior hyperparameters to one makes the parameter uniformly distributed on [0, 1], reflecting maximum ignorance.The passage contrasts this choice with the structured patterns often found in data.Source: C. Geometric discrete weights · p. 13
• Because the uninformative assumption rarely matches the structure found in data, the section identifies a hierarchical microcanonical description as a more robust approach.Source: C. Geometric discrete weights · p. 13

1. Microcanonical distribution

• The discrete microcanonical model is uniform over non-negative values conditioned on their total sum.Source: §1 · p. 13
• The number of configurations counts the ways to distribute the total across distinguishable parts.Source: §1 · p. 13
• At fixed mean µ/N, individual marginals approach a geometric distribution with p = N/(µ + N) as N grows.Source: §1 · p. 13, Figure 8 · p. 13

D. Binomial discrete weights

• Bounded weights x ∈ {0, …, M} can be modeled binomially, with x interpreted as the sum of M independent Bernoulli outcomes.The Bernoulli success probability is p ∈ [0, 1].Source: D. Binomial discrete weights · p. 14

1. Microcanonical distribution

• The microcanonical binomial model uniformly distributes N bounded non-negative values conditional on their total sum, by sampling exactly µ positive outcomes from NM trials.For large N with µ/N fixed, individual values approach a binomial distribution with p = µ/(NM).Source: §1 · p. 14, Figure 9 · p. 14
• If the global bound M* is unknown, it can be set to the maximum observed covariate; a compatible bound does not affect the posterior over partitions.The passage states that a prior on this single global bound can be omitted because it cannot influence that posterior.Source: §1 · p. 15

E. Poisson discrete weights

• Taking M → ∞ while keeping λ = pM fixed gives the Poisson model for discrete weights, with a gamma conjugate prior for λ.The model can also be formulated as an asymptotically equivalent microcanonical model.Source: E. Poisson discrete weights · p. 15

1. Microcanonical distribution

• The microcanonical Poisson model replaces the Poisson probability of the total sum with a constraint fixing that sum, leaving a uniform multinomial distribution over values.The joint Poisson distribution decomposes into a Poisson total and a uniform multinomial conditional on that total.Source: §1 · p. 15
• For sufficiently large N with µ/N fixed, individual covariates approach a Poisson distribution with λ = µ/N.Figure 10 depicts the asymptotic marginal distribution.Source: §1 · p. 15, Figure 10 · p. 16

F. Transformed weights

• Transforming weights as yij = f(xij) permits use of existing covariate models, and for continuous weights the derivative factor does not alter the partition posterior but matters for model selection.The transformation can be chosen to suit a dataset without otherwise changing the associated algorithms.Source: F. Transformed weights · p. 16

1. Broadly distributed weights

• For broadly distributed positive weights, transforming y = ln(x/xm) allows an exponential model, while a log-normal model may better fit weights peaked around a typical value.The latter is described as useful when the peaked shape is difficult to represent with a mixture of exponential distributions.Source: §1 · p. 16

2. Bounded weights

• Bounded weights can be mapped to unbounded values for normal or exponential modeling, with model selection determining which transformation best suits the data.The described options use logit or inverse-hyperbolic-tangent transformations for a normal model, or a negative logarithm for an exponential model.Source: §2 · pp. 16–17

3. Decomposing covariates

• Signed discrete weights can be reversibly decomposed into sign and magnitude, modeled respectively with a Bernoulli distribution and a non-negative distribution.The joint marginal likelihood combines the two covariate models.Source: §3 · p. 17

G. Model selection

• ln Λ ≈4,458 favors the log-normal over the exponential model for human-brain electrical connectivity, despite the log-normal model having more internal parameters.The Bayesian criterion favors the more complex model only when supported by statistical evidence; the table compares joint log-likelihoods for the two transformations.Source: Table I · p. 17, G. Model selection · p. 17

V. CONCLUSION

• The weighted SBM is nonparametric and efficient, infers hierarchical modular structure at multiple scales, and can detect it without bias toward a particular mixing pattern.The number of groups and the size and shape of the hierarchy are inferred from data, and the inferred hierarchy is described as statistically significant.Source: §V · p. 18

• The methods can be adapted to directed networks, although the main text focuses on undirected networks.Source: Appendix A · p. 18
• Directed adjacency-matrix models are described in Ref.Source: Appendix A · p. 18
• For edge covariates, the expressions remain identical except that products run over directed pairs of groups and nodes, and the reference implementation supports these variations.Source: Appendix A · p. 18