Beginner Explanation
Imagine a group of friends at a party where people are standing in different circles. Each circle represents a group of friends (clusters), and within each circle, friends talk to each other more often than to those outside their circle. The Symmetric k-Stochastic Block Model helps us understand how these circles form and how tightly connected the friends are within and between circles. It uses math to figure out the likelihood of connections based on these groups, helping us identify who belongs to which circle at the party.Technical Explanation
The Symmetric k-Stochastic Block Model (SBM) is a generative model used for community detection in graphs. In this model, nodes (or vertices) are divided into k clusters, and the probability of an edge existing between any two nodes depends on the clusters they belong to. The model is defined by two parameters: the intra-cluster connection probability matrix P (where P[i][j] is the probability of an edge between nodes in clusters i and j) and the number of nodes in each cluster. To simulate a graph using SBM, we can use the following Python code with the NetworkX library: “`python import numpy as np import networkx as nx # Parameters n = 100 # total number of nodes k = 3 # number of clusters sizes = [30, 30, 40] # sizes of each cluster p_in = 0.8 # intra-cluster probability p_out = 0.1 # inter-cluster probability # Generate the stochastic block model graph sizes = [30, 30, 40] probs = [[p_in if i == j else p_out for j in range(k)] for i in range(k)] G = nx.stochastic_block_model(sizes, probs) # Visualize the graph nx.draw(G) “`Academic Context
The Symmetric k-Stochastic Block Model (SBM) is rooted in statistical graph theory, particularly in the study of community structures in networks. The model was introduced in the seminal paper by Holland et al. (1983), titled ‘Stochastic blockmodels: First steps.’ The mathematical foundation of SBM involves probability theory and matrix representations of graphs. The model assumes that nodes are partitioned into k groups, and the probability of edge formation is determined by a matrix that specifies the connection probabilities among groups. The model has been extensively studied for its applications in social network analysis, biological networks, and information retrieval. Key papers include ‘Community detection algorithms: a comparative analysis’ by Lancichinetti and Fortunato (2009) and ‘A survey of community detection approaches: From statistical modeling to deep learning’ by Yang et al. (2020).Code Examples
Example 1:
import numpy as np
import networkx as nx
# Parameters
n = 100 # total number of nodes
k = 3 # number of clusters
sizes = [30, 30, 40] # sizes of each cluster
p_in = 0.8 # intra-cluster probability
p_out = 0.1 # inter-cluster probability
# Generate the stochastic block model graph
sizes = [30, 30, 40]
probs = [[p_in if i == j else p_out for j in range(k)] for i in range(k)]
G = nx.stochastic_block_model(sizes, probs)
# Visualize the graph
nx.draw(G)Example 2:
import numpy as np
import networkx as nx
# Parameters
n = 100 # total number of nodesExample 3:
import networkx as nx
# Parameters
n = 100 # total number of nodes
k = 3 # number of clustersView Source: https://arxiv.org/abs/2511.16613v1