generate_maxent_sbm#
- graph_tool.generation.generate_maxent_sbm(b, mrs, out_theta, in_theta=None, directed=False, multigraph=False, self_loops=False)[source]#
Generate a random graph by sampling from the maximum-entropy “canonical” stochastic block model.
- Parameters:
- biterable or
numpy.ndarray
Group membership for each node.
- mrstwo-dimensional
numpy.ndarray
orscipy.sparse.spmatrix
Matrix with edge fugacities between groups.
- out_thetaiterable or
numpy.ndarray
Out-degree fugacities for each node.
- in_thetaiterable or
numpy.ndarray
(optional, default:None
) In-degree fugacities for each node. If not provided, will be identical to
out_theta
.- directed
bool
(optional, default:False
) Whether the graph is directed.
- multigraph
bool
(optional, default:False
) Whether parallel edges are allowed.
- self_loops
bool
(optional, default:False
) Whether self-loops are allowed.
- biterable or
- Returns:
- g
Graph
The generated graph.
- g
See also
solve_sbm_fugacities
Obtain SBM fugacities, given expected degrees and block constraints.
generate_sbm
Generate samples from the Poisson SBM
Notes
The algorithm generates simple or multigraphs according to the degree-corrected maximum-entropy stochastic block model (SBM) [peixoto-latent-2020], which includes the non-degree-corrected SBM as a special case.
The simple graphs are generated with probability:
\[P({\boldsymbol A}|{\boldsymbol \theta},{\boldsymbol \mu},{\boldsymbol b}) = \prod_{i<j} \frac{\left(\theta_i\theta_j\mu_{b_i,b_j}\right)^{A_{ij}}}{1+\theta_i\theta_j\mu_{b_i,b_j}},\]and the multigraphs with probability:
\[P({\boldsymbol A}|{\boldsymbol \theta},{\boldsymbol \mu},{\boldsymbol b}) = \prod_{i<j} \left(\theta_i\theta_j\mu_{b_i,b_j}\right)^{A_{ij}}(1-\theta_i\theta_j\mu_{b_i,b_j}).\]In the above, \(\mu_{rs}\) is the edge fugacity between groups \(r\) and \(s\), and \(\theta_i\) is the edge fugacity of node i.
For directed graphs, the probabilities are analogous, i.e.
\[\begin{split}P({\boldsymbol A}|{\boldsymbol \theta}^+,{\boldsymbol \theta}^-,{\boldsymbol \mu},{\boldsymbol b}) &= \prod_{i\ne j} \frac{\left(\theta_i^+\theta_j^-\mu_{b_i,b_j}\right)^{A_{ij}}}{1+\theta_i^+\theta_j^-\mu_{b_i,b_j}} & \quad\text{(simple graphs)},\\ P({\boldsymbol A}|{\boldsymbol \theta}^+,{\boldsymbol \theta}^-,{\boldsymbol \mu},{\boldsymbol b}) &= \prod_{i\ne j} \left(\theta_i^+\theta_j^-\mu_{b_i,b_j}\right)^{A_{ij}}(1-\theta_i^+\theta_j^-\mu_{b_i,b_j}) & \quad\text{(multigraphs)}.\end{split}\]References
[peixoto-latent-2020]Tiago P. Peixoto, “Latent Poisson models for networks with heterogeneous density”, DOI: 10.1103/PhysRevE.102.012309 [sci-hub, @tor], arXiv: 2002.07803
Examples
>>> g = gt.collection.data["polblogs"] >>> g = gt.GraphView(g, vfilt=gt.label_largest_component(g)) >>> g = gt.Graph(g, prune=True) >>> gt.remove_self_loops(g) >>> gt.remove_parallel_edges(g) >>> state = gt.minimize_blockmodel_dl(g) >>> ers = gt.adjacency(state.get_bg(), state.get_ers()).T >>> out_degs = g.degree_property_map("out").a >>> in_degs = g.degree_property_map("in").a >>> mrs, theta_out, theta_in = gt.solve_sbm_fugacities(state.b.a, ers, out_degs, in_degs) >>> u = gt.generate_maxent_sbm(state.b.a, mrs, theta_out, theta_in, directed=True) >>> gt.graph_draw(g, g.vp.pos, output="polblogs-maxent-sbm.pdf") <...> >>> gt.graph_draw(u, u.own_property(g.vp.pos), output="polblogs-maxent-sbm-generated.pdf") <...>
Left: Political blogs network. Right: Sample from the maximum-entropy degree-corrected SBM fitted to the original network.