Must within-block probabilities be highest?

No. General block models allow other patterns.

Are block sizes always random?

No. Many generators use specified memberships or sizes.

Does the model prove communities exist?

No. It describes or infers structure under assumptions that require assessment.

AI Glossary / Statistics and probability / Intermediate

Stochastic block model

Definition

A stochastic block model is a probabilistic model of a network in which nodes belong to groups, or blocks, and connection probabilities depend on the groups of the two nodes. In the basic model, edges are independent conditional on the block memberships and connection probabilities. It provides a simple way to generate networks with group structure or infer possible structure from an observed network. The inferred blocks are model-based patterns, not automatically meaningful real-world communities.

What it means

The model replaces a separate connection probability for every node pair with a smaller matrix of probabilities between blocks. Nodes in the same block share the same pattern of connection probabilities in the basic version.

High within-block probabilities and lower between-block probabilities describe familiar community structure. Other matrices describe different patterns, including groups that connect mainly to other groups. The word block therefore does not require a dense, internally connected community.

Memberships can be fixed for generation or treated as unknown or random in a statistical model. When memberships are random, edge independence is conditional on them; shared uncertain memberships can create dependence after they are averaged out. This distinction matters when interpreting the model mathematically.

How it works

Specify the number and sizes of blocks, or a probability model for memberships. Define a block-to-block probability matrix with entries between zero and one. For an undirected network the matrix must be symmetric. State whether self-connections and directed edges are allowed.

For a simple undirected model without self-connections, consider each unordered pair of distinct nodes once. Draw an edge using the probability associated with the pair's blocks. Repeating this process creates different networks with the same underlying parameters.

For inference, begin with an observed network and estimate memberships, connection probabilities, and possibly the number of groups. The procedure and assumptions determine what patterns can be recovered. Compare the model with observed features such as degree variation and connectivity rather than assuming a plausible partition validates every aspect.

The basic model may not represent highly variable node activity within groups. Degree-corrected and other extensions address additional structure, but their parameters and interpretation differ. A generated benchmark is useful only to the extent that its assumptions resemble the challenge being evaluated.

Three practical examples

1. An AI researcher generates networks with known groups to test whether a graph-learning method can recover planted structure under varying connection strengths.

2. An analyst models collaboration links to explore whether departments have distinct connection patterns, without interpreting the estimated groups as official organizational categories.

3. A platform team compares observed interaction patterns with a simple block-model baseline to identify network features the baseline misses.

Think of it this way

Think of a social event where the probability of two guests exchanging contact details depends on their table assignments. Guests at the same table might connect often, but not necessarily. The seating plan defines probabilities; it does not prescribe a fixed list of conversations.

Worked example

Consider an original simple undirected network with no self-connections. Block A contains four nodes and block B contains three. Let within-A connection probability be 0.8, within-B probability 0.6, and between-block probability 0.1. Memberships are fixed.

There are 4 × 3 / 2 = 6 possible within-A edges and 3 × 2 / 2 = 3 possible within-B edges. There are 4 × 3 = 12 possible between-block edges. Expected counts are therefore 6 × 0.8 = 4.8, 3 × 0.6 = 1.8, and 12 × 0.1 = 1.2. Expected total edges equal 7.8.

One A node has expected degree 3 × 0.8 + 3 × 0.1 = 2.7. One B node has expected degree 2 × 0.6 + 4 × 0.1 = 1.6. Summing expected degrees gives 4 × 2.7 + 3 × 1.6 = 15.6, twice the expected edge count, as required for an undirected graph.

The probability of no between-block edges is 0.9 raised to the twelfth power, about 0.2824. Thus even a positive between-block probability can produce disconnected blocks in a realization. Fractional expected counts do not mean a generated network contains fractional edges.

Illustrative case study

In a fictional company, Maple Networks benchmarks a graph-based recommendation method using block-model simulations. Initial tests use clear communities and show strong recovery. The research team then increases cross-group connections and adds a separate benchmark with uneven node activity. Performance declines, revealing that the first test was unusually favorable. The team reports results by scenario and tests on suitable real data before making product claims. The simulations help explain behavior under controlled assumptions; they do not certify performance on every customer network.

Common misconceptions and mistakes

A block is not necessarily a densely linked community. The probability matrix can express other connection patterns.

Expected counts are not fixed counts, and nodes in the same block need not have identical realized degrees. Conversely, strong degree variation in observed data may require an extension to the basic model.

Estimated labels do not reveal intrinsic group identities. Relabeling blocks can describe the same model, and different fits may be plausible. Network sampling, missing edges, and model misspecification can affect conclusions. Avoid treating a mathematically convenient partition as a causal explanation of relationships.

Business use

Stochastic block models support network exploration, graph-method benchmarking, and simplified simulations of interaction structure. Their compact parameters make assumptions inspectable and enable controlled comparisons across scenarios.

Businesses should define what a node and edge represent before fitting or generating a graph. Check whether direction, intensity, repeated interactions, and time matter. If an application needs weighted or changing networks, the basic binary static model may be insufficient. Explain the operational interpretation of blocks and validate useful predictions rather than relying on visually appealing clusters.

Check your understanding

Answer: Two blocks have five and six nodes.

How many possible undirected between-block edges are there?

Answer: Thirty, because each of the five nodes can connect to each of the six. No division by two is needed for this cross-block count.

Related terms

Graph
Generative model
Conditional independence
Node degree
community detection
adjacency matrix
Erdős–Rényi graph
degree-corrected block model

Learn next

Study graph likelihoods and community-detection evaluation. Then compare the basic model with degree-corrected and mixed-membership extensions.

Graph

Sources

Aalto Dictionary of Machine Learning, stochastic block model: https://aaltodictionaryofml.github.io/ADictML_Main.pdf . NetworkX primary generator documentation: https://networkx.org/documentation/stable/reference/generated/networkx.generators.community.stochastic_block_model.html . The entry explicitly qualifies edge independence conditional on memberships. Counts, probabilities, and the fictional benchmark case are original teaching examples.

Previous: Stochastic beam search Next: Stochastic dominance