graph_tool.inference
 Statistical inference of generative network models¶
This module contains algorithms for the identification of largescale network structure via the statistical inference of generative models.
Note
An introduction to the concepts used here, as well as a basic HOWTO is included in the cookbook section: Inferring modular network structure.
Nonparametric stochastic block model inference¶
Highlevel functions¶
Fit the stochastic block model, by minimizing its description length using an agglomerative heuristic. 

Fit the nested stochastic block model, by minimizing its description length using an agglomerative heuristic. 
State classes¶
The stochastic block model state of a given graph. 

The overlapping stochastic block model state of a given graph. 

The (possibly overlapping) block state of a given graph, where the edges are divided into discrete layers. 

The nested stochastic block model state of a given graph. 

Obtain the partition of a network according to the Bayesian planted partition model. 

Obtain the ordered partition of a network according to the ranked stochastic block model. 

Obtain the partition of a network according to Newman's modularity. 

Obtain the partition of a network according to the normalized cut. 

This class aggregates several state classes and corresponding inversetemperature values to implement parallel tempering MCMC. 

The state of a clique decomposition of a given graph. 
Abstract base classes¶
Base state that implements singleflip MCMC sweeps 

Base state that implements multiflip (mergesplit) MCMC sweeps 

Base state that implements multilevel agglomerative MCMC sweeps 

Base state that implements single flip MCMC sweeps 

Base state that implements multicanonical MCMC sweeps 

Base state that implements exhaustive enumerative sweeps 
Sampling and minimization¶
Equilibrate a MCMC with a given starting state. 

Equilibrate a MCMC at a specified target temperature by performing simulated annealing. 

Equilibrate a multicanonical Monte Carlo sampling using the WangLandau algorithm. 

The density of states of a multicanonical Monte Carlo algorithm. 
Comparing and manipulating partitions¶
The random label model state for a set of labelled partitions, which attempts to align them with a common group labelling. 

The mixed random label model state for a set of labelled partitions, which attempts to align them inside clusters with a common group labelling. 

Obtain the center of a set of partitions, according to the variation of information metric or reduced mutual information. 

Returns the maximum overlap between partitions, according to an optimal label alignment. 

Returns the hierarchical maximum overlap between nested partitions, according to an optimal recursive label alignment. 

Returns the variation of information between two partitions. 

Returns the mutual information between two partitions. 

Returns the reduced mutual information between two partitions. 

Returns the contingency graph between both partitions. 

Returns a copy of partition 

Returns a copy of partition 

Returns a copy of nested partition 

Returns a copy of partition 

Returns a copy of nested partition 

Find a partition with a maximal overlap to all items of the list of partitions given. 

Find a nested partition with a maximal overlap to all items of the list of nested partitions given. 

Returns a copy of nested partition 

Remap the values of 

Remap the values of the nested partition 
Auxiliary functions¶
Compute the "mean field" entropy given the vertex block membership marginals. 

Compute the Bethe entropy given the edge block membership marginals. 

Compute microstate entropy given a histogram of partitions. 

Compute the entropy of the marginal latent multigraph distribution. 

Generate a halfedge graph, where each halfedge is represented by a node, and an edge connects the halfedges like in the original graph. 

Get edge gradients corresponding to the block membership at the endpoints of the edges given by the 
Auxiliary classes¶
Histogram of partitions, implemented in C++. 

Histogram of block pairs, implemented in C++. 
Nonparametric network reconstruction¶
State classes¶
Inference state of an erased Poisson multigraph, using the stochastic block model as a prior. 

Inference state of the stochastic block model with latent triadic closure edges. 

Inference state of a measured graph, using the stochastic block model as a prior. 

Inference state of a measured graph, using the stochastic block model with triadic closure as a prior. 

Inference state of a measured graph with heterogeneous errors, using the stochastic block model as a prior. 

Inference state of an uncertain graph, using the stochastic block model as a prior. 

Base state for uncertain network inference. 

Base state for network reconstruction based on dynamical data, using the stochastic block model as a prior. 

Inference state for network reconstruction based on epidemic dynamics, using the stochastic block model as a prior. 

Base state for network reconstruction based on the Ising model, using the stochastic block model as a prior. 

State for network reconstruction based on the Glauber dynamics of the Ising model, using the stochastic block model as a prior. 

State for network reconstruction based on the Glauber dynamics of the continuous Ising model, using the stochastic block model as a prior. 

State for network reconstruction based on the equilibrium configurations of the Ising model, using the Pseudolikelihood approximation and the stochastic block model as a prior. 

State for network reconstruction based on the equilibrium configurations of the continuous Ising model, using the Pseudolikelihood approximation and the stochastic block model as a prior. 
Expectationmaximization Inference¶
Infer latent Poisson multigraph model given an "erased" simple graph. 
Semiparametric stochastic block model inference¶
State classes¶
The parametric, undirected stochastic block model state of a given graph. 
Largescale descriptors¶
Calculate Newman's (generalized) modularity of a network partition. 
Contents¶
 graph_tool.inference.minimize_blockmodel_dl(g, state=<class 'graph_tool.inference.blockmodel.BlockState'>, state_args={}, multilevel_mcmc_args={})[source]¶
Fit the stochastic block model, by minimizing its description length using an agglomerative heuristic.
 Parameters
 g
Graph
The graph.
 stateSBMlike state class (optional, default:
BlockState
) Type of model that will be used. Must be derived from
MultilevelMCMCState
. state_args
dict
(optional, default:{}
) Arguments to be passed to appropriate state constructor (e.g.
BlockState
) multilevel_mcmc_args
dict
(optional, default:{}
) Arguments to be passed to
multilevel_mcmc_sweep()
.
 g
 Returns
 min_statetype given by parameter
state
State with minimum description length.
 min_statetype given by parameter
Notes
This function is a convenience wrapper around
multilevel_mcmc_sweep()
.See [peixotoefficient2014] for details on the algorithm.
This algorithm has a complexity of \(O(V \ln^2 V)\), where \(V\) is the number of nodes in the network.
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378.
Examples
>>> g = gt.collection.data["polbooks"] >>> state = gt.minimize_blockmodel_dl(g) >>> state.draw(pos=g.vp["pos"], vertex_shape=state.get_blocks(), ... output="polbooks_blocks_mdl.svg") <...>
>>> g = gt.collection.data["polbooks"] >>> state = gt.minimize_blockmodel_dl(g, state=gt.OverlapBlockState) >>> state.draw(pos=g.vp["pos"], output="polbooks_overlap_blocks_mdl.svg") <...>
>>> g = gt.collection.data["celegansneural"] >>> state = gt.minimize_blockmodel_dl(g, state=gt.PPBlockState) >>> state.draw(output="celegans_mdl_pp.pdf") <...>
 graph_tool.inference.minimize_nested_blockmodel_dl(g, init_bs=None, state=<class 'graph_tool.inference.nested_blockmodel.NestedBlockState'>, state_args={}, multilevel_mcmc_args={})[source]¶
Fit the nested stochastic block model, by minimizing its description length using an agglomerative heuristic.
 Parameters
 g
Graph
The graph.
 init_bsiterable of iterable of
int``s (optional, default: ``None
) Initial hierarchical partition.
 B_min
int
(optional, default:1
) The minimum number of blocks.
 B_max
int
(optional, default:numpy.iinfo(numpy.int64).max
) The maximum number of blocks.
 b_min
VertexPropertyMap
(optional, default:None
) The partition to be used with the minimum number of blocks.
 b_max
VertexPropertyMap
(optional, default:None
) The partition to be used with the maximum number of blocks.
 stateSBM state class (optional, default:
NestedBlockState
) Type of model that will be used.
 state_args
dict
(optional, default:{}
) Arguments to be passed to appropriate state constructor (e.g.
BlockState
) multilevel_mcmc_args
dict
(optional, default:{}
) Arguments to be passed to
multilevel_mcmc_sweep()
.
 g
 Returns
 min_statetype given by parameter
state
State with minimum description length.
 min_statetype given by parameter
Notes
This function is a convenience wrapper around
multilevel_mcmc_sweep()
.See [peixotohierarchical2014] for details on the algorithm.
This algorithm has a complexity of \(O(E \ln^2 V)\), where \(E\) and \(V\) are the number of edges and nodes in the network, respectively.
References
 peixotohierarchical2014
Tiago P. Peixoto, “Hierarchical block structures and highresolution model selection in large networks “, Phys. Rev. X 4, 011047 (2014), DOI: 10.1103/PhysRevX.4.011047 [scihub, @tor], arXiv: 1310.4377.
Examples
>>> g = gt.collection.data["power"] >>> state = gt.minimize_nested_blockmodel_dl(g) >>> state.draw(output="power_nested_mdl.pdf") (...)
>>> g = gt.collection.data["celegansneural"] >>> state = gt.minimize_nested_blockmodel_dl(g, state_args=dict(overlap=True)) >>> state.draw(output="celegans_nested_mdl_overlap.pdf") (...)
 class graph_tool.inference.BlockState(g, b=None, B=None, eweight=None, vweight=None, recs=[], rec_types=[], rec_params=[], clabel=None, pclabel=None, bfield=None, Bfield=None, deg_corr=True, dense_bg=False, **kwargs)[source]¶
Bases:
graph_tool.inference.base_states.MCMCState
,graph_tool.inference.base_states.MultiflipMCMCState
,graph_tool.inference.base_states.MultilevelMCMCState
,graph_tool.inference.base_states.GibbsMCMCState
,graph_tool.inference.base_states.MulticanonicalMCMCState
,graph_tool.inference.base_states.ExhaustiveSweepState
,graph_tool.inference.base_states.DrawBlockState
The stochastic block model state of a given graph.
 Parameters
 g
Graph
Graph to be modelled.
 b
VertexPropertyMap
(optional, default:None
) Initial block labels on the vertices. If not supplied, it will be randomly sampled.
 B
int
(optional, default:None
) Number of blocks (or vertex groups). If not supplied it will be obtained from the parameter
b
. eweight
EdgePropertyMap
(optional, default:None
) Edge multiplicities (for multigraphs or block graphs).
 vweight
VertexPropertyMap
(optional, default:None
) Vertex multiplicities (for block graphs).
 recslist of
EdgePropertyMap
instances (optional, default:[]
) List of real or discretevalued edge covariates.
 rec_typeslist of edge covariate types (optional, default:
[]
) List of types of edge covariates. The possible types are:
"realexponential"
,"realnormal"
,"discretegeometric"
,"discretepoisson"
or"discretebinomial"
. rec_paramslist of
dict
(optional, default:[]
) Model hyperparameters for edge covariates. This should be a list of
dict
instances, or the string “microcanonical” (the default if nothing is specified). The keys depend on the type of edge covariate:"realexponential"
or"discretepoisson"
The parameter list is
["r", "theta"]
, corresponding to the parameters of the Gamma prior distribution. If unspecified, the default is the “empirical Bayes” choice:r = 1.0
andtheta
is the global average of the edge covariate."discretegeometric"
The parameter list is
["alpha", "beta"]
, corresponding to the parameters of the Beta prior distribution. If unspecified, the default is the noninformative choice:alpha = beta = 1.0
"discretebinomial"
The parameter list is
["N", "alpha", "beta"]
, corresponding to the number of trialsN
and the parameters of the Beta prior distribution. If unspecified, the default is the noninformative choice,alpha = beta = 1.0
, andN
is taken to be the maximum edge covarite value."realnormal"
The parameter list is
["m0", "k0", "v0", "nu0"]
corresponding to the normalinversechisquared prior. If unspecified, the defaults are:m0 = rec.fa.mean()
,k0 = 1
,v0 = rec.fa.std() ** 2
, andnu0 = 3
, whererec
is the corresponding edge covariate property map.
 clabel
VertexPropertyMap
(optional, default:None
) Constraint labels on the vertices. If supplied, vertices with different label values will not be clustered in the same group.
 pclabel
VertexPropertyMap
(optional, default:None
) Partition constraint labels on the vertices. This has the same interpretation as
clabel
, but will be used to compute the partition description length. bfield
VertexPropertyMap
(optional, default:None
) Local field acting as a prior for the node partition. This should be a vector property map of type
vector<double>
, and contain the logprobability for each node to be placed in each group. deg_corr
bool
(optional, default:True
) If
True
, the degreecorrected version of the blockmodel ensemble will be assumed, otherwise the traditional variant will be used. dense_bg
bool
(optional, default:False
) If
True
a dense matrix is used for the block graph, otherwise a sparse matrix will be used.
 g
 copy(g=None, eweight=None, vweight=None, b=None, B=None, deg_corr=None, clabel=None, overlap=False, pclabel=None, bfield=None, dense_bg=None, **kwargs)[source]¶
Copies the block state. The parameters override the state properties, and have the same meaning as in the constructor.
 get_block_state(b=None, vweight=False, **kwargs)[source]¶
Returns a
BlockState
corresponding to the block graph (i.e. the blocks of the current state become the nodes). The parameters have the same meaning as the in the constructor. Ifvweight == True
the nodes of the block state are weighted with the node counts.
 get_Be()[source]¶
Returns the effective number of blocks, defined as \(e^{H}\), with \(H=\sum_r\frac{n_r}{N}\ln \frac{n_r}{N}\), where \(n_r\) is the number of nodes in group r.
 get_bclabel(clabel=None)[source]¶
Returns a
VertexPropertyMap
corresponding to constraint labels for the block graph.
 get_bpclabel()[source]¶
Returns a
VertexPropertyMap
corresponding to partition constraint labels for the block graph.
 get_state()[source]¶
Alias to
get_blocks()
.
 get_ers()[source]¶
Returns the edge property map of the block graph which contains the \(e_{rs}\) matrix entries. For undirected graphs, the diagonal values (selfloops) contain \(e_{rr}/2\).
 get_er()[source]¶
Returns the vertex property map of the block graph which contains the number \(e_r\) of halfedges incident on block \(r\). If the graph is directed, a pair of property maps is returned, with the number of outedges \(e^+_r\) and inedges \(e^_r\), respectively.
 get_nr()[source]¶
Returns the vertex property map of the block graph which contains the block sizes \(n_r\).
 entropy(adjacency=True, dl=True, partition_dl=True, degree_dl=True, degree_dl_kind='distributed', edges_dl=True, dense=False, multigraph=True, deg_entropy=True, recs=True, recs_dl=True, beta_dl=1.0, Bfield=True, exact=True, **kwargs)[source]¶
Calculate the entropy (a.k.a. negative loglikelihood) associated with the current block partition.
 Parameters
 adjacency
bool
(optional, default:True
) If
True
, the adjacency term of the description length will be included. dl
bool
(optional, default:True
) If
True
, the description length for the parameters will be included. partition_dl
bool
(optional, default:True
) If
True
, anddl == True
the partition description length will be included. degree_dl
bool
(optional, default:True
) If
True
, anddl == True
the degree sequence description length will be included (for degreecorrected models). degree_dl_kind
str
(optional, default:"distributed"
) This specifies the prior used for the degree sequence. It must be one of:
"uniform"
,"distributed"
(default) or"entropy"
. edges_dl
bool
(optional, default:True
) If
True
, anddl == True
the edge matrix description length will be included. dense
bool
(optional, default:False
) If
True
, the “dense” variant of the entropy will be computed. multigraph
bool
(optional, default:True
) If
True
, the multigraph entropy will be used. deg_entropy
bool
(optional, default:True
) If
True
, the degree entropy term that is independent of the network partition will be included (for degreecorrected models). recs
bool
(optional, default:True
) If
True
, the likelihood for real or discretevalued edge covariates is computed. recs_dl
bool
(optional, default:True
) If
True
, anddl == True
the edge covariate description length will be included. beta_dl
double
(optional, default:1.
) Prior inverse temperature.
 exact
bool
(optional, default:True
) If
True
, the exact expressions will be used. Otherwise, Stirling’s factorial approximation will be used for some terms.
 adjacency
Notes
The “entropy” of the state is the negative loglikelihood of the microcanonical SBM, that includes the generated graph \(\boldsymbol{A}\) and the model parameters \(\boldsymbol{\theta}\),
\[\begin{split}\Sigma &=  \ln P(\boldsymbol{A},\boldsymbol{\theta}) \\ &=  \ln P(\boldsymbol{A}\boldsymbol{\theta})  \ln P(\boldsymbol{\theta}).\end{split}\]This value is also called the description length of the data, and it corresponds to the amount of information required to describe it (in nats).
For the traditional blockmodel (
deg_corr == False
), the model parameters are \(\boldsymbol{\theta} = \{\boldsymbol{e}, \boldsymbol{b}\}\), where \(\boldsymbol{e}\) is the matrix of edge counts between blocks, and \(\boldsymbol{b}\) is the partition of the nodes into blocks. For the degreecorrected blockmodel (deg_corr == True
), we have an additional set of parameters, namely the degree sequence \(\boldsymbol{k}\).For the traditional blockmodel, the model likelihood is
\[\begin{split}P(\boldsymbol{A}\boldsymbol{e},\boldsymbol{b}) &= \frac{\prod_{r<s}e_{rs}!\prod_re_{rr}!!}{\prod_rn_r^{e_r}}\times \frac{1}{\prod_{i<j}A_{ij}!\prod_iA_{ii}!!},\\ P(\boldsymbol{A}\boldsymbol{e},\boldsymbol{b}) &= \frac{\prod_{rs}e_{rs}!}{\prod_rn_r^{e_r}}\times \frac{1}{\prod_{ij}A_{ij}!},\end{split}\]for undirected and directed graphs, respectively, where \(e_{rs}\) is the number of edges from block \(r\) to \(s\) (or the number of halfedges for the undirected case when \(r=s\)), and \(n_r\) is the number of vertices in block \(r\) .
For the degreecorrected variant the equivalent expressions are
\[\begin{split}P(\boldsymbol{A}\boldsymbol{e},\boldsymbol{b},\boldsymbol{k}) &= \frac{\prod_{r<s}e_{rs}!\prod_re_{rr}!!}{\prod_re_r!}\times \frac{\prod_ik_i!}{\prod_{i<j}A_{ij}!\prod_iA_{ii}!!},\\ P(\boldsymbol{A}\boldsymbol{e},\boldsymbol{b},\boldsymbol{k}) &= \frac{\prod_{rs}e_{rs}!}{\prod_re_r^+!\prod_re_r^!}\times \frac{\prod_ik_i^+!\prod_ik_i^!}{\prod_{ij}A_{ij}!},\end{split}\]where \(e_r = \sum_se_{rs}\) is the number of halfedges incident on block \(r\), and \(e^+_r = \sum_se_{rs}\) and \(e^_r = \sum_se_{sr}\) are the numbers of out and inedges adjacent to block \(r\), respectively.
If
exact == False
, Stirling’s approximation is used in the above expression.If
dense == True
, the likelihood for the nondegreecorrected model becomes instead\[\begin{split}P(\boldsymbol{A}\boldsymbol{e},\boldsymbol{b})^{1} &= \prod_{r<s}{n_rn_s\choose e_{rs}}\prod_r{{n_r\choose 2}\choose e_{rr}/2},\\ P(\boldsymbol{A}\boldsymbol{e},\boldsymbol{b})^{1} &= \prod_{rs}{n_rn_s\choose e_{rs}}\end{split}\]if
multigraph == False
, otherwise we replace \({n\choose m}\to\left(\!\!{n\choose m}\!\!\right)\) above, where \(\left(\!\!{n\choose m}\!\!\right) = {n+m1\choose m}\). A “dense” entropy for the degreecorrected model is not available, and if requested will raise aNotImplementedError
.If
dl == True
, the description length \(\mathcal{L} = \ln P(\boldsymbol{\theta})\) of the model will be returned as well. The terms \(P(\boldsymbol{e})\) and \(P(\boldsymbol{b})\) are described in described as follows.For an undirected graph, the number of distinct \(e_{rs}\) matrices is given by,
\[\Omega_m = \left(\!\!{B(B+1)/2 \choose E}\!\!\right)\]and for a directed graph,
\[\Omega_m = \left(\!\!{B^2 \choose E}\!\!\right)\]where \(\left(\!{n \choose k}\!\right) = {n+k1\choose k}\) is the number of \(k\) combinations with repetitions from a set of size \(n\). Hence, we have the description length of the edge counts
\[\ln P(\boldsymbol{e}) = \ln \Omega_m.\]For the node partition \(\boldsymbol{b}\) we assume a twolevel Bayesian hierarchy, where first the group size histogram is generated, and conditioned on it the partition, which leads to a description length:
\[\ln P(\boldsymbol{b}) = \ln {N  1 \choose B  1} + \ln N!  \sum_r \ln n_r!.\]where \(n_r\) is the number of nodes in block \(r\).
The total information necessary to describe the model is then,
\[\ln P(\boldsymbol{e}, \boldsymbol{b}) = \ln P(\boldsymbol{e})  \ln P(\boldsymbol{b}).\]If
nr
isNone
, it is assumed \(n_r=N/B\). Ifnr
isFalse
, the partition term \(\ln P(\boldsymbol{b})\) is omitted entirely.For the degreecorrected model we need to specify the prior \(P(\boldsymbol{k})\) for the degree sequence as well. Here there are three options:
degree_dl_kind == "uniform"
\[P(\boldsymbol{k}\boldsymbol{e},\boldsymbol{b}) = \prod_r\left(\!\!{n_r\choose e_r}\!\!\right)^{1}.\]This corresponds to a noninformative prior, where the degrees are sampled from a uniform distribution.
degree_dl_kind == "distributed"
(default)\[P(\boldsymbol{k}\boldsymbol{e},\boldsymbol{b}) = \prod_r\frac{\prod_k\eta_k^r!}{n_r!} \prod_r q(e_r, n_r)^{1}\]with \(\eta_k^r\) being the number of nodes with degree \(k\) in group \(r\), and \(q(n,m)\) being the number of partitions of integer \(n\) into at most \(m\) parts.
This corresponds to a prior for the degree sequence conditioned on the degree frequencies, which are themselves sampled from a uniform hyperprior. This option should be preferred in most cases.
degree_dl_kind == "entropy"
\[P(\boldsymbol{k}\boldsymbol{e},\boldsymbol{b}) \approx \prod_r\exp\left(n_rH(\boldsymbol{k}_r)\right)\]where \(H(\boldsymbol{k}_r) = \sum_kp_r(k)\ln p_r(k)\) is the entropy of the degree distribution inside block \(r\).
Note that, differently from the other two choices, this represents only an approximation of the description length. It is meant to be used only for comparison purposes, and should be avoided in practice.
For the directed case, the above expressions are duplicated for the in and outdegrees.
References
 peixotononparametric2017
Tiago P. Peixoto, “Nonparametric Bayesian inference of the microcanonical stochastic block model”, Phys. Rev. E 95 012317 (2017), DOI: 10.1103/PhysRevE.95.012317 [scihub, @tor], arXiv: 1610.02703
 peixotohierarchical2014
Tiago P. Peixoto, “Hierarchical block structures and highresolution model selection in large networks “, Phys. Rev. X 4, 011047 (2014), DOI: 10.1103/PhysRevX.4.011047 [scihub, @tor], arXiv: 1310.4377.
 peixotoweighted2017
Tiago P. Peixoto, “Nonparametric weighted stochastic block models”, Phys. Rev. E 97, 012306 (2018), DOI: 10.1103/PhysRevE.97.012306 [scihub, @tor], arXiv: 1708.01432
 get_matrix()[source]¶
Returns the block matrix (as a sparse
csr_matrix
), which contains the number of edges between each block pair.Warning
This corresponds to the adjacency matrix of the block graph, which by convention includes twice the amount of edges in the diagonal entries if the graph is undirected.
Examples
>>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=5, deg_corr=True) >>> state.mcmc_sweep(niter=1000) (...) >>> m = state.get_matrix() >>> figure() <...> >>> matshow(m.todense()) <...> >>> savefig("bloc_mat.svg")
 virtual_vertex_move(v, s, **kwargs)[source]¶
Computes the entropy difference if vertex
v
is moved to blocks
. The remaining parameters are the same as ingraph_tool.inference.BlockState.entropy()
.
 move_vertex(v, s)[source]¶
Move vertex
v
to blocks
.This optionally accepts a list of vertices and blocks to move simultaneously.
 remove_vertex(v)[source]¶
Remove vertex
v
from its current group.This optionally accepts a list of vertices to remove.
Warning
This will leave the state in an inconsistent state before the vertex is returned to some other group, or if the same vertex is removed twice.
 add_vertex(v, r)[source]¶
Add vertex
v
to blockr
.This optionally accepts a list of vertices and blocks to add.
Warning
This can leave the state in an inconsistent state if a vertex is added twice to the same group.
 sample_vertex_move(v, c=1.0, d=0.1)[source]¶
Sample block membership proposal of vertex
v
according to realvalued sampling parametersc
andd
: For \(c\to 0\) the blocks are sampled according to the local neighborhood and their connections; for \(c\to\infty\) the blocks are sampled randomly. With a probabilityd
, a new (empty) group is sampled.
 get_move_prob(v, s, c=1.0, d=0.1, reverse=False)[source]¶
Compute the logprobability of a move proposal for vertex
v
to blocks
according to sampling parametersc
andd
, as obtained withgraph_tool.inference.BlockState.sample_vertex_move()
. Ifreverse == True
, the reverse probability of moving the node back from blocks
to its current one is obtained.
 get_edges_prob(missing, spurious=[], entropy_args={})[source]¶
Compute the joint logprobability of the missing and spurious edges given by
missing
andspurious
(a list of(source, target)
tuples, orEdge()
instances), together with the observed edges.More precisely, the loglikelihood returned is
\[\ln \frac{P(\boldsymbol G + \delta \boldsymbol G  \boldsymbol b)}{P(\boldsymbol G \boldsymbol b)}\]where \(\boldsymbol G + \delta \boldsymbol G\) is the modified graph (with missing edges added and spurious edges deleted).
The values in
entropy_args
are passed toentropy()
to calculate the logprobability.
 draw(**kwargs)¶
Convenience wrapper to
graph_draw()
that draws the state of the graph as colors on the vertices and edges.
 exhaustive_sweep(entropy_args={}, callback=None, density=None, vertices=None, initial_partition=None, max_iter=None)¶
Perform an exhaustive loop over all possible network partitions.
 Parameters
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. callbackcallable object (optional, default:
None
) Function to be called for each partition, with three arguments
(S, S_min, b_min)
corresponding to the the current entropy value, the minimum entropy value so far, and the corresponding partition, respectively. If not provided, andhist is None
an iterator over the same values will be returned instead. density
tuple
(optional, default:None
) If provided, it should contain a tuple with values
(S_min, S_max, n_bins)
, which will be used to obtain the density of states via a histogram of sizen_bins
. This parameter is ignored unlesscallback is None
. verticesiterable of ints (optional, default:
None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 initial_partitioniterable of ints (optional, default:
None
) If provided, this will provide the initial partition for the iteration.
 max_iter
int
(optional, default:None
) If provided, this will limit the total number of iterations.
 entropy_args
 Returns
 statesiterator over (S, S_min, b_min)
If
callback
isNone
andhist
isNone
, the function will return an iterator over(S, S_min, b_min)
corresponding to the the current entropy value, the minimum entropy value so far, and the corresponding partition, respectively. Ss, countspair of
numpy.ndarray
If
callback is None
andhist is not None
, the function will return the values of each bin (Ss
) and the state count of each bin (counts
). b_min
VertexPropertyMap
If
callback is not None
orhist is not None
, the function will also return partition with smallest entropy.
Notes
This algorithm has an \(O(B^N)\) complexity, where \(B\) is the number of groups, and \(N\) is the number of vertices.
 gibbs_sweep(beta=1.0, niter=1, entropy_args={}, allow_new_group=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a rejectionfree Gibbs MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_new_group
bool
(optional, default:True
) Allow the number of groups to increase and decrease.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\times B)\) complexity, where \(B\) is the number of groups, and \(E\) is the number of edges.
 mcmc_sweep(beta=1.0, c=0.5, d=0.01, niter=1, entropy_args={}, allow_vacate=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given move.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_vacate
bool
(optional, default:True
) Allow groups to be vacated.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 multicanonical_sweep(m_state, multiflip=False, **kwargs)¶
Perform
niter
sweeps of a nonMarkovian multicanonical sampling using the WangLandau algorithm. Parameters
 m_state
MulticanonicalState
MulticanonicalState
instance containing the current state of the WangLandau run. multiflip
bool
(optional, default:False
) If
True
,multiflip_mcmc_sweep()
will be used, otherwisemcmc_sweep()
. **kwargsKeyword parameter list
The remaining parameters will be passed to
multiflip_mcmc_sweep()
ormcmc_sweep()
.
 m_state
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 wangefficient2001
Fugao Wang, D. P. Landau, “An efficient, multiple range random walk algorithm to calculate the density of states”, Phys. Rev. Lett. 86, 2050 (2001), DOI: 10.1103/PhysRevLett.86.2050 [scihub, @tor], arXiv: condmat/0011174
 multiflip_mcmc_sweep(beta=1.0, c=0.5, psingle=None, psplit=1, pmerge=1, pmergesplit=1, pmovelabel=0, d=0.01, gibbs_sweeps=10, niter=1, entropy_args={}, accept_stats=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC with multiple simultaneous moves (i.e. merges and splits) to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. psplit
float
(optional, default:1
) Relative probability of proposing a group split.
 pmergesplit
float
(optional, default:1
) Relative probability of proposing a margesplit move.
 pmovelabel
float
(optional, default:0
) Relative probability of proposing a group label move.
 d
float
(optional, default:1
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 gibbs_sweeps
int
(optional, default:10
) Number of sweeps of Gibbs sampling to be performed (i.e. each node is attempted once per sweep) to refine a split proposal.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotomergesplit2020
Tiago P. Peixoto, “Mergesplit Markov chain Monte Carlo for community detection”, Phys. Rev. E 102, 012305 (2020), DOI: 10.1103/PhysRevE.102.012305 [scihub, @tor], arXiv: 2003.07070
 multilevel_mcmc_sweep(niter=1, beta=1.0, c=0.5, psingle=None, pmultilevel=1, d=0.01, r=0.9, random_bisect=True, merge_sweeps=10, mh_sweeps=10, init_r=0.99, init_beta=1.0, gibbs=False, B_min=1, B_max=18446744073709551615, b_min=None, b_max=None, M=None, cache_states=True, entropy_args={}, verbose=False, **kwargs)¶
Perform
niter
sweeps of a multilevel agglomerative acceptancerejection MCMC to sample network partitions, that uses a bisection search on the number of groups, together with group merges and singenode moves. Parameters
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. pmultilevel
float
(optional, default:1
) Relative probability of proposing a multilevel move.
 d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 r
float
(optional, default:0.9
) Group shrink ratio. The number of groups is reduced by this fraction at each merge sweep.
 random_bisect
bool
(optional, default:True
) If
True
, bisections are done at randomly chosen intervals. Otherwise a Fibonacci sequence is used. merge_sweeps
int
(optional, default:10
) Number of sweeps spent to find good merge proposals.
 mh_sweeps
int
(optional, default:10
) Number of singlenode MetropolisHastings sweeps between merge splits.
 init_r
double
(optional, default:0.99
) Stopping criterion for the intialization phase, after each node is put in their own group, to set the initial upper bound of the bisection search. A number of singlenode MetropolisHastings sweeps is done until the number of groups is shrunk by a factor that is larger than this parameter.
 init_beta
float
(optional, default:1.
) Inverse temperature to be used for the very first sweep of the initialization phase.
 gibbs
bool
(optional, default:False
) If
True
, the single node moves use (slower) Gibbs sampling, rather than MetropolisHastings. B_min
int
(optional, default:1
) Minimum number of groups to be considered in the search.
 b_min
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_min
. B_max
int
(optional, default:1
) Maximum number of groups to be considered in the search.
 b_max
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_max
. M
int
(optional, default:None
) Maximum number of groups to select for the multilevel move. If
None
is provided, then all groups are always elected. cache_states
bool
(optional, default:True
) If
True
, intermediary states will be cached during the bisection search. entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 niter
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\ln^2 N)\) complexity, where \(E\) is the number of edges and \(N\) is the number of nodes (independently of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 collect_edge_marginals(p=None, update=1)[source]¶
Collect the edge marginal histogram, which counts the number of times the endpoints of each node have been assigned to a given block pair.
This should be called multiple times, e.g. after repeated runs of the
graph_tool.inference.BlockState.mcmc_sweep()
function. Parameters
 p
EdgePropertyMap
(optional, default:None
) Edge property map with edge marginals to be updated. If not provided, an empty histogram will be created.
 updatefloat (optional, default:
1
) Each call increases the current count by the amount given by this parameter.
 p
 Returns
 p
EdgePropertyMap
Edge property map with updated edge marginals.
 p
Examples
>>> np.random.seed(42) >>> gt.seed_rng(42) >>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=4, deg_corr=True) >>> pe = None >>> state.mcmc_sweep(niter=1000) # remove part of the transient (...) >>> for i in range(1000): ... ret = state.mcmc_sweep(niter=10) ... pe = state.collect_edge_marginals(pe) >>> gt.bethe_entropy(g, pe)[0] 0.571383...
 collect_vertex_marginals(p=None, b=None, unlabel=False, update=1)[source]¶
Collect the vertex marginal histogram, which counts the number of times a node was assigned to a given block.
This should be called multiple times, e.g. after repeated runs of the
graph_tool.inference.BlockState.mcmc_sweep()
function. Parameters
 p
VertexPropertyMap
(optional, default:None
) Vertex property map with vectortype values, storing the previous block membership counts. If not provided, an empty histogram will be created.
 b
VertexPropertyMap
(optional, default:None
) Vertex property map with group partition. If not provided, the state’s partition will be used.
 unlabelbool (optional, default:
False
) If
True
, a canonical labelling of the groups will be used, so that each partition is uniquely represented. updateint (optional, default:
1
) Each call increases the current count by the amount given by this parameter.
 p
 Returns
 p
VertexPropertyMap
Vertex property map with vectortype values, storing the accumulated block membership counts.
 p
Examples
>>> np.random.seed(42) >>> gt.seed_rng(42) >>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=4, deg_corr=True) >>> pv = None >>> state.mcmc_sweep(niter=1000) # remove part of the transient (...) >>> for i in range(1000): ... ret = state.mcmc_sweep(niter=10) ... pv = state.collect_vertex_marginals(pv) >>> gt.mf_entropy(g, pv) 15.037062... >>> gt.graph_draw(g, pos=g.vp["pos"], vertex_shape="pie", ... vertex_pie_fractions=pv, output="polbooks_blocks_soft_B4.svg") <...>
 collect_partition_histogram(h=None, update=1, unlabel=True)[source]¶
Collect a histogram of partitions.
This should be called multiple times, e.g. after repeated runs of the
graph_tool.inference.BlockState.mcmc_sweep()
function. Parameters
 h
PartitionHist
(optional, default:None
) Partition histogram. If not provided, an empty histogram will be created.
 updatefloat (optional, default:
1
) Each call increases the current count by the amount given by this parameter.
 unlabelbool (optional, default:
True
) If
True
, a canonical labelling of the groups will be used, so that each partition is uniquely represented.
 h
 Returns
 h
PartitionHist
(optional, default:None
) Updated Partition histogram.
 h
Examples
>>> np.random.seed(42) >>> gt.seed_rng(42) >>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=4, deg_corr=True) >>> ph = None >>> state.mcmc_sweep(niter=1000) # remove part of the transient (...) >>> for i in range(1000): ... ret = state.mcmc_sweep(niter=10) ... ph = state.collect_partition_histogram(ph) >>> gt.microstate_entropy(ph) 126.171367...
 sample_graph(canonical=False, multigraph=True, self_loops=True, sample_params=False, max_ent=False, n_iter=1000)[source]¶
Sample a new graph from the fitted model.
 Parameters
 canonical
bool
(optional, default:False
) If
canonical == True
, the graph will be sampled from the maximumlikelihood estimate of the canonical stochastic block model. Otherwise, it will be sampled from the microcanonical model. multigraph
bool
(optional, default:True
) If
True
, parallel edges will be allowed. selfloops
bool
(optional, default:True
) If
True
, selfloops will be allowed. sample_params
bool
(optional, default:True
) If
True
, andcanonical == True
andmax_ent == False
, the count parameters (edges between groups and node degrees) will be sampled from their posterior distribution conditioned on the actual state. Otherwise, their maximumlikelihood values will be used. max_ent
bool
(optional, default:False
) If
True
, maximumentropy model variants will be used. n_iter
int
(optional, default:1000
) Number of iterations used (only relevant if
canonical == False
andmax_ent == True
).
 canonical
 Returns
 g
Graph
Generated graph.
 g
Notes
This function is just a convenience wrapper to
generate_sbm()
. However, ifmax_ent==True
andcanonical == False
it wrapsrandom_rewire()
instead.Examples
>>> g = gt.collection.data["polbooks"] >>> state = gt.minimize_blockmodel_dl(g, multilevel_mcmc_args=dict(B_max=3)) >>> u = state.sample_graph(canonical=True, self_loops=False, multigraph=False) >>> ustate = gt.BlockState(u, b=state.b) >>> state.draw(pos=g.vp.pos, output="polbookssbm.svg") <...> >>> ustate.draw(pos=u.own_property(g.vp.pos), output="polbookssbmsampled.svg") <...>
Left: Political books network. Right: Sample from the degreecorrected SBM fitted to the original network.
 class graph_tool.inference.OverlapBlockState(g, b=None, B=None, recs=[], rec_types=[], rec_params=[], clabel=None, pclabel=None, deg_corr=True, dense_bg=False, **kwargs)[source]¶
Bases:
graph_tool.inference.blockmodel.BlockState
The overlapping stochastic block model state of a given graph.
 Parameters
 g
Graph
Graph to be modelled.
 b
VertexPropertyMap
ornumpy.ndarray
(optional, default:None
) Initial block labels on the vertices or halfedges. If not supplied, it will be randomly sampled. If the value passed is a vertex property map, it will be assumed to be a nonoverlapping partition of the vertices. If it is an edge property map, it should contain a vector for each edge, with the block labels at each end point (sorted according to their vertex index, in the case of undirected graphs, otherwise from source to target). If the value is an
numpy.ndarray
, it will be assumed to correspond directly to a partition of the list of halfedges. B
int
(optional, default:None
) Number of blocks (or vertex groups). If not supplied it will be obtained from the parameter
b
. recslist of
EdgePropertyMap
instances (optional, default:[]
) List of real or discretevalued edge covariates.
 rec_typeslist of edge covariate types (optional, default:
[]
) List of types of edge covariates. The possible types are:
"realexponential"
,"realnormal"
,"discretegeometric"
,"discretepoisson"
or"discretebinomial"
. rec_paramslist of
dict
(optional, default:[]
) Model hyperparameters for edge covariates. This should a list of
dict
instances. SeeBlockState
for more details. clabel
VertexPropertyMap
(optional, default:None
) Constraint labels on the vertices. If supplied, vertices with different label values will not be clustered in the same group.
 deg_corr
bool
(optional, default:True
) If
True
, the degreecorrected version of the blockmodel ensemble will be assumed, otherwise the traditional variant will be used. dense_bg
bool
(optional, default:False
) If
True
a dense matrix is used for the block graph, otherwise a sparse matrix will be used.
 g
 copy(g=None, b=None, B=None, deg_corr=None, clabel=None, pclabel=None, **kwargs)[source]¶
Copies the block state. The parameters override the state properties, and have the same meaning as in the constructor. If
overlap=False
an instance ofBlockState
is returned. This is by default a shallow copy.
 get_edge_blocks()[source]¶
Returns an edge property map which contains the block labels pairs for each edge.
 get_overlap_blocks()[source]¶
Returns the mixed membership of each vertex.
 Returns
 bv
VertexPropertyMap
A vectorvalued vertex property map containing the block memberships of each node.
 bc_in
VertexPropertyMap
The labelled indegrees of each node, i.e. how many inedges belong to each group, in the same order as the
bv
property above. bc_out
VertexPropertyMap
The labelled outdegrees of each node, i.e. how many outedges belong to each group, in the same order as the
bv
property above. bc_total
VertexPropertyMap
The labelled total degrees of each node, i.e. how many incident edges belong to each group, in the same order as the
bv
property above.
 bv
 get_nonoverlap_blocks()[source]¶
Returns a scalarvalued vertex property map with the block mixture represented as a single number.
 get_majority_blocks()[source]¶
Returns a scalarvalued vertex property map with the majority block membership of each node.
 get_bclabel(clabel=None)[source]¶
Returns a
VertexPropertyMap
corresponding to constraint labels for the block graph.
 entropy(adjacency=True, dl=True, partition_dl=True, degree_dl=True, degree_dl_kind='distributed', edges_dl=True, dense=False, multigraph=True, deg_entropy=True, recs=True, recs_dl=True, beta_dl=1.0, exact=True, **kwargs)[source]¶
Calculate the entropy associated with the current block partition.
 Parameters
 adjacency
bool
(optional, default:True
) If
True
, the adjacency term of the description length will be included. dl
bool
(optional, default:True
) If
True
, the description length for the parameters will be included. partition_dl
bool
(optional, default:True
) If
True
, anddl == True
the partition description length will be included. degree_dl
bool
(optional, default:True
) If
True
, anddl == True
the degree sequence description length will be included (for degreecorrected models). degree_dl_kind
str
(optional, default:"distributed"
) This specifies the prior used for the degree sequence. It must be one of:
"uniform"
,"distributed"
(default) or"entropy"
. edges_dl
bool
(optional, default:True
) If
True
, anddl == True
the edge matrix description length will be included. dense
bool
(optional, default:False
) If
True
, the “dense” variant of the entropy will be computed. multigraph
bool
(optional, default:True
) If
True
, the multigraph entropy will be used. deg_entropy
bool
(optional, default:True
) If
True
, the degree entropy term that is independent of the network partition will be included (for degreecorrected models). recs
bool
(optional, default:True
) If
True
, the likelihood for real or discretevalued edge covariates is computed. recs_dl
bool
(optional, default:True
) If
True
, anddl == True
the edge covariate description length will be included. beta_dl
double
(optional, default:1.
) Prior inverse temperature.
 exact
bool
(optional, default:True
) If
True
, the exact expressions will be used. Otherwise, Stirling’s factorial approximation will be used for some terms.
 adjacency
Notes
The “entropy” of the state is minus the loglikelihood of the microcanonical SBM, that includes the generated graph \(\boldsymbol{A}\) and the model parameters \(\boldsymbol{\theta}\),
\[\begin{split}\mathcal{S} &=  \ln P(\boldsymbol{A},\boldsymbol{\theta}) \\ &=  \ln P(\boldsymbol{A}\boldsymbol{\theta})  \ln P(\boldsymbol{\theta}).\end{split}\]This value is also called the description length of the data, and it corresponds to the amount of information required to describe it (in nats).
For the traditional blockmodel (
deg_corr == False
), the model parameters are \(\boldsymbol{\theta} = \{\boldsymbol{e}, \boldsymbol{b}\}\), where \(\boldsymbol{e}\) is the matrix of edge counts between blocks, and \(\boldsymbol{b}\) is the overlapping partition of the nodes into blocks. For the degreecorrected blockmodel (deg_corr == True
), we have an additional set of parameters, namely the labelled degree sequence \(\boldsymbol{k}\).The model likelihood \(P(\boldsymbol{A}\theta)\) is given analogously to the nonoverlapping case, as described in
graph_tool.inference.BlockState.entropy()
.If
dl == True
, the description length \(\mathcal{L} = \ln P(\boldsymbol{\theta})\) of the model will be returned as well. The edgecount prior \(P(\boldsymbol{e})\) is described in described inentropy()
. For the overlapping partition \(P(\boldsymbol{b})\), we have\[\ln P(\boldsymbol{b}) = \ln\left(\!\!{D \choose N}\!\!\right) + \sum_d \ln {\left(\!\!{{B\choose d}\choose n_d}\!\!\right)} + \ln N!  \sum_{\vec{b}}\ln n_{\vec{b}}!,\]where \(d \equiv \vec{b}_1 = \sum_rb_r\) is the mixture size, \(n_d\) is the number of nodes in a mixture of size \(d\), \(D\) is the maximum value of \(d\), \(n_{\vec{b}}\) is the number of nodes in mixture \(\vec{b}\).
For the degreecorrected model we need to specify the prior \(P(\boldsymbol{k})\) for the labelled degree sequence as well:
\[\ln P(\boldsymbol{k}) = \sum_r\ln\left(\!\!{m_r \choose e_r}\!\!\right)  \sum_{\vec{b}}\ln P(\boldsymbol{k}{\vec{b}}),\]where \(m_r\) is the number of nonempty mixtures which contain type \(r\), and \(P(\boldsymbol{k}{\vec{b}})\) is the likelihood of the labelled degree sequence inside mixture \(\vec{b}\). For this term we have three options:
degree_dl_kind == "uniform"
\[P(\boldsymbol{k}\vec{b}) = \prod_r\left(\!\!{n_{\vec{b}}\choose e^r_{\vec{b}}}\!\!\right)^{1}.\]degree_dl_kind == "distributed"
\[P(\boldsymbol{k}\vec{b}) = \prod_{\vec{b}}\frac{\prod_{\vec{k}}\eta_{\vec{k}}^{\vec{b}}!}{n_{\vec{b}}!} \prod_r q(e_{\vec{b}}^r  n_{\vec{b}}, n_{\vec{b}})\]where \(n^{\vec{b}}_{\vec{k}}\) is the number of nodes in mixture \(\vec{b}\) with labelled degree \(\vec{k}\), and \(q(n,m)\) is the number of partitions of integer \(n\) into at most \(m\) parts.
degree_dl_kind == "entropy"
\[P(\boldsymbol{k}\vec{b}) = \prod_{\vec{b}}\exp\left(n_{\vec{b}}H(\boldsymbol{k}_{\vec{b}})\right)\]where \(H(\boldsymbol{k}_{\vec{b}}) = \sum_{\vec{k}}p_{\vec{b}}(\vec{k})\ln p_{\vec{b}}(\vec{k})\) is the entropy of the labelled degree distribution inside mixture \(\vec{b}\).
Note that, differently from the other two choices, this represents only an approximation of the description length. It is meant to be used only for comparison purposes, and should be avoided in practice.
For the directed case, the above expressions are duplicated for the in and outdegrees.
 mcmc_sweep(bundled=False, **kwargs)[source]¶
Perform sweeps of a MetropolisHastings rejection sampling MCMC to sample network partitions. If
bundled == True
, the halfedges incident of the same node that belong to the same group are moved together. All remaining parameters are passed tograph_tool.inference.BlockState.mcmc_sweep()
.
 add_vertex(v, r)¶
Add vertex
v
to blockr
.This optionally accepts a list of vertices and blocks to add.
Warning
This can leave the state in an inconsistent state if a vertex is added twice to the same group.
 collect_edge_marginals(p=None, update=1)¶
Collect the edge marginal histogram, which counts the number of times the endpoints of each node have been assigned to a given block pair.
This should be called multiple times, e.g. after repeated runs of the
graph_tool.inference.BlockState.mcmc_sweep()
function. Parameters
 p
EdgePropertyMap
(optional, default:None
) Edge property map with edge marginals to be updated. If not provided, an empty histogram will be created.
 updatefloat (optional, default:
1
) Each call increases the current count by the amount given by this parameter.
 p
 Returns
 p
EdgePropertyMap
Edge property map with updated edge marginals.
 p
Examples
>>> np.random.seed(42) >>> gt.seed_rng(42) >>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=4, deg_corr=True) >>> pe = None >>> state.mcmc_sweep(niter=1000) # remove part of the transient (...) >>> for i in range(1000): ... ret = state.mcmc_sweep(niter=10) ... pe = state.collect_edge_marginals(pe) >>> gt.bethe_entropy(g, pe)[0] 0.571383...
 collect_partition_histogram(h=None, update=1, unlabel=True)¶
Collect a histogram of partitions.
This should be called multiple times, e.g. after repeated runs of the
graph_tool.inference.BlockState.mcmc_sweep()
function. Parameters
 h
PartitionHist
(optional, default:None
) Partition histogram. If not provided, an empty histogram will be created.
 updatefloat (optional, default:
1
) Each call increases the current count by the amount given by this parameter.
 unlabelbool (optional, default:
True
) If
True
, a canonical labelling of the groups will be used, so that each partition is uniquely represented.
 h
 Returns
 h
PartitionHist
(optional, default:None
) Updated Partition histogram.
 h
Examples
>>> np.random.seed(42) >>> gt.seed_rng(42) >>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=4, deg_corr=True) >>> ph = None >>> state.mcmc_sweep(niter=1000) # remove part of the transient (...) >>> for i in range(1000): ... ret = state.mcmc_sweep(niter=10) ... ph = state.collect_partition_histogram(ph) >>> gt.microstate_entropy(ph) 126.171367...
 collect_vertex_marginals(p=None, b=None, unlabel=False, update=1)¶
Collect the vertex marginal histogram, which counts the number of times a node was assigned to a given block.
This should be called multiple times, e.g. after repeated runs of the
graph_tool.inference.BlockState.mcmc_sweep()
function. Parameters
 p
VertexPropertyMap
(optional, default:None
) Vertex property map with vectortype values, storing the previous block membership counts. If not provided, an empty histogram will be created.
 b
VertexPropertyMap
(optional, default:None
) Vertex property map with group partition. If not provided, the state’s partition will be used.
 unlabelbool (optional, default:
False
) If
True
, a canonical labelling of the groups will be used, so that each partition is uniquely represented. updateint (optional, default:
1
) Each call increases the current count by the amount given by this parameter.
 p
 Returns
 p
VertexPropertyMap
Vertex property map with vectortype values, storing the accumulated block membership counts.
 p
Examples
>>> np.random.seed(42) >>> gt.seed_rng(42) >>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=4, deg_corr=True) >>> pv = None >>> state.mcmc_sweep(niter=1000) # remove part of the transient (...) >>> for i in range(1000): ... ret = state.mcmc_sweep(niter=10) ... pv = state.collect_vertex_marginals(pv) >>> gt.mf_entropy(g, pv) 15.037062... >>> gt.graph_draw(g, pos=g.vp["pos"], vertex_shape="pie", ... vertex_pie_fractions=pv, output="polbooks_blocks_soft_B4.svg") <...>
 exhaustive_sweep(entropy_args={}, callback=None, density=None, vertices=None, initial_partition=None, max_iter=None)¶
Perform an exhaustive loop over all possible network partitions.
 Parameters
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. callbackcallable object (optional, default:
None
) Function to be called for each partition, with three arguments
(S, S_min, b_min)
corresponding to the the current entropy value, the minimum entropy value so far, and the corresponding partition, respectively. If not provided, andhist is None
an iterator over the same values will be returned instead. density
tuple
(optional, default:None
) If provided, it should contain a tuple with values
(S_min, S_max, n_bins)
, which will be used to obtain the density of states via a histogram of sizen_bins
. This parameter is ignored unlesscallback is None
. verticesiterable of ints (optional, default:
None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 initial_partitioniterable of ints (optional, default:
None
) If provided, this will provide the initial partition for the iteration.
 max_iter
int
(optional, default:None
) If provided, this will limit the total number of iterations.
 entropy_args
 Returns
 statesiterator over (S, S_min, b_min)
If
callback
isNone
andhist
isNone
, the function will return an iterator over(S, S_min, b_min)
corresponding to the the current entropy value, the minimum entropy value so far, and the corresponding partition, respectively. Ss, countspair of
numpy.ndarray
If
callback is None
andhist is not None
, the function will return the values of each bin (Ss
) and the state count of each bin (counts
). b_min
VertexPropertyMap
If
callback is not None
orhist is not None
, the function will also return partition with smallest entropy.
Notes
This algorithm has an \(O(B^N)\) complexity, where \(B\) is the number of groups, and \(N\) is the number of vertices.
 get_Be()¶
Returns the effective number of blocks, defined as \(e^{H}\), with \(H=\sum_r\frac{n_r}{N}\ln \frac{n_r}{N}\), where \(n_r\) is the number of nodes in group r.
 get_bg()¶
Returns the block graph.
 get_block_state(b=None, vweight=False, **kwargs)¶
Returns a
BlockState
corresponding to the block graph (i.e. the blocks of the current state become the nodes). The parameters have the same meaning as the in the constructor. Ifvweight == True
the nodes of the block state are weighted with the node counts.
 get_blocks()¶
Returns the property map which contains the block labels for each vertex.
 get_bpclabel()¶
Returns a
VertexPropertyMap
corresponding to partition constraint labels for the block graph.
 get_edges_prob(missing, spurious=[], entropy_args={})¶
Compute the joint logprobability of the missing and spurious edges given by
missing
andspurious
(a list of(source, target)
tuples, orEdge()
instances), together with the observed edges.More precisely, the loglikelihood returned is
\[\ln \frac{P(\boldsymbol G + \delta \boldsymbol G  \boldsymbol b)}{P(\boldsymbol G \boldsymbol b)}\]where \(\boldsymbol G + \delta \boldsymbol G\) is the modified graph (with missing edges added and spurious edges deleted).
The values in
entropy_args
are passed toentropy()
to calculate the logprobability.
 get_er()¶
Returns the vertex property map of the block graph which contains the number \(e_r\) of halfedges incident on block \(r\). If the graph is directed, a pair of property maps is returned, with the number of outedges \(e^+_r\) and inedges \(e^_r\), respectively.
 get_ers()¶
Returns the edge property map of the block graph which contains the \(e_{rs}\) matrix entries. For undirected graphs, the diagonal values (selfloops) contain \(e_{rr}/2\).
 get_matrix()¶
Returns the block matrix (as a sparse
csr_matrix
), which contains the number of edges between each block pair.Warning
This corresponds to the adjacency matrix of the block graph, which by convention includes twice the amount of edges in the diagonal entries if the graph is undirected.
Examples
>>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=5, deg_corr=True) >>> state.mcmc_sweep(niter=1000) (...) >>> m = state.get_matrix() >>> figure() <...> >>> matshow(m.todense()) <...> >>> savefig("bloc_mat.svg")
 get_move_prob(v, s, c=1.0, d=0.1, reverse=False)¶
Compute the logprobability of a move proposal for vertex
v
to blocks
according to sampling parametersc
andd
, as obtained withgraph_tool.inference.BlockState.sample_vertex_move()
. Ifreverse == True
, the reverse probability of moving the node back from blocks
to its current one is obtained.
 get_nr()¶
Returns the vertex property map of the block graph which contains the block sizes \(n_r\).
 get_rec_params()¶
Get model hyperparameters for edge covariates.
 get_state()¶
Alias to
get_blocks()
.
 gibbs_sweep(beta=1.0, niter=1, entropy_args={}, allow_new_group=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a rejectionfree Gibbs MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_new_group
bool
(optional, default:True
) Allow the number of groups to increase and decrease.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\times B)\) complexity, where \(B\) is the number of groups, and \(E\) is the number of edges.
 move_vertex(v, s)¶
Move vertex
v
to blocks
.This optionally accepts a list of vertices and blocks to move simultaneously.
 multicanonical_sweep(m_state, multiflip=False, **kwargs)¶
Perform
niter
sweeps of a nonMarkovian multicanonical sampling using the WangLandau algorithm. Parameters
 m_state
MulticanonicalState
MulticanonicalState
instance containing the current state of the WangLandau run. multiflip
bool
(optional, default:False
) If
True
,multiflip_mcmc_sweep()
will be used, otherwisemcmc_sweep()
. **kwargsKeyword parameter list
The remaining parameters will be passed to
multiflip_mcmc_sweep()
ormcmc_sweep()
.
 m_state
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 wangefficient2001
Fugao Wang, D. P. Landau, “An efficient, multiple range random walk algorithm to calculate the density of states”, Phys. Rev. Lett. 86, 2050 (2001), DOI: 10.1103/PhysRevLett.86.2050 [scihub, @tor], arXiv: condmat/0011174
 multiflip_mcmc_sweep(beta=1.0, c=0.5, psingle=None, psplit=1, pmerge=1, pmergesplit=1, pmovelabel=0, d=0.01, gibbs_sweeps=10, niter=1, entropy_args={}, accept_stats=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC with multiple simultaneous moves (i.e. merges and splits) to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. psplit
float
(optional, default:1
) Relative probability of proposing a group split.
 pmergesplit
float
(optional, default:1
) Relative probability of proposing a margesplit move.
 pmovelabel
float
(optional, default:0
) Relative probability of proposing a group label move.
 d
float
(optional, default:1
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 gibbs_sweeps
int
(optional, default:10
) Number of sweeps of Gibbs sampling to be performed (i.e. each node is attempted once per sweep) to refine a split proposal.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotomergesplit2020
Tiago P. Peixoto, “Mergesplit Markov chain Monte Carlo for community detection”, Phys. Rev. E 102, 012305 (2020), DOI: 10.1103/PhysRevE.102.012305 [scihub, @tor], arXiv: 2003.07070
 multilevel_mcmc_sweep(niter=1, beta=1.0, c=0.5, psingle=None, pmultilevel=1, d=0.01, r=0.9, random_bisect=True, merge_sweeps=10, mh_sweeps=10, init_r=0.99, init_beta=1.0, gibbs=False, B_min=1, B_max=18446744073709551615, b_min=None, b_max=None, M=None, cache_states=True, entropy_args={}, verbose=False, **kwargs)¶
Perform
niter
sweeps of a multilevel agglomerative acceptancerejection MCMC to sample network partitions, that uses a bisection search on the number of groups, together with group merges and singenode moves. Parameters
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. pmultilevel
float
(optional, default:1
) Relative probability of proposing a multilevel move.
 d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 r
float
(optional, default:0.9
) Group shrink ratio. The number of groups is reduced by this fraction at each merge sweep.
 random_bisect
bool
(optional, default:True
) If
True
, bisections are done at randomly chosen intervals. Otherwise a Fibonacci sequence is used. merge_sweeps
int
(optional, default:10
) Number of sweeps spent to find good merge proposals.
 mh_sweeps
int
(optional, default:10
) Number of singlenode MetropolisHastings sweeps between merge splits.
 init_r
double
(optional, default:0.99
) Stopping criterion for the intialization phase, after each node is put in their own group, to set the initial upper bound of the bisection search. A number of singlenode MetropolisHastings sweeps is done until the number of groups is shrunk by a factor that is larger than this parameter.
 init_beta
float
(optional, default:1.
) Inverse temperature to be used for the very first sweep of the initialization phase.
 gibbs
bool
(optional, default:False
) If
True
, the single node moves use (slower) Gibbs sampling, rather than MetropolisHastings. B_min
int
(optional, default:1
) Minimum number of groups to be considered in the search.
 b_min
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_min
. B_max
int
(optional, default:1
) Maximum number of groups to be considered in the search.
 b_max
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_max
. M
int
(optional, default:None
) Maximum number of groups to select for the multilevel move. If
None
is provided, then all groups are always elected. cache_states
bool
(optional, default:True
) If
True
, intermediary states will be cached during the bisection search. entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 niter
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\ln^2 N)\) complexity, where \(E\) is the number of edges and \(N\) is the number of nodes (independently of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 remove_vertex(v)¶
Remove vertex
v
from its current group.This optionally accepts a list of vertices to remove.
Warning
This will leave the state in an inconsistent state before the vertex is returned to some other group, or if the same vertex is removed twice.
 sample_graph(canonical=False, multigraph=True, self_loops=True, sample_params=False, max_ent=False, n_iter=1000)¶
Sample a new graph from the fitted model.
 Parameters
 canonical
bool
(optional, default:False
) If
canonical == True
, the graph will be sampled from the maximumlikelihood estimate of the canonical stochastic block model. Otherwise, it will be sampled from the microcanonical model. multigraph
bool
(optional, default:True
) If
True
, parallel edges will be allowed. selfloops
bool
(optional, default:True
) If
True
, selfloops will be allowed. sample_params
bool
(optional, default:True
) If
True
, andcanonical == True
andmax_ent == False
, the count parameters (edges between groups and node degrees) will be sampled from their posterior distribution conditioned on the actual state. Otherwise, their maximumlikelihood values will be used. max_ent
bool
(optional, default:False
) If
True
, maximumentropy model variants will be used. n_iter
int
(optional, default:1000
) Number of iterations used (only relevant if
canonical == False
andmax_ent == True
).
 canonical
 Returns
 g
Graph
Generated graph.
 g
Notes
This function is just a convenience wrapper to
generate_sbm()
. However, ifmax_ent==True
andcanonical == False
it wrapsrandom_rewire()
instead.Examples
>>> g = gt.collection.data["polbooks"] >>> state = gt.minimize_blockmodel_dl(g, multilevel_mcmc_args=dict(B_max=3)) >>> u = state.sample_graph(canonical=True, self_loops=False, multigraph=False) >>> ustate = gt.BlockState(u, b=state.b) >>> state.draw(pos=g.vp.pos, output="polbookssbm.svg") <...> >>> ustate.draw(pos=u.own_property(g.vp.pos), output="polbookssbmsampled.svg") <...>
Left: Political books network. Right: Sample from the degreecorrected SBM fitted to the original network.
 sample_vertex_move(v, c=1.0, d=0.1)¶
Sample block membership proposal of vertex
v
according to realvalued sampling parametersc
andd
: For \(c\to 0\) the blocks are sampled according to the local neighborhood and their connections; for \(c\to\infty\) the blocks are sampled randomly. With a probabilityd
, a new (empty) group is sampled.
 set_rec_params(params)¶
Update model hyperparameters for edge covariates.
 set_state(b)¶
Sets the internal partition of the state.
 virtual_vertex_move(v, s, **kwargs)¶
Computes the entropy difference if vertex
v
is moved to blocks
. The remaining parameters are the same as ingraph_tool.inference.BlockState.entropy()
.
 draw(**kwargs)[source]¶
Convenience wrapper to
graph_draw()
that draws the state of the graph as colors on the vertices and edges.
 class graph_tool.inference.LayeredBlockState(g, ec, eweight=None, vweight=None, recs=[], rec_types=[], rec_params=[], b=None, B=None, clabel=None, pclabel=None, layers=False, deg_corr=True, overlap=False, **kwargs)[source]¶
Bases:
graph_tool.inference.overlap_blockmodel.OverlapBlockState
,graph_tool.inference.blockmodel.BlockState
The (possibly overlapping) block state of a given graph, where the edges are divided into discrete layers.
 Parameters
 g
Graph
Graph to be modelled.
 ec
EdgePropertyMap
Edge property map containing discrete edge covariates that will split the network in discrete layers.
 recslist of
EdgePropertyMap
instances (optional, default:[]
) List of real or discretevalued edge covariates.
 rec_typeslist of edge covariate types (optional, default:
[]
) List of types of edge covariates. The possible types are:
"realexponential"
,"realnormal"
,"discretegeometric"
,"discretepoisson"
or"discretebinomial"
. rec_paramslist of
dict
(optional, default:[]
) Model hyperparameters for edge covariates. This should a list of
dict
instances. SeeBlockState
for more details. eweight
EdgePropertyMap
(optional, default:None
) Edge multiplicities (for multigraphs or block graphs).
 vweight
VertexPropertyMap
(optional, default:None
) Vertex multiplicities (for block graphs).
 b
VertexPropertyMap
ornumpy.ndarray
(optional, default:None
) Initial block labels on the vertices or halfedges. If not supplied, it will be randomly sampled.
 B
int
(optional, default:None
) Number of blocks (or vertex groups). If not supplied it will be obtained from the parameter
b
. clabel
VertexPropertyMap
(optional, default:None
) Constraint labels on the vertices. If supplied, vertices with different label values will not be clustered in the same group.
 pclabel
VertexPropertyMap
(optional, default:None
) Partition constraint labels on the vertices. This has the same interpretation as
clabel
, but will be used to compute the partition description length. layers
bool
(optional, default:False
) If
layers == True
, the “independent layers” version of the model is used, instead of the “edge covariates” version. deg_corr
bool
(optional, default:True
) If
True
, the degreecorrected version of the blockmodel ensemble will be assumed, otherwise the traditional variant will be used. overlap
bool
(optional, default:False
) If
True
, the overlapping version of the model will be used.
 g
 copy(g=None, eweight=None, vweight=None, b=None, B=None, deg_corr=None, clabel=None, pclabel=None, bfield=None, overlap=None, layers=None, ec=None, **kwargs)[source]¶
Copies the block state. The parameters override the state properties, and have the same meaning as in the constructor.
 get_block_state(b=None, vweight=False, deg_corr=False, overlap=False, layers=None, **kwargs)[source]¶
Returns a
LayeredBlockState
corresponding to the block graph. The parameters have the same meaning as the in the constructor.
 get_edge_blocks()[source]¶
Returns an edge property map which contains the block labels pairs for each edge.
 get_overlap_blocks()[source]¶
Returns the mixed membership of each vertex.
 Returns
 bv
VertexPropertyMap
A vectorvalued vertex property map containing the block memberships of each node.
 bc_in
VertexPropertyMap
The labelled indegrees of each node, i.e. how many inedges belong to each group, in the same order as the
bv
property above. bc_out
VertexPropertyMap
The labelled outdegrees of each node, i.e. how many outedges belong to each group, in the same order as the
bv
property above. bc_total
VertexPropertyMap
The labelled total degrees of each node, i.e. how many incident edges belong to each group, in the same order as the
bv
property above.
 bv
 get_nonoverlap_blocks()[source]¶
Returns a scalarvalued vertex property map with the block mixture represented as a single number.
 get_majority_blocks()[source]¶
Returns a scalarvalued vertex property map with the majority block membership of each node.
 entropy(adjacency=True, dl=True, partition_dl=True, degree_dl=True, degree_dl_kind='distributed', edges_dl=True, dense=False, multigraph=True, deg_entropy=True, exact=True, **kwargs)[source]¶
Calculate the entropy associated with the current block partition. The meaning of the parameters are the same as in
graph_tool.inference.BlockState.entropy()
.
 get_edges_prob(missing, spurious=[], entropy_args={})[source]¶
Compute the joint logprobability of the missing and spurious edges given by
missing
andspurious
(a list of(source, target, layer)
tuples, orEdge()
instances), together with the observed edges.More precisely, the loglikelihood returned is
\[\ln \frac{P(\boldsymbol G + \delta \boldsymbol G  \boldsymbol b)}{P(\boldsymbol G \boldsymbol b)}\]where \(\boldsymbol G + \delta \boldsymbol G\) is the modified graph (with missing edges added and spurious edges deleted).
The values in
entropy_args
are passed tograph_tool.inference.BlockState.entropy()
to calculate the logprobability.
 add_vertex(v, r)¶
Add vertex
v
to blockr
.This optionally accepts a list of vertices and blocks to add.
Warning
This can leave the state in an inconsistent state if a vertex is added twice to the same group.
 collect_edge_marginals(p=None, update=1)¶
Collect the edge marginal histogram, which counts the number of times the endpoints of each node have been assigned to a given block pair.
This should be called multiple times, e.g. after repeated runs of the
graph_tool.inference.BlockState.mcmc_sweep()
function. Parameters
 p
EdgePropertyMap
(optional, default:None
) Edge property map with edge marginals to be updated. If not provided, an empty histogram will be created.
 updatefloat (optional, default:
1
) Each call increases the current count by the amount given by this parameter.
 p
 Returns
 p
EdgePropertyMap
Edge property map with updated edge marginals.
 p
Examples
>>> np.random.seed(42) >>> gt.seed_rng(42) >>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=4, deg_corr=True) >>> pe = None >>> state.mcmc_sweep(niter=1000) # remove part of the transient (...) >>> for i in range(1000): ... ret = state.mcmc_sweep(niter=10) ... pe = state.collect_edge_marginals(pe) >>> gt.bethe_entropy(g, pe)[0] 0.571383...
 collect_partition_histogram(h=None, update=1, unlabel=True)¶
Collect a histogram of partitions.
This should be called multiple times, e.g. after repeated runs of the
graph_tool.inference.BlockState.mcmc_sweep()
function. Parameters
 h
PartitionHist
(optional, default:None
) Partition histogram. If not provided, an empty histogram will be created.
 updatefloat (optional, default:
1
) Each call increases the current count by the amount given by this parameter.
 unlabelbool (optional, default:
True
) If
True
, a canonical labelling of the groups will be used, so that each partition is uniquely represented.
 h
 Returns
 h
PartitionHist
(optional, default:None
) Updated Partition histogram.
 h
Examples
>>> np.random.seed(42) >>> gt.seed_rng(42) >>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=4, deg_corr=True) >>> ph = None >>> state.mcmc_sweep(niter=1000) # remove part of the transient (...) >>> for i in range(1000): ... ret = state.mcmc_sweep(niter=10) ... ph = state.collect_partition_histogram(ph) >>> gt.microstate_entropy(ph) 126.171367...
 collect_vertex_marginals(p=None, b=None, unlabel=False, update=1)¶
Collect the vertex marginal histogram, which counts the number of times a node was assigned to a given block.
This should be called multiple times, e.g. after repeated runs of the
graph_tool.inference.BlockState.mcmc_sweep()
function. Parameters
 p
VertexPropertyMap
(optional, default:None
) Vertex property map with vectortype values, storing the previous block membership counts. If not provided, an empty histogram will be created.
 b
VertexPropertyMap
(optional, default:None
) Vertex property map with group partition. If not provided, the state’s partition will be used.
 unlabelbool (optional, default:
False
) If
True
, a canonical labelling of the groups will be used, so that each partition is uniquely represented. updateint (optional, default:
1
) Each call increases the current count by the amount given by this parameter.
 p
 Returns
 p
VertexPropertyMap
Vertex property map with vectortype values, storing the accumulated block membership counts.
 p
Examples
>>> np.random.seed(42) >>> gt.seed_rng(42) >>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=4, deg_corr=True) >>> pv = None >>> state.mcmc_sweep(niter=1000) # remove part of the transient (...) >>> for i in range(1000): ... ret = state.mcmc_sweep(niter=10) ... pv = state.collect_vertex_marginals(pv) >>> gt.mf_entropy(g, pv) 15.037062... >>> gt.graph_draw(g, pos=g.vp["pos"], vertex_shape="pie", ... vertex_pie_fractions=pv, output="polbooks_blocks_soft_B4.svg") <...>
 exhaustive_sweep(entropy_args={}, callback=None, density=None, vertices=None, initial_partition=None, max_iter=None)¶
Perform an exhaustive loop over all possible network partitions.
 Parameters
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. callbackcallable object (optional, default:
None
) Function to be called for each partition, with three arguments
(S, S_min, b_min)
corresponding to the the current entropy value, the minimum entropy value so far, and the corresponding partition, respectively. If not provided, andhist is None
an iterator over the same values will be returned instead. density
tuple
(optional, default:None
) If provided, it should contain a tuple with values
(S_min, S_max, n_bins)
, which will be used to obtain the density of states via a histogram of sizen_bins
. This parameter is ignored unlesscallback is None
. verticesiterable of ints (optional, default:
None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 initial_partitioniterable of ints (optional, default:
None
) If provided, this will provide the initial partition for the iteration.
 max_iter
int
(optional, default:None
) If provided, this will limit the total number of iterations.
 entropy_args
 Returns
 statesiterator over (S, S_min, b_min)
If
callback
isNone
andhist
isNone
, the function will return an iterator over(S, S_min, b_min)
corresponding to the the current entropy value, the minimum entropy value so far, and the corresponding partition, respectively. Ss, countspair of
numpy.ndarray
If
callback is None
andhist is not None
, the function will return the values of each bin (Ss
) and the state count of each bin (counts
). b_min
VertexPropertyMap
If
callback is not None
orhist is not None
, the function will also return partition with smallest entropy.
Notes
This algorithm has an \(O(B^N)\) complexity, where \(B\) is the number of groups, and \(N\) is the number of vertices.
 get_Be()¶
Returns the effective number of blocks, defined as \(e^{H}\), with \(H=\sum_r\frac{n_r}{N}\ln \frac{n_r}{N}\), where \(n_r\) is the number of nodes in group r.
 get_bclabel(clabel=None)¶
Returns a
VertexPropertyMap
corresponding to constraint labels for the block graph.
 get_blocks()¶
Returns the property map which contains the block labels for each vertex.
 get_bpclabel()¶
Returns a
VertexPropertyMap
corresponding to partition constraint labels for the block graph.
 get_er()¶
Returns the vertex property map of the block graph which contains the number \(e_r\) of halfedges incident on block \(r\). If the graph is directed, a pair of property maps is returned, with the number of outedges \(e^+_r\) and inedges \(e^_r\), respectively.
 get_ers()¶
Returns the edge property map of the block graph which contains the \(e_{rs}\) matrix entries. For undirected graphs, the diagonal values (selfloops) contain \(e_{rr}/2\).
 get_matrix()¶
Returns the block matrix (as a sparse
csr_matrix
), which contains the number of edges between each block pair.Warning
This corresponds to the adjacency matrix of the block graph, which by convention includes twice the amount of edges in the diagonal entries if the graph is undirected.
Examples
>>> g = gt.collection.data["polbooks"] >>> state = gt.BlockState(g, B=5, deg_corr=True) >>> state.mcmc_sweep(niter=1000) (...) >>> m = state.get_matrix() >>> figure() <...> >>> matshow(m.todense()) <...> >>> savefig("bloc_mat.svg")
 get_move_prob(v, s, c=1.0, d=0.1, reverse=False)¶
Compute the logprobability of a move proposal for vertex
v
to blocks
according to sampling parametersc
andd
, as obtained withgraph_tool.inference.BlockState.sample_vertex_move()
. Ifreverse == True
, the reverse probability of moving the node back from blocks
to its current one is obtained.
 get_nr()¶
Returns the vertex property map of the block graph which contains the block sizes \(n_r\).
 get_rec_params()¶
Get model hyperparameters for edge covariates.
 get_state()¶
Alias to
get_blocks()
.
 gibbs_sweep(beta=1.0, niter=1, entropy_args={}, allow_new_group=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a rejectionfree Gibbs MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_new_group
bool
(optional, default:True
) Allow the number of groups to increase and decrease.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\times B)\) complexity, where \(B\) is the number of groups, and \(E\) is the number of edges.
 mcmc_sweep(bundled=False, **kwargs)[source]¶
Perform sweeps of a MetropolisHastings rejection sampling MCMC to sample network partitions. If
bundled == True
and the state is an overlapping one, the halfedges incident of the same node that belong to the same group are moved together. All remaining parameters are passed tograph_tool.inference.BlockState.mcmc_sweep()
.
 move_vertex(v, s)¶
Move vertex
v
to blocks
.This optionally accepts a list of vertices and blocks to move simultaneously.
 multicanonical_sweep(m_state, multiflip=False, **kwargs)¶
Perform
niter
sweeps of a nonMarkovian multicanonical sampling using the WangLandau algorithm. Parameters
 m_state
MulticanonicalState
MulticanonicalState
instance containing the current state of the WangLandau run. multiflip
bool
(optional, default:False
) If
True
,multiflip_mcmc_sweep()
will be used, otherwisemcmc_sweep()
. **kwargsKeyword parameter list
The remaining parameters will be passed to
multiflip_mcmc_sweep()
ormcmc_sweep()
.
 m_state
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 wangefficient2001
Fugao Wang, D. P. Landau, “An efficient, multiple range random walk algorithm to calculate the density of states”, Phys. Rev. Lett. 86, 2050 (2001), DOI: 10.1103/PhysRevLett.86.2050 [scihub, @tor], arXiv: condmat/0011174
 multiflip_mcmc_sweep(beta=1.0, c=0.5, psingle=None, psplit=1, pmerge=1, pmergesplit=1, pmovelabel=0, d=0.01, gibbs_sweeps=10, niter=1, entropy_args={}, accept_stats=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC with multiple simultaneous moves (i.e. merges and splits) to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. psplit
float
(optional, default:1
) Relative probability of proposing a group split.
 pmergesplit
float
(optional, default:1
) Relative probability of proposing a margesplit move.
 pmovelabel
float
(optional, default:0
) Relative probability of proposing a group label move.
 d
float
(optional, default:1
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 gibbs_sweeps
int
(optional, default:10
) Number of sweeps of Gibbs sampling to be performed (i.e. each node is attempted once per sweep) to refine a split proposal.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotomergesplit2020
Tiago P. Peixoto, “Mergesplit Markov chain Monte Carlo for community detection”, Phys. Rev. E 102, 012305 (2020), DOI: 10.1103/PhysRevE.102.012305 [scihub, @tor], arXiv: 2003.07070
 multilevel_mcmc_sweep(niter=1, beta=1.0, c=0.5, psingle=None, pmultilevel=1, d=0.01, r=0.9, random_bisect=True, merge_sweeps=10, mh_sweeps=10, init_r=0.99, init_beta=1.0, gibbs=False, B_min=1, B_max=18446744073709551615, b_min=None, b_max=None, M=None, cache_states=True, entropy_args={}, verbose=False, **kwargs)¶
Perform
niter
sweeps of a multilevel agglomerative acceptancerejection MCMC to sample network partitions, that uses a bisection search on the number of groups, together with group merges and singenode moves. Parameters
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. pmultilevel
float
(optional, default:1
) Relative probability of proposing a multilevel move.
 d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 r
float
(optional, default:0.9
) Group shrink ratio. The number of groups is reduced by this fraction at each merge sweep.
 random_bisect
bool
(optional, default:True
) If
True
, bisections are done at randomly chosen intervals. Otherwise a Fibonacci sequence is used. merge_sweeps
int
(optional, default:10
) Number of sweeps spent to find good merge proposals.
 mh_sweeps
int
(optional, default:10
) Number of singlenode MetropolisHastings sweeps between merge splits.
 init_r
double
(optional, default:0.99
) Stopping criterion for the intialization phase, after each node is put in their own group, to set the initial upper bound of the bisection search. A number of singlenode MetropolisHastings sweeps is done until the number of groups is shrunk by a factor that is larger than this parameter.
 init_beta
float
(optional, default:1.
) Inverse temperature to be used for the very first sweep of the initialization phase.
 gibbs
bool
(optional, default:False
) If
True
, the single node moves use (slower) Gibbs sampling, rather than MetropolisHastings. B_min
int
(optional, default:1
) Minimum number of groups to be considered in the search.
 b_min
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_min
. B_max
int
(optional, default:1
) Maximum number of groups to be considered in the search.
 b_max
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_max
. M
int
(optional, default:None
) Maximum number of groups to select for the multilevel move. If
None
is provided, then all groups are always elected. cache_states
bool
(optional, default:True
) If
True
, intermediary states will be cached during the bisection search. entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 niter
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\ln^2 N)\) complexity, where \(E\) is the number of edges and \(N\) is the number of nodes (independently of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 remove_vertex(v)¶
Remove vertex
v
from its current group.This optionally accepts a list of vertices to remove.
Warning
This will leave the state in an inconsistent state before the vertex is returned to some other group, or if the same vertex is removed twice.
 sample_graph(canonical=False, multigraph=True, self_loops=True, sample_params=False, max_ent=False, n_iter=1000)¶
Sample a new graph from the fitted model.
 Parameters
 canonical
bool
(optional, default:False
) If
canonical == True
, the graph will be sampled from the maximumlikelihood estimate of the canonical stochastic block model. Otherwise, it will be sampled from the microcanonical model. multigraph
bool
(optional, default:True
) If
True
, parallel edges will be allowed. selfloops
bool
(optional, default:True
) If
True
, selfloops will be allowed. sample_params
bool
(optional, default:True
) If
True
, andcanonical == True
andmax_ent == False
, the count parameters (edges between groups and node degrees) will be sampled from their posterior distribution conditioned on the actual state. Otherwise, their maximumlikelihood values will be used. max_ent
bool
(optional, default:False
) If
True
, maximumentropy model variants will be used. n_iter
int
(optional, default:1000
) Number of iterations used (only relevant if
canonical == False
andmax_ent == True
).
 canonical
 Returns
 g
Graph
Generated graph.
 g
Notes
This function is just a convenience wrapper to
generate_sbm()
. However, ifmax_ent==True
andcanonical == False
it wrapsrandom_rewire()
instead.Examples
>>> g = gt.collection.data["polbooks"] >>> state = gt.minimize_blockmodel_dl(g, multilevel_mcmc_args=dict(B_max=3)) >>> u = state.sample_graph(canonical=True, self_loops=False, multigraph=False) >>> ustate = gt.BlockState(u, b=state.b) >>> state.draw(pos=g.vp.pos, output="polbookssbm.svg") <...> >>> ustate.draw(pos=u.own_property(g.vp.pos), output="polbookssbmsampled.svg") <...>
Left: Political books network. Right: Sample from the degreecorrected SBM fitted to the original network.
 sample_vertex_move(v, c=1.0, d=0.1)¶
Sample block membership proposal of vertex
v
according to realvalued sampling parametersc
andd
: For \(c\to 0\) the blocks are sampled according to the local neighborhood and their connections; for \(c\to\infty\) the blocks are sampled randomly. With a probabilityd
, a new (empty) group is sampled.
 set_rec_params(params)¶
Update model hyperparameters for edge covariates.
 set_state(b)¶
Sets the internal partition of the state.
 virtual_vertex_move(v, s, **kwargs)¶
Computes the entropy difference if vertex
v
is moved to blocks
. The remaining parameters are the same as ingraph_tool.inference.BlockState.entropy()
.
 draw(**kwargs)[source]¶
Convenience function to draw the current state. All keyword arguments are passed to
graph_tool.inference.BlockState.draw()
orgraph_tool.inference.OverlapBlockState.draw()
, as appropriate.
 class graph_tool.inference.NestedBlockState(g, bs=None, base_type=<class 'graph_tool.inference.blockmodel.BlockState'>, state_args={}, hstate_args={}, hentropy_args={}, **kwargs)[source]¶
Bases:
object
The nested stochastic block model state of a given graph.
 Parameters
 g
Graph
Graph to be modeled.
 bs
list
ofVertexPropertyMap
ornumpy.ndarray
(optional, default:None
) Hierarchical node partition. If not provided it will correspond to a singlegroup hierarchy of length \(\lceil\log_2(N)\rceil\).
 base_type
type
(optional, default:BlockState
) State type for lowermost level (e.g.
BlockState
,OverlapBlockState
orLayeredBlockState
) hstate_args
dict
(optional, default: {}) Keyword arguments to be passed to the constructor of the higherlevel states.
 hentropy_args
dict
(optional, default: {}) Keyword arguments to be passed to the
entropy()
method of the higherlevel states. state_args
dict
(optional, default:{}
) Keyword arguments to be passed to base type constructor.
 **kwargskeyword arguments
Keyword arguments to be passed to base type constructor. The
state_args
parameter overrides this.
 g
 copy(**kwargs)[source]¶
Copies the block state. The parameters override the state properties, and have the same meaning as in the constructor.
 get_bs()[source]¶
Get hierarchy levels as a list of
numpy.ndarray
objects with the group memberships at each level.
 get_levels()[source]¶
Get hierarchy levels as a list of
BlockState
instances.
 entropy(**kwargs)[source]¶
Compute the entropy of whole hierarchy.
The keyword arguments are passed to the
entropy()
method of the underlying state objects (e.g.graph_tool.inference.BlockState.entropy
,graph_tool.inference.OverlapBlockState.entropy
, orgraph_tool.inference.LayeredBlockState.entropy
).
 remove_vertex(v)[source]¶
Remove vertex
v
from its current group.This optionally accepts a list of vertices to remove.
Warning
This will leave the state in an inconsistent state before the vertex is returned to some other group, or if the same vertex is removed twice.
 add_vertex(v, r)[source]¶
Add vertex
v
to blockr
.This optionally accepts a list of vertices and blocks to add.
Warning
This can leave the state in an inconsistent state if a vertex is added twice to the same group.
 get_edges_prob(missing, spurious=[], entropy_args={})[source]¶
Compute the joint logprobability of the missing and spurious edges given by
missing
andspurious
(a list of(source, target)
tuples, orEdge()
instances), together with the observed edges.More precisely, the loglikelihood returned is
\[\ln \frac{P(\boldsymbol G + \delta \boldsymbol G  \boldsymbol b)}{P(\boldsymbol G \boldsymbol b)}\]where \(\boldsymbol G + \delta \boldsymbol G\) is the modified graph (with missing edges added and spurious edges deleted).
The values in
entropy_args
are passed tograph_tool.inference.BlockState.entropy()
to calculate the logprobability.
 get_bstack()[source]¶
Return the nested levels as individual graphs.
This returns a list of
Graph
instances representing the inferred hierarchy at each level. Each graph has two internal vertex and edge property maps named “count” which correspond to the vertex and edge counts at the lower level, respectively. Additionally, an internal vertex property map named “b” specifies the block partition.
 project_level(l)[source]¶
Project the partition at level
l
onto the lowest level, and return the corresponding state.
 mcmc_sweep(**kwargs)[source]¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC to sample hierarchical network partitions.The arguments accepted are the same as in
graph_tool.inference.BlockState.mcmc_sweep()
.If the parameter
c
is a scalar, the values used at each level arec * 2 ** l
forl
in the range[0, L1]
. Optionally, a list of values may be passed instead, which specifies the value ofc[l]
to be used at each level.Warning
This function performs
niter
sweeps at each hierarchical level once. This means that in order for the chain to equilibrate, we need to call this function several times, i.e. it is not enough to call it once with a large value ofniter
.
 multiflip_mcmc_sweep(**kwargs)[source]¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC with multiple moves to sample hierarchical network partitions.The arguments accepted are the same as in
graph_tool.inference.BlockState.multiflip_mcmc_sweep()
.If the parameter
c
is a scalar, the values used at each level arec * 2 ** l
forl
in the range[0, L1]
. Optionally, a list of values may be passed instead, which specifies the value ofc[l]
to be used at each level.Warning
This function performs
niter
sweeps at each hierarchical level once. This means that in order for the chain to equilibrate, we need to call this function several times, i.e. it is not enough to call it once with a large value ofniter
.
 multilevel_mcmc_sweep(**kwargs)[source]¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC with multilevel moves to sample hierarchical network partitions.The arguments accepted are the same as in
graph_tool.inference.BlockState.multilevel_mcmc_sweep()
.If the parameter
c
is a scalar, the values used at each level arec * 2 ** l
forl
in the range[0, L1]
. Optionally, a list of values may be passed instead, which specifies the value ofc[l]
to be used at each level.Warning
This function performs
niter
sweeps at each hierarchical level once. This means that in order for the chain to equilibrate, we need to call this function several times, i.e. it is not enough to call it once with a large value ofniter
.
 gibbs_sweep(**kwargs)[source]¶
Perform
niter
sweeps of a rejectionfree Gibbs sampling MCMC to sample network partitions.The arguments accepted are the same as in
graph_tool.inference.BlockState.gibbs_sweep()
.Warning
This function performs
niter
sweeps at each hierarchical level once. This means that in order for the chain to equilibrate, we need to call this function several times, i.e. it is not enough to call it once with a large value ofniter
.
 multicanonical_sweep(m_state, **kwargs)[source]¶
Perform
niter
sweeps of a nonMarkovian multicanonical sampling using the WangLandau algorithm.The arguments accepted are the same as in
graph_tool.inference.BlockState.multicanonical_sweep()
.
 collect_partition_histogram(h=None, update=1)[source]¶
Collect a histogram of partitions.
This should be called multiple times, e.g. after repeated runs of the
graph_tool.inference.NestedBlockState.mcmc_sweep()
function. Parameters
 h
PartitionHist
(optional, default:None
) Partition histogram. If not provided, an empty histogram will be created.
 updatefloat (optional, default:
1
) Each call increases the current count by the amount given by this parameter.
 h
 Returns
 h
PartitionHist
(optional, default:None
) Updated Partition histogram.
 h
 draw(**kwargs)[source]¶
Convenience wrapper to
draw_hierarchy()
that draws the hierarchical state.
 class graph_tool.inference.PPBlockState(g, b=None)[source]¶
Bases:
graph_tool.inference.base_states.MCMCState
,graph_tool.inference.base_states.MultiflipMCMCState
,graph_tool.inference.base_states.MultilevelMCMCState
,graph_tool.inference.base_states.GibbsMCMCState
,graph_tool.inference.base_states.DrawBlockState
Obtain the partition of a network according to the Bayesian planted partition model.
 Parameters
 g
Graph
Graph to be modelled.
 b
PropertyMap
(optional, default:None
) Initial partition. If not supplied, a partition into a single group will be used.
 g
References
 lizhistatistical2020
Lizhi Zhang, Tiago P. Peixoto, “Statistical inference of assortative community structures”, Phys. Rev. Research 2 043271 (2020), DOI: 10.1103/PhysRevResearch.2.043271 [scihub, @tor], arXiv: 2006.14493
 copy(g=None, b=None)[source]¶
Copies the state. The parameters override the state properties, and have the same meaning as in the constructor.
 get_state()[source]¶
Alias to
get_blocks()
.
 get_Be()[source]¶
Returns the effective number of blocks, defined as \(e^{H}\), with \(H=\sum_r\frac{n_r}{N}\ln \frac{n_r}{N}\), where \(n_r\) is the number of nodes in group r.
 virtual_vertex_move(v, s, **kwargs)[source]¶
Computes the entropy difference if vertex
v
is moved to blocks
. The remaining parameters are the same as inentropy()
.
 entropy(uniform=False, degree_dl_kind='distributed', **kwargs)[source]¶
Return the model entropy (negative loglikelihood).
 Parameters
 uniform
bool
(optional, default:False
) If
True
, the uniform planted partition model is used, otherwise a nonuniform version is used. degree_dl_kind
str
(optional, default:"distributed"
) This specifies the prior used for the degree sequence. It must be one of:
"uniform"
or"distributed"
(default).
 uniform
Notes
The “entropy” of the state is the negative loglikelihood of the microcanonical SBM, that includes the generated graph \(\boldsymbol{A}\) and the model parameters \(e_{\text{in}}\), \(e_{\text{out}}\), \(\boldsymbol{k}\) and \(\boldsymbol{b}\),
\[\begin{split}\Sigma &=  \ln P(\boldsymbol{A},e_{\text{in}},e_{\text{out}},\boldsymbol{k},\boldsymbol{b}) \\ &=  \ln P(\boldsymbol{A}e_{\text{in}},e_{\text{out}},\boldsymbol{k},\boldsymbol{b})  \ln P(e_{\text{in}},e_{\text{out}},\boldsymbol{k},\boldsymbol{b}).\end{split}\]This value is also called the description length of the data, and it corresponds to the amount of information required to describe it (in nats).
For the uniform version of the model, the likelihood is
\[P(\boldsymbol{A}\boldsymbol{k},\boldsymbol{b}) = \frac{e_{\text{in}}!e_{\text{out}}!} {\left(\frac{B}{2}\right)^{e_{\text{in}}}{B\choose 2}^{e_{\text{out}}}(E+1)^{1\delta_{B,1}}\prod_re_r!}\times \frac{\prod_ik_i!}{\prod_{i<j}A_{ij}!\prod_i A_{ii}!!}.\]where \(e_{\text{in}}\) and \(e_{\text{out}}\) are the number of edges inside and outside communities, respectively, and \(e_r\) is the sum of degrees in group \(r\).
For the nonuniform model we have instead:
\[P(\boldsymbol{A}\boldsymbol{k},\boldsymbol{b}) = \frac{e_{\text{out}}!\prod_re_{rr}!!} {{B\choose 2}^{e_{\text{out}}}(E+1)^{1\delta_{B,1}}\prod_re_r!}\times{B + e_{\text{in}}  1 \choose e_{\text{in}}}^{1}\times \frac{\prod_ik_i!}{\prod_{i<j}A_{ij}!\prod_i A_{ii}!!}.\]Here there are two options for the prior on the degrees:
degree_dl_kind == "uniform"
\[P(\boldsymbol{k}\boldsymbol{e},\boldsymbol{b}) = \prod_r\left(\!\!{n_r\choose e_r}\!\!\right)^{1}.\]This corresponds to a noninformative prior, where the degrees are sampled from a uniform distribution.
degree_dl_kind == "distributed"
(default)\[P(\boldsymbol{k}\boldsymbol{e},\boldsymbol{b}) = \prod_r\frac{\prod_k\eta_k^r!}{n_r!} \prod_r q(e_r, n_r)^{1}\]with \(\eta_k^r\) being the number of nodes with degree \(k\) in group \(r\), and \(q(n,m)\) being the number of partitions of integer \(n\) into at most \(m\) parts.
This corresponds to a prior for the degree sequence conditioned on the degree frequencies, which are themselves sampled from a uniform hyperprior. This option should be preferred in most cases.
For the partition prior \(P(\boldsymbol{b})\) please refer to
entropy()
.References
 lizhistatistical2020
Lizhi Zhang, Tiago P. Peixoto, “Statistical inference of assortative community structures”, Phys. Rev. Research 2 043271 (2020), DOI: 10.1103/PhysRevResearch.2.043271 [scihub, @tor], arXiv: 2006.14493
 draw(**kwargs)¶
Convenience wrapper to
graph_draw()
that draws the state of the graph as colors on the vertices and edges.
 gibbs_sweep(beta=1.0, niter=1, entropy_args={}, allow_new_group=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a rejectionfree Gibbs MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_new_group
bool
(optional, default:True
) Allow the number of groups to increase and decrease.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\times B)\) complexity, where \(B\) is the number of groups, and \(E\) is the number of edges.
 mcmc_sweep(beta=1.0, c=0.5, d=0.01, niter=1, entropy_args={}, allow_vacate=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given move.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_vacate
bool
(optional, default:True
) Allow groups to be vacated.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 multiflip_mcmc_sweep(beta=1.0, c=0.5, psingle=None, psplit=1, pmerge=1, pmergesplit=1, pmovelabel=0, d=0.01, gibbs_sweeps=10, niter=1, entropy_args={}, accept_stats=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC with multiple simultaneous moves (i.e. merges and splits) to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. psplit
float
(optional, default:1
) Relative probability of proposing a group split.
 pmergesplit
float
(optional, default:1
) Relative probability of proposing a margesplit move.
 pmovelabel
float
(optional, default:0
) Relative probability of proposing a group label move.
 d
float
(optional, default:1
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 gibbs_sweeps
int
(optional, default:10
) Number of sweeps of Gibbs sampling to be performed (i.e. each node is attempted once per sweep) to refine a split proposal.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotomergesplit2020
Tiago P. Peixoto, “Mergesplit Markov chain Monte Carlo for community detection”, Phys. Rev. E 102, 012305 (2020), DOI: 10.1103/PhysRevE.102.012305 [scihub, @tor], arXiv: 2003.07070
 multilevel_mcmc_sweep(niter=1, beta=1.0, c=0.5, psingle=None, pmultilevel=1, d=0.01, r=0.9, random_bisect=True, merge_sweeps=10, mh_sweeps=10, init_r=0.99, init_beta=1.0, gibbs=False, B_min=1, B_max=18446744073709551615, b_min=None, b_max=None, M=None, cache_states=True, entropy_args={}, verbose=False, **kwargs)¶
Perform
niter
sweeps of a multilevel agglomerative acceptancerejection MCMC to sample network partitions, that uses a bisection search on the number of groups, together with group merges and singenode moves. Parameters
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. pmultilevel
float
(optional, default:1
) Relative probability of proposing a multilevel move.
 d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 r
float
(optional, default:0.9
) Group shrink ratio. The number of groups is reduced by this fraction at each merge sweep.
 random_bisect
bool
(optional, default:True
) If
True
, bisections are done at randomly chosen intervals. Otherwise a Fibonacci sequence is used. merge_sweeps
int
(optional, default:10
) Number of sweeps spent to find good merge proposals.
 mh_sweeps
int
(optional, default:10
) Number of singlenode MetropolisHastings sweeps between merge splits.
 init_r
double
(optional, default:0.99
) Stopping criterion for the intialization phase, after each node is put in their own group, to set the initial upper bound of the bisection search. A number of singlenode MetropolisHastings sweeps is done until the number of groups is shrunk by a factor that is larger than this parameter.
 init_beta
float
(optional, default:1.
) Inverse temperature to be used for the very first sweep of the initialization phase.
 gibbs
bool
(optional, default:False
) If
True
, the single node moves use (slower) Gibbs sampling, rather than MetropolisHastings. B_min
int
(optional, default:1
) Minimum number of groups to be considered in the search.
 b_min
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_min
. B_max
int
(optional, default:1
) Maximum number of groups to be considered in the search.
 b_max
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_max
. M
int
(optional, default:None
) Maximum number of groups to select for the multilevel move. If
None
is provided, then all groups are always elected. cache_states
bool
(optional, default:True
) If
True
, intermediary states will be cached during the bisection search. entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 niter
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\ln^2 N)\) complexity, where \(E\) is the number of edges and \(N\) is the number of nodes (independently of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 class graph_tool.inference.RankedBlockState(g, b=None, u=None, **kwargs)[source]¶
Bases:
graph_tool.inference.base_states.MCMCState
,graph_tool.inference.base_states.MultiflipMCMCState
,graph_tool.inference.base_states.MultilevelMCMCState
,graph_tool.inference.base_states.GibbsMCMCState
,graph_tool.inference.base_states.DrawBlockState
Obtain the ordered partition of a network according to the ranked stochastic block model.
 Parameters
 g
Graph
Graph to be modelled.
 b
PropertyMap
(optional, default:None
) Initial partition. If not supplied, a partition into a single group will be used.
 u
PropertyMap
or iterable (optional, default:None
) Ordering of the group labels. It should contain a map from each group label to the unit interval \([0,1]\), inidicating how the groups should be ordered. If not supplied, the numeric values of the group lalbels will be used to initialize the ordering.
 g
References
 peixotoordered2022
Tiago P. Peixoto, “Ordered community detection in directed networks”, arXiv: 2203.16460
 copy(**kwargs)[source]¶
Copies the state. The parameters override the state properties, and have the same meaning as in the constructor.
 get_block_state(b=None, vweight=None, deg_corr=False, **kwargs)[source]¶
Returns a
ReciprocalBlockState
corresponding to the block graph (i.e. the blocks of the current state become the nodes).
 get_vertex_order()[source]¶
Returns a vertex
PropertyMap
with the rank order for every vertex.
 get_vertex_position()[source]¶
Returns a vertex
PropertyMap
with vertex positions in the unit interval \([0,1]\).
 collect_vertex_marginals(p=None, b=None, update=1)[source]¶
Collect the vertex marginal histogram, which counts the number of times a node was assigned to a given block.
 Parameters
 p
VertexPropertyMap
(optional, default:None
) Vertex property map with vectortype values, storing the previous block membership counts. If not provided, an empty histogram will be created.
 b
VertexPropertyMap
(optional, default:None
) Vertex property map with group partition. If not provided, the state’s partition will be used.
 updateint (optional, default:
1
) Each call increases the current count by the amount given by this parameter.
 p
 Returns
 p
VertexPropertyMap
Vertex property map with vectortype values, storing the accumulated block membership counts.
 p
 get_edge_dir()[source]¶
Return an edge
PropertyMap
containing the edge direction:1
(downstream),0
(lateral),+1
(upstream).
 get_Be()[source]¶
Returns the effective number of blocks, defined as \(e^{H}\), with \(H=\sum_r\frac{n_r}{N}\ln \frac{n_r}{N}\), where \(n_r\) is the number of nodes in group r.
 virtual_vertex_move(v, s, **kwargs)[source]¶
Computes the entropy difference if vertex
v
is moved to blocks
. The remaining parameters are the same as inentropy()
.
 entropy(adjacency=True, dl=True, partition_dl=True, degree_dl=True, degree_dl_kind='distributed', edges_dl=True, dense=False, multigraph=True, deg_entropy=True, recs=True, recs_dl=True, beta_dl=1.0, Bfield=True, exact=True, **kwargs)[source]¶
Return the model entropy (negative loglikelihood). See
BlockState.entropy()
for documentation.
 sample_graph(**kwargs)[source]¶
Sample a new graph from the fitted model. See
BlockState.sample_graph()
for documentation.
 draw(**kwargs)[source]¶
Convenience wrapper to
graph_draw()
that draws the state of the graph as colors on the vertices and edges.
 gibbs_sweep(beta=1.0, niter=1, entropy_args={}, allow_new_group=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a rejectionfree Gibbs MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_new_group
bool
(optional, default:True
) Allow the number of groups to increase and decrease.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\times B)\) complexity, where \(B\) is the number of groups, and \(E\) is the number of edges.
 mcmc_sweep(beta=1.0, c=0.5, d=0.01, niter=1, entropy_args={}, allow_vacate=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given move.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_vacate
bool
(optional, default:True
) Allow groups to be vacated.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 multiflip_mcmc_sweep(beta=1.0, c=0.5, psingle=None, psplit=1, pmerge=1, pmergesplit=1, pmovelabel=0, d=0.01, gibbs_sweeps=10, niter=1, entropy_args={}, accept_stats=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC with multiple simultaneous moves (i.e. merges and splits) to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. psplit
float
(optional, default:1
) Relative probability of proposing a group split.
 pmergesplit
float
(optional, default:1
) Relative probability of proposing a margesplit move.
 pmovelabel
float
(optional, default:0
) Relative probability of proposing a group label move.
 d
float
(optional, default:1
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 gibbs_sweeps
int
(optional, default:10
) Number of sweeps of Gibbs sampling to be performed (i.e. each node is attempted once per sweep) to refine a split proposal.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotomergesplit2020
Tiago P. Peixoto, “Mergesplit Markov chain Monte Carlo for community detection”, Phys. Rev. E 102, 012305 (2020), DOI: 10.1103/PhysRevE.102.012305 [scihub, @tor], arXiv: 2003.07070
 multilevel_mcmc_sweep(niter=1, beta=1.0, c=0.5, psingle=None, pmultilevel=1, d=0.01, r=0.9, random_bisect=True, merge_sweeps=10, mh_sweeps=10, init_r=0.99, init_beta=1.0, gibbs=False, B_min=1, B_max=18446744073709551615, b_min=None, b_max=None, M=None, cache_states=True, entropy_args={}, verbose=False, **kwargs)¶
Perform
niter
sweeps of a multilevel agglomerative acceptancerejection MCMC to sample network partitions, that uses a bisection search on the number of groups, together with group merges and singenode moves. Parameters
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. pmultilevel
float
(optional, default:1
) Relative probability of proposing a multilevel move.
 d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 r
float
(optional, default:0.9
) Group shrink ratio. The number of groups is reduced by this fraction at each merge sweep.
 random_bisect
bool
(optional, default:True
) If
True
, bisections are done at randomly chosen intervals. Otherwise a Fibonacci sequence is used. merge_sweeps
int
(optional, default:10
) Number of sweeps spent to find good merge proposals.
 mh_sweeps
int
(optional, default:10
) Number of singlenode MetropolisHastings sweeps between merge splits.
 init_r
double
(optional, default:0.99
) Stopping criterion for the intialization phase, after each node is put in their own group, to set the initial upper bound of the bisection search. A number of singlenode MetropolisHastings sweeps is done until the number of groups is shrunk by a factor that is larger than this parameter.
 init_beta
float
(optional, default:1.
) Inverse temperature to be used for the very first sweep of the initialization phase.
 gibbs
bool
(optional, default:False
) If
True
, the single node moves use (slower) Gibbs sampling, rather than MetropolisHastings. B_min
int
(optional, default:1
) Minimum number of groups to be considered in the search.
 b_min
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_min
. B_max
int
(optional, default:1
) Maximum number of groups to be considered in the search.
 b_max
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_max
. M
int
(optional, default:None
) Maximum number of groups to select for the multilevel move. If
None
is provided, then all groups are always elected. cache_states
bool
(optional, default:True
) If
True
, intermediary states will be cached during the bisection search. entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 niter
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\ln^2 N)\) complexity, where \(E\) is the number of edges and \(N\) is the number of nodes (independently of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 class graph_tool.inference.PartitionCentroidState(bs, b=None, RMI=False)[source]¶
Bases:
graph_tool.inference.base_states.MCMCState
,graph_tool.inference.base_states.MultiflipMCMCState
,graph_tool.inference.base_states.MultilevelMCMCState
Obtain the center of a set of partitions, according to the variation of information metric or reduced mutual information.
 Parameters
 bsiterable of iterable of
int
List of partitions.
 b
list
ornumpy.ndarray
(optional, default:None
) Initial partition. If not supplied, a partition into a single group will be used.
 RMI
bool
(optional, default:False
) If
True
, the reduced mutual information will be used, otherwise the variation of information metric will be used instead.
 bsiterable of iterable of
 copy(bs=None, b=None, RMI=None)[source]¶
Copies the state. The parameters override the state properties, and have the same meaning as in the constructor.
 get_Be()[source]¶
Returns the effective number of blocks, defined as \(e^{H}\), with \(H=\sum_r\frac{n_r}{N}\ln \frac{n_r}{N}\), where \(n_r\) is the number of nodes in group r.
 mcmc_sweep(beta=1.0, c=0.5, d=0.01, niter=1, entropy_args={}, allow_vacate=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given move.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_vacate
bool
(optional, default:True
) Allow groups to be vacated.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 multiflip_mcmc_sweep(beta=1.0, c=0.5, psingle=None, psplit=1, pmerge=1, pmergesplit=1, pmovelabel=0, d=0.01, gibbs_sweeps=10, niter=1, entropy_args={}, accept_stats=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC with multiple simultaneous moves (i.e. merges and splits) to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. psplit
float
(optional, default:1
) Relative probability of proposing a group split.
 pmergesplit
float
(optional, default:1
) Relative probability of proposing a margesplit move.
 pmovelabel
float
(optional, default:0
) Relative probability of proposing a group label move.
 d
float
(optional, default:1
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 gibbs_sweeps
int
(optional, default:10
) Number of sweeps of Gibbs sampling to be performed (i.e. each node is attempted once per sweep) to refine a split proposal.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotomergesplit2020
Tiago P. Peixoto, “Mergesplit Markov chain Monte Carlo for community detection”, Phys. Rev. E 102, 012305 (2020), DOI: 10.1103/PhysRevE.102.012305 [scihub, @tor], arXiv: 2003.07070
 multilevel_mcmc_sweep(niter=1, beta=1.0, c=0.5, psingle=None, pmultilevel=1, d=0.01, r=0.9, random_bisect=True, merge_sweeps=10, mh_sweeps=10, init_r=0.99, init_beta=1.0, gibbs=False, B_min=1, B_max=18446744073709551615, b_min=None, b_max=None, M=None, cache_states=True, entropy_args={}, verbose=False, **kwargs)¶
Perform
niter
sweeps of a multilevel agglomerative acceptancerejection MCMC to sample network partitions, that uses a bisection search on the number of groups, together with group merges and singenode moves. Parameters
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. pmultilevel
float
(optional, default:1
) Relative probability of proposing a multilevel move.
 d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 r
float
(optional, default:0.9
) Group shrink ratio. The number of groups is reduced by this fraction at each merge sweep.
 random_bisect
bool
(optional, default:True
) If
True
, bisections are done at randomly chosen intervals. Otherwise a Fibonacci sequence is used. merge_sweeps
int
(optional, default:10
) Number of sweeps spent to find good merge proposals.
 mh_sweeps
int
(optional, default:10
) Number of singlenode MetropolisHastings sweeps between merge splits.
 init_r
double
(optional, default:0.99
) Stopping criterion for the intialization phase, after each node is put in their own group, to set the initial upper bound of the bisection search. A number of singlenode MetropolisHastings sweeps is done until the number of groups is shrunk by a factor that is larger than this parameter.
 init_beta
float
(optional, default:1.
) Inverse temperature to be used for the very first sweep of the initialization phase.
 gibbs
bool
(optional, default:False
) If
True
, the single node moves use (slower) Gibbs sampling, rather than MetropolisHastings. B_min
int
(optional, default:1
) Minimum number of groups to be considered in the search.
 b_min
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_min
. B_max
int
(optional, default:1
) Maximum number of groups to be considered in the search.
 b_max
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_max
. M
int
(optional, default:None
) Maximum number of groups to select for the multilevel move. If
None
is provided, then all groups are always elected. cache_states
bool
(optional, default:True
) If
True
, intermediary states will be cached during the bisection search. entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 niter
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\ln^2 N)\) complexity, where \(E\) is the number of edges and \(N\) is the number of nodes (independently of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 class graph_tool.inference.PartitionModeState(bs, relabel=True, nested=False, converge=False, **kwargs)[source]¶
Bases:
object
The random label model state for a set of labelled partitions, which attempts to align them with a common group labelling.
 Parameters
 bslist of iterables
List of partitions to be aligned. If
nested=True
, these should be hierarchical partitions, composed each as a list of partitions. relabel
bool
(optional, default:True
) If
True
, an initial alignment of the partitions will be attempted during instantiation, otherwise they will be incorporated as they are. nested
bool
(optional, default:False
) If
True
, the partitions will be assumed to be hierarchical. converge
bool
(optional, default:False
) If
True
, the label alignment will be iterated until convergence upon initialization (otherwisereplace_partitions()
needs to be called repeatedly).
References
 peixotorevealing2021
Tiago P. Peixoto, “Revealing consensus and dissensus between network partitions”, Phys. Rev. X 11 021003 (2021) DOI: 10.1103/PhysRevX.11.021003 [scihub, @tor], arXiv: 2005.13977
 copy(bs=None)[source]¶
Copies the state. The parameters override the state properties, and have the same meaning as in the constructor.
 add_partition(b, relabel=True)[source]¶
Adds partition
b
to the ensemble, after relabelling it ifrelabel=True
, and returns its index in the population.
 virtual_add_partition(b, relabel=True)[source]¶
Computes the entropy difference (negative log probability) if partition
b
were inserted the ensemble, after relabelling it ifrelabel=True
.
 virtual_remove_partition(b, relabel=True)[source]¶
Computes the entropy difference (negative log probability) if partition
b
were removed from the ensemble, after relabelling it ifrelabel=True
.
 replace_partitions()[source]¶
Removes and readds every partition, after relabelling, and returns the entropy difference (negative log probability).
 relabel_partition(b)[source]¶
Returns a relabelled copy of partition
b
, according to its alignment with the ensemble.
 align_mode(mode)[source]¶
Relabel entire ensemble to align with another ensemble given by
mode
, which should be an instance ofPartitionModeState
.
 posterior_entropy(MLE=True)[source]¶
Return the entropy of the random label model, using maximum likelihood estimates for the marginal node probabilities if
`MLE=True`
, otherwise using posterior mean estimates.
 posterior_cdev(MLE=True)[source]¶
Return the uncertainty of the mode in the range \([0,1]\), using maximum likelihood estimates for the marginal node probabilities if
`MLE=True`
, otherwise using posterior mean estimates.
 posterior_lprob(b, MLE=True)[source]¶
Return the logprobability of partition
b
, using maximum likelihood estimates for the marginal node probabilities if`MLE=True`
, otherwise using posterior mean estimates.
 get_coupled_state()[source]¶
Return the instance of
PartitionModeState
representing the model at the upper hierarchical level.
 get_marginal(g)[source]¶
Return a
VertexPropertyMap
forGraph
g
, withvector<int>
values containing the marginal group membership counts for each node.
 get_max(g)[source]¶
Return a
VertexPropertyMap
forGraph
g
, withint
values containing the maximum marginal group membership for each node.
 get_max_nested()[source]¶
Return a hierarchical partition as a list of
numpy.ndarray
objects, containing the maximum marginal group membership for each node in every level.
 class graph_tool.inference.ModeClusterState(bs, b=None, B=1, nested=False, relabel=True)[source]¶
Bases:
graph_tool.inference.base_states.MCMCState
,graph_tool.inference.base_states.MultiflipMCMCState
,graph_tool.inference.base_states.MultilevelMCMCState
The mixed random label model state for a set of labelled partitions, which attempts to align them inside clusters with a common group labelling.
 Parameters
 bslist of iterables
List of partitions to be aligned. If
nested=True
, these should be hierarchical partitions, composed each as a list of partitions. biterable (optional, default:
None
) Initial cluster membership for every partition. If
None
a random division intoB
groups will be used. B
int
(optional, default:1
) Number of groups for initial division.
 relabel
bool
(optional, default:True
) If
True
, an initial alignment of the partitions will be attempted during instantiation, otherwise they will be incorporated as they are. nested
bool
(optional, default:False
) If
True
, the partitions will be assumed to be hierarchical.
References
 peixotorevealing2021
Tiago P. Peixoto, “Revealing consensus and dissensus between network partitions”, Phys. Rev. X 11 021003 (2021) DOI: 10.1103/PhysRevX.11.021003 [scihub, @tor], arXiv: 2005.13977
 copy(bs=None, b=None)[source]¶
Copies the state. The parameters override the state properties, and have the same meaning as in the constructor.
 get_mode(r)[source]¶
Return the mode in cluster
r
as an instance ofPartitionModeState
.
 get_modes(sort=True)[source]¶
Return the list of nonempty modes, as instances of
PartitionModeState
. If sorted == True, the modes are retured in decreasing order with respect to their size.
 get_Be()[source]¶
Returns the effective number of clusters, defined as \(e^{H}\), with \(H=\sum_r\frac{n_r}{N}\ln \frac{n_r}{N}\), where \(n_r\) is the number of partitions in cluster \(r\).
 virtual_add_partition(b, r, relabel=True)[source]¶
Computes the entropy difference (negative log probability) if partition
b
were inserted in clusterr
, after relabelling it ifrelabel=True
.
 add_partition(b, r, relabel=True)[source]¶
Add partition
b
in clusterr
, after relabelling it ifrelabel=True
.
 classify_partition(b, relabel=True, new_group=True, sample=False)[source]¶
Returns the cluster
r
to which partitionb
would belong, after relabelling it ifrelabel=True
, according to the most probable assignment, or randomly sampled according to the relative probabilities ifsample==True
. Ifnew_group==True
, a new previously unoccupied group is also considered for the classification.
 relabel(epsilon=1e06, maxiter=100)[source]¶
Attempt to align group labels between clusters via a greedy algorithm. The algorithm stops after
maxiter
iterations or when the entropy improvement lies belowepsilon
.
 posterior_entropy(MLE=True)[source]¶
Return the entropy of the random label model, using maximum likelihood estimates for the marginal node probabilities if
`MLE=True`
, otherwise using posterior mean estimates.
 posterior_lprob(r, b, MLE=True)[source]¶
Return the logprobability of partition
b
belonging to moder
, using maximum likelihood estimates for the marginal node probabilities if`MLE=True`
, otherwise using posterior mean estimates.
 replace_partitions()[source]¶
For every cluster, removes and readds every partition, after relabelling, and returns the entropy difference (negative log probability).
 sample_partition(MLE=True)[source]¶
Sampled a cluster label and partition from the inferred model, using maximum likelihood estimates for the marginal node probabilities if
`MLE=True`
, otherwise using posterior mean estimates.
 sample_nested_partition(MLE=True, fix_empty=True)[source]¶
Sampled a cluster label and nested partition from the inferred model, using maximum likelihood estimates for the marginal node probabilities if
`MLE=True`
, otherwise using posterior mean estimates.
 mcmc_sweep(beta=1.0, c=0.5, d=0.01, niter=1, entropy_args={}, allow_vacate=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given move.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_vacate
bool
(optional, default:True
) Allow groups to be vacated.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 multiflip_mcmc_sweep(beta=1.0, c=0.5, psingle=None, psplit=1, pmerge=1, pmergesplit=1, pmovelabel=0, d=0.01, gibbs_sweeps=10, niter=1, entropy_args={}, accept_stats=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC with multiple simultaneous moves (i.e. merges and splits) to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. psplit
float
(optional, default:1
) Relative probability of proposing a group split.
 pmergesplit
float
(optional, default:1
) Relative probability of proposing a margesplit move.
 pmovelabel
float
(optional, default:0
) Relative probability of proposing a group label move.
 d
float
(optional, default:1
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 gibbs_sweeps
int
(optional, default:10
) Number of sweeps of Gibbs sampling to be performed (i.e. each node is attempted once per sweep) to refine a split proposal.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotomergesplit2020
Tiago P. Peixoto, “Mergesplit Markov chain Monte Carlo for community detection”, Phys. Rev. E 102, 012305 (2020), DOI: 10.1103/PhysRevE.102.012305 [scihub, @tor], arXiv: 2003.07070
 multilevel_mcmc_sweep(niter=1, beta=1.0, c=0.5, psingle=None, pmultilevel=1, d=0.01, r=0.9, random_bisect=True, merge_sweeps=10, mh_sweeps=10, init_r=0.99, init_beta=1.0, gibbs=False, B_min=1, B_max=18446744073709551615, b_min=None, b_max=None, M=None, cache_states=True, entropy_args={}, verbose=False, **kwargs)¶
Perform
niter
sweeps of a multilevel agglomerative acceptancerejection MCMC to sample network partitions, that uses a bisection search on the number of groups, together with group merges and singenode moves. Parameters
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. pmultilevel
float
(optional, default:1
) Relative probability of proposing a multilevel move.
 d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 r
float
(optional, default:0.9
) Group shrink ratio. The number of groups is reduced by this fraction at each merge sweep.
 random_bisect
bool
(optional, default:True
) If
True
, bisections are done at randomly chosen intervals. Otherwise a Fibonacci sequence is used. merge_sweeps
int
(optional, default:10
) Number of sweeps spent to find good merge proposals.
 mh_sweeps
int
(optional, default:10
) Number of singlenode MetropolisHastings sweeps between merge splits.
 init_r
double
(optional, default:0.99
) Stopping criterion for the intialization phase, after each node is put in their own group, to set the initial upper bound of the bisection search. A number of singlenode MetropolisHastings sweeps is done until the number of groups is shrunk by a factor that is larger than this parameter.
 init_beta
float
(optional, default:1.
) Inverse temperature to be used for the very first sweep of the initialization phase.
 gibbs
bool
(optional, default:False
) If
True
, the single node moves use (slower) Gibbs sampling, rather than MetropolisHastings. B_min
int
(optional, default:1
) Minimum number of groups to be considered in the search.
 b_min
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_min
. B_max
int
(optional, default:1
) Maximum number of groups to be considered in the search.
 b_max
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_max
. M
int
(optional, default:None
) Maximum number of groups to select for the multilevel move. If
None
is provided, then all groups are always elected. cache_states
bool
(optional, default:True
) If
True
, intermediary states will be cached during the bisection search. entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 niter
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\ln^2 N)\) complexity, where \(E\) is the number of edges and \(N\) is the number of nodes (independently of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 class graph_tool.inference.ModularityState(g, b=None)[source]¶
Bases:
graph_tool.inference.base_states.MCMCState
,graph_tool.inference.base_states.MultiflipMCMCState
,graph_tool.inference.base_states.MultilevelMCMCState
,graph_tool.inference.base_states.GibbsMCMCState
,graph_tool.inference.base_states.DrawBlockState
Obtain the partition of a network according to Newman’s modularity.
Warning
Do not use this approach in the analysis of networks without understanding the consequences. This algorithm is included only for comparison purposes. In general, the inferencebased approaches based on
BlockState
,NestedBlockState
, andPPBlockState
should be universally preferred. Parameters
 g
Graph
Graph to be partitioned.
 b
PropertyMap
(optional, default:None
) Initial partition. If not supplied, a partition into a single group will be used.
 g
 copy(g=None, b=None)[source]¶
Copies the state. The parameters override the state properties, and have the same meaning as in the constructor.
 get_Be()[source]¶
Returns the effective number of blocks, defined as \(e^{H}\), with \(H=\sum_r\frac{n_r}{N}\ln \frac{n_r}{N}\), where \(n_r\) is the number of nodes in group r.
 entropy(gamma=1.0, **kwargs)[source]¶
Return the unnormalized negative generalized modularity.
Notes
The unnormalized negative generalized modularity is defined as
\[\sum_{ij}\left(A_{ij}\gamma \frac{k_ik_j}{2E}\right)\]Where \(A_{ij}\) is the adjacency matrix, \(k_i\) is the degree of node \(i\), and \(E\) is the total number of edges.
 modularity(gamma=1)[source]¶
Return the generalized modularity.
Notes
The generalized modularity is defined as
\[\frac{1}{2E}\sum_{ij}\left(A_{ij}\gamma \frac{k_ik_j}{2E}\right)\]Where \(A_{ij}\) is the adjacency matrix, \(k_i\) is the degree of node \(i\), and \(E\) is the total number of edges.
 draw(**kwargs)¶
Convenience wrapper to
graph_draw()
that draws the state of the graph as colors on the vertices and edges.
 gibbs_sweep(beta=1.0, niter=1, entropy_args={}, allow_new_group=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a rejectionfree Gibbs MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_new_group
bool
(optional, default:True
) Allow the number of groups to increase and decrease.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\times B)\) complexity, where \(B\) is the number of groups, and \(E\) is the number of edges.
 mcmc_sweep(beta=1.0, c=0.5, d=0.01, niter=1, entropy_args={}, allow_vacate=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given move.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_vacate
bool
(optional, default:True
) Allow groups to be vacated.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 multiflip_mcmc_sweep(beta=1.0, c=0.5, psingle=None, psplit=1, pmerge=1, pmergesplit=1, pmovelabel=0, d=0.01, gibbs_sweeps=10, niter=1, entropy_args={}, accept_stats=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC with multiple simultaneous moves (i.e. merges and splits) to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. psplit
float
(optional, default:1
) Relative probability of proposing a group split.
 pmergesplit
float
(optional, default:1
) Relative probability of proposing a margesplit move.
 pmovelabel
float
(optional, default:0
) Relative probability of proposing a group label move.
 d
float
(optional, default:1
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 gibbs_sweeps
int
(optional, default:10
) Number of sweeps of Gibbs sampling to be performed (i.e. each node is attempted once per sweep) to refine a split proposal.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotomergesplit2020
Tiago P. Peixoto, “Mergesplit Markov chain Monte Carlo for community detection”, Phys. Rev. E 102, 012305 (2020), DOI: 10.1103/PhysRevE.102.012305 [scihub, @tor], arXiv: 2003.07070
 multilevel_mcmc_sweep(niter=1, beta=1.0, c=0.5, psingle=None, pmultilevel=1, d=0.01, r=0.9, random_bisect=True, merge_sweeps=10, mh_sweeps=10, init_r=0.99, init_beta=1.0, gibbs=False, B_min=1, B_max=18446744073709551615, b_min=None, b_max=None, M=None, cache_states=True, entropy_args={}, verbose=False, **kwargs)¶
Perform
niter
sweeps of a multilevel agglomerative acceptancerejection MCMC to sample network partitions, that uses a bisection search on the number of groups, together with group merges and singenode moves. Parameters
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. pmultilevel
float
(optional, default:1
) Relative probability of proposing a multilevel move.
 d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 r
float
(optional, default:0.9
) Group shrink ratio. The number of groups is reduced by this fraction at each merge sweep.
 random_bisect
bool
(optional, default:True
) If
True
, bisections are done at randomly chosen intervals. Otherwise a Fibonacci sequence is used. merge_sweeps
int
(optional, default:10
) Number of sweeps spent to find good merge proposals.
 mh_sweeps
int
(optional, default:10
) Number of singlenode MetropolisHastings sweeps between merge splits.
 init_r
double
(optional, default:0.99
) Stopping criterion for the intialization phase, after each node is put in their own group, to set the initial upper bound of the bisection search. A number of singlenode MetropolisHastings sweeps is done until the number of groups is shrunk by a factor that is larger than this parameter.
 init_beta
float
(optional, default:1.
) Inverse temperature to be used for the very first sweep of the initialization phase.
 gibbs
bool
(optional, default:False
) If
True
, the single node moves use (slower) Gibbs sampling, rather than MetropolisHastings. B_min
int
(optional, default:1
) Minimum number of groups to be considered in the search.
 b_min
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_min
. B_max
int
(optional, default:1
) Maximum number of groups to be considered in the search.
 b_max
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_max
. M
int
(optional, default:None
) Maximum number of groups to select for the multilevel move. If
None
is provided, then all groups are always elected. cache_states
bool
(optional, default:True
) If
True
, intermediary states will be cached during the bisection search. entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 niter
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\ln^2 N)\) complexity, where \(E\) is the number of edges and \(N\) is the number of nodes (independently of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 class graph_tool.inference.NormCutState(g, b=None)[source]¶
Bases:
graph_tool.inference.base_states.MCMCState
,graph_tool.inference.base_states.MultiflipMCMCState
,graph_tool.inference.base_states.MultilevelMCMCState
,graph_tool.inference.base_states.GibbsMCMCState
,graph_tool.inference.base_states.DrawBlockState
Obtain the partition of a network according to the normalized cut.
Warning
Do not use this approach in the analysis of networks without understanding the consequences. This algorithm is included only for comparison purposes. In general, the inferencebased approaches based on
BlockState
,NestedBlockState
, andPPBlockState
should be universally preferred. Parameters
 g
Graph
Graph to be partitioned.
 b
PropertyMap
(optional, default:None
) Initial partition. If not supplied, a partition into a single group will be used.
 g
 copy(g=None, b=None)[source]¶
Copies the state. The parameters override the state properties, and have the same meaning as in the constructor.
 get_Be()[source]¶
Returns the effective number of blocks, defined as \(e^{H}\), with \(H=\sum_r\frac{n_r}{N}\ln \frac{n_r}{N}\), where \(n_r\) is the number of nodes in group r.
 entropy(**kwargs)[source]¶
Return the normalized cut. See
norm_cut()
.
 norm_cut()[source]¶
Return the normalized cut.
Notes
The normalized cut is defined as
\[B  \sum_r \frac{e_{rr}}{e_r}\]Where \(B\) is the number of groups, \(e_{rr}\) is twice the number of edges between nodes of group \(r\), and \(e_r\) is the sum of degrees of nodes in group \(r\).
 draw(**kwargs)¶
Convenience wrapper to
graph_draw()
that draws the state of the graph as colors on the vertices and edges.
 gibbs_sweep(beta=1.0, niter=1, entropy_args={}, allow_new_group=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a rejectionfree Gibbs MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_new_group
bool
(optional, default:True
) Allow the number of groups to increase and decrease.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\times B)\) complexity, where \(B\) is the number of groups, and \(E\) is the number of edges.
 mcmc_sweep(beta=1.0, c=0.5, d=0.01, niter=1, entropy_args={}, allow_vacate=True, sequential=True, deterministic=False, vertices=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given move.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. allow_vacate
bool
(optional, default:True
) Allow groups to be vacated.
 sequential
bool
(optional, default:True
) If
sequential == True
each vertex move attempt is made sequentially, where vertices are visited in random order. Otherwise the moves are attempted by sampling vertices randomly, so that the same vertex can be moved more than once, before other vertices had the chance to move. deterministic
bool
(optional, default:False
) If
sequential == True
anddeterministic == True
the vertices will be visited in deterministic order. vertices
list
of ints (optional, default:None
) If provided, this should be a list of vertices which will be moved. Otherwise, all vertices will.
 verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 multiflip_mcmc_sweep(beta=1.0, c=0.5, psingle=None, psplit=1, pmerge=1, pmergesplit=1, pmovelabel=0, d=0.01, gibbs_sweeps=10, niter=1, entropy_args={}, accept_stats=None, verbose=False, **kwargs)¶
Perform
niter
sweeps of a MetropolisHastings acceptancerejection MCMC with multiple simultaneous moves (i.e. merges and splits) to sample network partitions. Parameters
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. psplit
float
(optional, default:1
) Relative probability of proposing a group split.
 pmergesplit
float
(optional, default:1
) Relative probability of proposing a margesplit move.
 pmovelabel
float
(optional, default:0
) Relative probability of proposing a group label move.
 d
float
(optional, default:1
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 gibbs_sweeps
int
(optional, default:10
) Number of sweeps of Gibbs sampling to be performed (i.e. each node is attempted once per sweep) to refine a split proposal.
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 beta
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E)\) complexity, where \(E\) is the number of edges (independent of the number of groups).
References
 peixotomergesplit2020
Tiago P. Peixoto, “Mergesplit Markov chain Monte Carlo for community detection”, Phys. Rev. E 102, 012305 (2020), DOI: 10.1103/PhysRevE.102.012305 [scihub, @tor], arXiv: 2003.07070
 multilevel_mcmc_sweep(niter=1, beta=1.0, c=0.5, psingle=None, pmultilevel=1, d=0.01, r=0.9, random_bisect=True, merge_sweeps=10, mh_sweeps=10, init_r=0.99, init_beta=1.0, gibbs=False, B_min=1, B_max=18446744073709551615, b_min=None, b_max=None, M=None, cache_states=True, entropy_args={}, verbose=False, **kwargs)¶
Perform
niter
sweeps of a multilevel agglomerative acceptancerejection MCMC to sample network partitions, that uses a bisection search on the number of groups, together with group merges and singenode moves. Parameters
 niter
int
(optional, default:1
) Number of sweeps to perform. During each sweep, a move attempt is made for each node, on average.
 beta
float
(optional, default:1.
) Inverse temperature.
 c
float
(optional, default:.5
) Sampling parameter
c
for move proposals: For \(c\to 0\) the blocks are sampled according to the local neighborhood of a given node and their block connections; for \(c\to\infty\) the blocks are sampled randomly. Note that only for \(c > 0\) the MCMC is guaranteed to be ergodic. psingle
float
(optional, default:None
) Relative probability of proposing a single node move. If
None
, it will be selected as the number of nodes in the graph. pmultilevel
float
(optional, default:1
) Relative probability of proposing a multilevel move.
 d
float
(optional, default:.01
) Probability of selecting a new (i.e. empty) group for a given singlenode move.
 r
float
(optional, default:0.9
) Group shrink ratio. The number of groups is reduced by this fraction at each merge sweep.
 random_bisect
bool
(optional, default:True
) If
True
, bisections are done at randomly chosen intervals. Otherwise a Fibonacci sequence is used. merge_sweeps
int
(optional, default:10
) Number of sweeps spent to find good merge proposals.
 mh_sweeps
int
(optional, default:10
) Number of singlenode MetropolisHastings sweeps between merge splits.
 init_r
double
(optional, default:0.99
) Stopping criterion for the intialization phase, after each node is put in their own group, to set the initial upper bound of the bisection search. A number of singlenode MetropolisHastings sweeps is done until the number of groups is shrunk by a factor that is larger than this parameter.
 init_beta
float
(optional, default:1.
) Inverse temperature to be used for the very first sweep of the initialization phase.
 gibbs
bool
(optional, default:False
) If
True
, the single node moves use (slower) Gibbs sampling, rather than MetropolisHastings. B_min
int
(optional, default:1
) Minimum number of groups to be considered in the search.
 b_min
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_min
. B_max
int
(optional, default:1
) Maximum number of groups to be considered in the search.
 b_max
VertexPropertyMap
(optional, default:None
) If provided, this will be used for the partition corresponding to
B_max
. M
int
(optional, default:None
) Maximum number of groups to select for the multilevel move. If
None
is provided, then all groups are always elected. cache_states
bool
(optional, default:True
) If
True
, intermediary states will be cached during the bisection search. entropy_args
dict
(optional, default:{}
) Entropy arguments, with the same meaning and defaults as in
graph_tool.inference.BlockState.entropy()
. verbose
bool
(optional, default:False
) If
verbose == True
, detailed information will be displayed.
 niter
 Returns
 dS
float
Entropy difference after the sweeps.
 nattempts
int
Number of vertex moves attempted.
 nmoves
int
Number of vertices moved.
 dS
Notes
This algorithm has an \(O(E\ln^2 N)\) complexity, where \(E\) is the number of edges and \(N\) is the number of nodes (independently of the number of groups).
References
 peixotoefficient2014
Tiago P. Peixoto, “Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models”, Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [scihub, @tor], arXiv: 1310.4378
 class graph_tool.inference.LatentMultigraphBlockState(g, aE=nan, nested=True, state_args={}, bstate=None, self_loops=False, **kwargs)[source]¶
Bases:
graph_tool.inference.uncertain_blockmodel.UncertainBaseState
Inference state of an erased Poisson multigraph, using the stochastic block model as a prior.
 Parameters
 g
Graph
Measured graph.
 aE
float
(optional, default:NaN
) Expected total number of edges used in prior. If
NaN
, a flat prior will be used instead. nested
boolean
(optional, default:True
) If
True
, aNestedBlockState
will be used, otherwiseBlockState
. state_args
dict
(optional, default:{}
) Arguments to be passed to
NestedBlockState
orBlockState
. bstate
NestedBlockState
orBlockState
(optional, default:None
) If passed, this will be used to initialize the block state directly.
 self_loopsbool (optional, default:
False
) If
True
, it is assumed that the uncertain graph can contain selfloops.
 g
References
 peixotolatent2020
Tiago P. Peixoto, “Latent Poisson models for networks with heterogeneous density”, DOI: 10.1103/PhysRevE.102.012309 [scihub, @tor], arXiv: 2002.07803
 collect_marginal(g=None)¶
Collect marginal inferred network during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal graph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"eprob"
, containing the marginal probabilities for each edge.
 g
Notes
The posterior marginal probability of an edge \((i,j)\) is defined as
\[\pi_{ij} = \sum_{\boldsymbol A}A_{ij}P(\boldsymbol A\boldsymbol D)\]where \(P(\boldsymbol A\boldsymbol D)\) is the posterior probability given the data.
 collect_marginal_multigraph(g=None)¶
Collect marginal latent multigraph during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal multigraph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"w"
and"wcount"
, containing the edge multiplicities and their respective counts.
 g
Notes
The mean posterior marginal multiplicity distribution of a multiedge \((i,j)\) is defined as
\[\pi_{ij}(w) = \sum_{\boldsymbol G}\delta_{w,G_{ij}}P(\boldsymbol G\boldsymbol D)\]where \(P(\boldsymbol G\boldsymbol D)\) is the posterior probability of a multigraph \(\boldsymbol G\) given the data.
 get_block_state()¶
Return the underlying block state, which can be either
BlockState
orNestedBlockState
.
 get_edge_prob(u, v, entropy_args={}, epsilon=1e08)¶
Return conditional posterior logprobability of edge \((u,v)\).
 get_edges_prob(elist, entropy_args={}, epsilon=1e08)¶
Return conditional posterior logprobability of an edge list, with shape \((E,2)\).
 get_graph()¶
Return the current inferred graph.
 mcmc_sweep(r=0.5, multiflip=True, **kwargs)¶
Perform sweeps of a MetropolisHastings acceptancerejection sampling MCMC to sample network partitions and latent edges. The parameter
r
controls the probability with which edge move will be attempted, instead of partition moves. The remaining keyword parameters will be passed tomcmc_sweep()
ormultiflip_mcmc_sweep()
, ifmultiflip=True
.
 multiflip_mcmc_sweep(**kwargs)¶
Alias for
mcmc_sweep()
withmultiflip=True
.
 set_state(g, w)¶
 virtual_add_edge(u, v, entropy_args={})¶
 virtual_remove_edge(u, v, entropy_args={})¶
 class graph_tool.inference.UncertainBlockState(g, q, q_default=0.0, aE=nan, nested=True, state_args={}, bstate=None, self_loops=False, **kwargs)[source]¶
Bases:
graph_tool.inference.uncertain_blockmodel.UncertainBaseState
Inference state of an uncertain graph, using the stochastic block model as a prior.
 Parameters
 g
Graph
Measured graph.
 q
EdgePropertyMap
Edge probabilities in range \([0,1]\).
 q_default
float
(optional, default:0.
) Nonedge probability in range \([0,1]\).
 aE
float
(optional, default:NaN
) Expected total number of edges used in prior. If
NaN
, a flat prior will be used instead. nested
boolean
(optional, default:True
) If
True
, aNestedBlockState
will be used, otherwiseBlockState
. state_args
dict
(optional, default:{}
) Arguments to be passed to
NestedBlockState
orBlockState
. bstate
NestedBlockState
orBlockState
(optional, default:None
) If passed, this will be used to initialize the block state directly.
 self_loopsbool (optional, default:
False
) If
True
, it is assumed that the uncertain graph can contain selfloops.
 g
References
 peixotoreconstructing2018
Tiago P. Peixoto, “Reconstructing networks with unknown and heterogeneous errors”, Phys. Rev. X 8 041011 (2018). DOI: 10.1103/PhysRevX.8.041011 [scihub, @tor], arXiv: 1806.07956
 collect_marginal(g=None)¶
Collect marginal inferred network during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal graph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"eprob"
, containing the marginal probabilities for each edge.
 g
Notes
The posterior marginal probability of an edge \((i,j)\) is defined as
\[\pi_{ij} = \sum_{\boldsymbol A}A_{ij}P(\boldsymbol A\boldsymbol D)\]where \(P(\boldsymbol A\boldsymbol D)\) is the posterior probability given the data.
 collect_marginal_multigraph(g=None)¶
Collect marginal latent multigraph during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal multigraph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"w"
and"wcount"
, containing the edge multiplicities and their respective counts.
 g
Notes
The mean posterior marginal multiplicity distribution of a multiedge \((i,j)\) is defined as
\[\pi_{ij}(w) = \sum_{\boldsymbol G}\delta_{w,G_{ij}}P(\boldsymbol G\boldsymbol D)\]where \(P(\boldsymbol G\boldsymbol D)\) is the posterior probability of a multigraph \(\boldsymbol G\) given the data.
 entropy(latent_edges=True, density=True, **kwargs)¶
Return the entropy, i.e. negative loglikelihood.
 get_block_state()¶
Return the underlying block state, which can be either
BlockState
orNestedBlockState
.
 get_edge_prob(u, v, entropy_args={}, epsilon=1e08)¶
Return conditional posterior logprobability of edge \((u,v)\).
 get_edges_prob(elist, entropy_args={}, epsilon=1e08)¶
Return conditional posterior logprobability of an edge list, with shape \((E,2)\).
 get_graph()¶
Return the current inferred graph.
 mcmc_sweep(r=0.5, multiflip=True, **kwargs)¶
Perform sweeps of a MetropolisHastings acceptancerejection sampling MCMC to sample network partitions and latent edges. The parameter
r
controls the probability with which edge move will be attempted, instead of partition moves. The remaining keyword parameters will be passed tomcmc_sweep()
ormultiflip_mcmc_sweep()
, ifmultiflip=True
.
 multiflip_mcmc_sweep(**kwargs)¶
Alias for
mcmc_sweep()
withmultiflip=True
.
 set_state(g, w)¶
 virtual_add_edge(u, v, entropy_args={})¶
 virtual_remove_edge(u, v, entropy_args={})¶
 class graph_tool.inference.MeasuredBlockState(g, n, x, n_default=1, x_default=0, fn_params={'alpha': 1, 'beta': 1}, fp_params={'mu': 1, 'nu': 1}, aE=nan, nested=True, state_args={}, bstate=None, self_loops=False, **kwargs)[source]¶
Bases:
graph_tool.inference.uncertain_blockmodel.UncertainBaseState
Inference state of a measured graph, using the stochastic block model as a prior.
 Parameters
 g
Graph
Measured graph.
 n
EdgePropertyMap
Edge property map of type
int
, containing the total number of measurements for each edge. x
EdgePropertyMap
Edge property map of type
int
, containing the number of positive measurements for each edge. n_default
int
(optional, default:1
) Total number of measurements for each nonedge.
 x_default
int
(optional, default:0
) Total number of positive measurements for each nonedge.
 fn_params
dict
(optional, default:dict(alpha=1, beta=1)
) Beta distribution hyperparameters for the probability of missing edges (false negatives).
 fp_params
dict
(optional, default:dict(mu=1, nu=1)
) Beta distribution hyperparameters for the probability of spurious edges (false positives).
 aE
float
(optional, default:NaN
) Expected total number of edges used in prior. If
NaN
, a flat prior will be used instead. nested
boolean
(optional, default:True
) If
True
, aNestedBlockState
will be used, otherwiseBlockState
. state_args
dict
(optional, default:{}
) Arguments to be passed to
NestedBlockState
orBlockState
. bstate
NestedBlockState
orBlockState
(optional, default:None
) If passed, this will be used to initialize the block state directly.
 self_loopsbool (optional, default:
False
) If
True
, it is assumed that the uncertain graph can contain selfloops.
 g
References
 peixotoreconstructing2018
Tiago P. Peixoto, “Reconstructing networks with unknown and heterogeneous errors”, Phys. Rev. X 8 041011 (2018). DOI: 10.1103/PhysRevX.8.041011 [scihub, @tor], arXiv: 1806.07956
 get_p_posterior()[source]¶
Get beta distribution parameters for the posterior probability of missing edges.
 get_q_posterior()[source]¶
Get beta distribution parameters for the posterior probability of spurious edges.
 collect_marginal(g=None)¶
Collect marginal inferred network during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal graph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"eprob"
, containing the marginal probabilities for each edge.
 g
Notes
The posterior marginal probability of an edge \((i,j)\) is defined as
\[\pi_{ij} = \sum_{\boldsymbol A}A_{ij}P(\boldsymbol A\boldsymbol D)\]where \(P(\boldsymbol A\boldsymbol D)\) is the posterior probability given the data.
 collect_marginal_multigraph(g=None)¶
Collect marginal latent multigraph during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal multigraph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"w"
and"wcount"
, containing the edge multiplicities and their respective counts.
 g
Notes
The mean posterior marginal multiplicity distribution of a multiedge \((i,j)\) is defined as
\[\pi_{ij}(w) = \sum_{\boldsymbol G}\delta_{w,G_{ij}}P(\boldsymbol G\boldsymbol D)\]where \(P(\boldsymbol G\boldsymbol D)\) is the posterior probability of a multigraph \(\boldsymbol G\) given the data.
 entropy(latent_edges=True, density=True, **kwargs)¶
Return the entropy, i.e. negative loglikelihood.
 get_block_state()¶
Return the underlying block state, which can be either
BlockState
orNestedBlockState
.
 get_edge_prob(u, v, entropy_args={}, epsilon=1e08)¶
Return conditional posterior logprobability of edge \((u,v)\).
 get_edges_prob(elist, entropy_args={}, epsilon=1e08)¶
Return conditional posterior logprobability of an edge list, with shape \((E,2)\).
 get_graph()¶
Return the current inferred graph.
 mcmc_sweep(r=0.5, multiflip=True, **kwargs)¶
Perform sweeps of a MetropolisHastings acceptancerejection sampling MCMC to sample network partitions and latent edges. The parameter
r
controls the probability with which edge move will be attempted, instead of partition moves. The remaining keyword parameters will be passed tomcmc_sweep()
ormultiflip_mcmc_sweep()
, ifmultiflip=True
.
 multiflip_mcmc_sweep(**kwargs)¶
Alias for
mcmc_sweep()
withmultiflip=True
.
 set_state(g, w)¶
 virtual_add_edge(u, v, entropy_args={})¶
 virtual_remove_edge(u, v, entropy_args={})¶
 class graph_tool.inference.UncertainBaseState(g, nested=True, state_args={}, bstate=None, self_loops=False, init_empty=False)[source]¶
Bases:
object
Base state for uncertain network inference.
 get_block_state()[source]¶
Return the underlying block state, which can be either
BlockState
orNestedBlockState
.
 entropy(latent_edges=True, density=True, **kwargs)[source]¶
Return the entropy, i.e. negative loglikelihood.
 mcmc_sweep(r=0.5, multiflip=True, **kwargs)[source]¶
Perform sweeps of a MetropolisHastings acceptancerejection sampling MCMC to sample network partitions and latent edges. The parameter
r
controls the probability with which edge move will be attempted, instead of partition moves. The remaining keyword parameters will be passed tomcmc_sweep()
ormultiflip_mcmc_sweep()
, ifmultiflip=True
.
 multiflip_mcmc_sweep(**kwargs)[source]¶
Alias for
mcmc_sweep()
withmultiflip=True
.
 get_edge_prob(u, v, entropy_args={}, epsilon=1e08)[source]¶
Return conditional posterior logprobability of edge \((u,v)\).
 get_edges_prob(elist, entropy_args={}, epsilon=1e08)[source]¶
Return conditional posterior logprobability of an edge list, with shape \((E,2)\).
 collect_marginal(g=None)[source]¶
Collect marginal inferred network during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal graph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"eprob"
, containing the marginal probabilities for each edge.
 g
Notes
The posterior marginal probability of an edge \((i,j)\) is defined as
\[\pi_{ij} = \sum_{\boldsymbol A}A_{ij}P(\boldsymbol A\boldsymbol D)\]where \(P(\boldsymbol A\boldsymbol D)\) is the posterior probability given the data.
 collect_marginal_multigraph(g=None)[source]¶
Collect marginal latent multigraph during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal multigraph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"w"
and"wcount"
, containing the edge multiplicities and their respective counts.
 g
Notes
The mean posterior marginal multiplicity distribution of a multiedge \((i,j)\) is defined as
\[\pi_{ij}(w) = \sum_{\boldsymbol G}\delta_{w,G_{ij}}P(\boldsymbol G\boldsymbol D)\]where \(P(\boldsymbol G\boldsymbol D)\) is the posterior probability of a multigraph \(\boldsymbol G\) given the data.
 class graph_tool.inference.MixedMeasuredBlockState(g, n, x, n_default=1, x_default=0, fn_params={'alpha': 1, 'beta': 10}, fp_params={'mu': 1, 'nu': 10}, aE=nan, nested=True, state_args={}, bstate=None, self_loops=False, **kwargs)[source]¶
Bases:
graph_tool.inference.uncertain_blockmodel.UncertainBaseState
Inference state of a measured graph with heterogeneous errors, using the stochastic block model as a prior.
 Parameters
 g
Graph
Measured graph.
 n
EdgePropertyMap
Edge property map of type
int
, containing the total number of measurements for each edge. x
EdgePropertyMap
Edge property map of type
int
, containing the number of positive measurements for each edge. n_default
int
(optional, default:1
) Total number of measurements for each nonedge.
 x_default
int
(optional, default:1
) Total number of positive measurements for each nonedge.
 fn_params
dict
(optional, default:dict(alpha=1, beta=10)
) Beta distribution hyperparameters for the probability of missing edges (false negatives).
 fp_params
dict
(optional, default:dict(mu=1, nu=10)
) Beta distribution hyperparameters for the probability of spurious edges (false positives).
 aE
float
(optional, default:NaN
) Expected total number of edges used in prior. If
NaN
, a flat prior will be used instead. nested
boolean
(optional, default:True
) If
True
, aNestedBlockState
will be used, otherwiseBlockState
. state_args
dict
(optional, default:{}
) Arguments to be passed to
NestedBlockState
orBlockState
. bstate
NestedBlockState
orBlockState
(optional, default:None
) If passed, this will be used to initialize the block state directly.
 self_loopsbool (optional, default:
False
) If
True
, it is assumed that the uncertain graph can contain selfloops.
 g
References
 peixotoreconstructing2018
Tiago P. Peixoto, “Reconstructing networks with unknown and heterogeneous errors”, Phys. Rev. X 8 041011 (2018). DOI: 10.1103/PhysRevX.8.041011 [scihub, @tor], arXiv: 1806.07956
 mcmc_sweep(r=0.5, h=0.1, hstep=1, multiflip=True, **kwargs)[source]¶
Perform sweeps of a MetropolisHastings acceptancerejection sampling MCMC to sample network partitions and latent edges. The parameter
r
controls the probability with which edge move will be attempted, instead of partition moves. The parameterh
controls the relative probability with which hyperparamters moves will be attempted, andhstep
is the size of the step.The remaining keyword parameters will be passed to
mcmc_sweep()
ormultiflip_mcmc_sweep()
, ifmultiflip=True
.
 collect_marginal(g=None)¶
Collect marginal inferred network during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal graph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"eprob"
, containing the marginal probabilities for each edge.
 g
Notes
The posterior marginal probability of an edge \((i,j)\) is defined as
\[\pi_{ij} = \sum_{\boldsymbol A}A_{ij}P(\boldsymbol A\boldsymbol D)\]where \(P(\boldsymbol A\boldsymbol D)\) is the posterior probability given the data.
 collect_marginal_multigraph(g=None)¶
Collect marginal latent multigraph during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal multigraph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"w"
and"wcount"
, containing the edge multiplicities and their respective counts.
 g
Notes
The mean posterior marginal multiplicity distribution of a multiedge \((i,j)\) is defined as
\[\pi_{ij}(w) = \sum_{\boldsymbol G}\delta_{w,G_{ij}}P(\boldsymbol G\boldsymbol D)\]where \(P(\boldsymbol G\boldsymbol D)\) is the posterior probability of a multigraph \(\boldsymbol G\) given the data.
 entropy(latent_edges=True, density=True, **kwargs)¶
Return the entropy, i.e. negative loglikelihood.
 get_block_state()¶
Return the underlying block state, which can be either
BlockState
orNestedBlockState
.
 get_edge_prob(u, v, entropy_args={}, epsilon=1e08)¶
Return conditional posterior logprobability of edge \((u,v)\).
 get_edges_prob(elist, entropy_args={}, epsilon=1e08)¶
Return conditional posterior logprobability of an edge list, with shape \((E,2)\).
 get_graph()¶
Return the current inferred graph.
 multiflip_mcmc_sweep(**kwargs)¶
Alias for
mcmc_sweep()
withmultiflip=True
.
 set_state(g, w)¶
 virtual_add_edge(u, v, entropy_args={})¶
 virtual_remove_edge(u, v, entropy_args={})¶
 class graph_tool.inference.DynamicsBlockStateBase(g, s, t, x=None, aE=nan, nested=True, state_args={}, bstate=None, self_loops=False, **kwargs)[source]¶
Bases:
graph_tool.inference.uncertain_blockmodel.UncertainBaseState
Base state for network reconstruction based on dynamical data, using the stochastic block model as a prior. This class is not meant to be instantiated directly, only indirectly via one of its subclasses.
 get_edge_prob(u, v, x, entropy_args={}, epsilon=1e08)[source]¶
Return conditional posterior logprobability of edge \((u,v)\).
 collect_marginal(g=None)[source]¶
Collect marginal inferred network during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal graph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"eprob"
, containing the marginal probabilities for each edge.
 g
Notes
The posterior marginal probability of an edge \((i,j)\) is defined as
\[\pi_{ij} = \sum_{\boldsymbol A}A_{ij}P(\boldsymbol A\boldsymbol D)\]where \(P(\boldsymbol A\boldsymbol D)\) is the posterior probability given the data.
 collect_marginal_multigraph(g=None)¶
Collect marginal latent multigraph during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal multigraph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"w"
and"wcount"
, containing the edge multiplicities and their respective counts.
 g
Notes
The mean posterior marginal multiplicity distribution of a multiedge \((i,j)\) is defined as
\[\pi_{ij}(w) = \sum_{\boldsymbol G}\delta_{w,G_{ij}}P(\boldsymbol G\boldsymbol D)\]where \(P(\boldsymbol G\boldsymbol D)\) is the posterior probability of a multigraph \(\boldsymbol G\) given the data.
 entropy(latent_edges=True, density=True, **kwargs)¶
Return the entropy, i.e. negative loglikelihood.
 get_block_state()¶
Return the underlying block state, which can be either
BlockState
orNestedBlockState
.
 get_edges_prob(elist, entropy_args={}, epsilon=1e08)¶
Return conditional posterior logprobability of an edge list, with shape \((E,2)\).
 get_graph()¶
Return the current inferred graph.
 mcmc_sweep(r=0.5, multiflip=True, **kwargs)¶
Perform sweeps of a MetropolisHastings acceptancerejection sampling MCMC to sample network partitions and latent edges. The parameter
r
controls the probability with which edge move will be attempted, instead of partition moves. The remaining keyword parameters will be passed tomcmc_sweep()
ormultiflip_mcmc_sweep()
, ifmultiflip=True
.
 multiflip_mcmc_sweep(**kwargs)¶
Alias for
mcmc_sweep()
withmultiflip=True
.
 set_state(g, w)¶
 virtual_add_edge(u, v, entropy_args={})¶
 virtual_remove_edge(u, v, entropy_args={})¶
 class graph_tool.inference.EpidemicsBlockState(g, s, beta, r, r_v=None, global_beta=None, active=None, t=[], exposed=False, aE=nan, nested=True, state_args={}, bstate=None, self_loops=False, **kwargs)[source]¶
Bases:
graph_tool.inference.uncertain_blockmodel.DynamicsBlockStateBase
Inference state for network reconstruction based on epidemic dynamics, using the stochastic block model as a prior.
 Parameters
 g
Graph
Initial graph state.
 s
list
ofVertexPropertyMap
Collection of timeseries with node states over time. Each entry in this list must be a
VertexPropertyMap
with typevector<int>
containing the states of each node in each time step. A value of1
means infected and0
susceptible. Other values are allowed (e.g. for recovered), but their actual value is unimportant for reconstruction.If the parameter
t
below is given, each property map value for a given node should contain only the states for the same points in time given by that parameter. beta
float
orEdgePropertyMap
Initial value of the global or local transmission probability for each edge.
 r
float
Spontaneous infection probability.
 r_v
VertexPropertyMap
(optional, default:None
) If given, this will set the initial spontaneous infection probability for each node, and trigger the use of a model where this quantity is in principle different for each node.
 global_beta
float
(optional, default:None
) If provided, and
beta is None
this will trigger the use of a model where all transmission probabilities on edges are the same, and given (initially) by this value. t
list
ofVertexPropertyMap
(optional, default:[]
) If nonempty, this allows for a compressed representation of the timeseries parameter
s
, corresponding only to points in time where the state of each node changes. Each entry in this list must be aVertexPropertyMap
with typevector<int>
containing the points in time where the state of each node change. The corresponding state of the nodes at these times are given by parameters
. active
list
ofVertexPropertyMap
(optional, default:None
) If given, this specifies the points in time where each node is “active”, and prepared to change its state according to the state of its neighbors. Each entry in this list must be a
VertexPropertyMap
with typevector<int>
containing the states of each node in each time step. A value of1
means active and0
inactive. exposed
boolean
(optional, default:False
) If
True
, the data is supposed to come from a SEI, SEIR, etc. model, where a susceptible node (valued0
) first transits to an exposed state (valued1
) upon transmission, before transiting to the infective state (valued1
). aE
float
(optional, default:NaN
) Expected total number of edges used in prior. If
NaN
, a flat prior will be used instead. nested
boolean
(optional, default:True
) If
True
, aNestedBlockState
will be used, otherwiseBlockState
. state_args
dict
(optional, default:{}
) Arguments to be passed to
NestedBlockState
orBlockState
. bstate
NestedBlockState
orBlockState
(optional, default:None
) If passed, this will be used to initialize the block state directly.
 self_loopsbool (optional, default:
False
) If
True
, it is assumed that the inferred graph can contain selfloops.
 g
References
 peixotonetwork2019
Tiago P. Peixoto, “Network reconstruction and community detection from dynamics”, Phys. Rev. Lett. 123 128301 (2019), DOI: 10.1103/PhysRevLett.123.128301 [scihub, @tor], arXiv: 1903.10833
 mcmc_sweep(r=0.5, p=0.1, pstep=0.1, h=0.1, hstep=1, xstep=0.1, multiflip=True, **kwargs)[source]¶
Perform sweeps of a MetropolisHastings acceptancerejection sampling MCMC to sample network partitions and latent edges. The parameter
r
controls the probability with which edge move will be attempted, instead of partition moves. The parameterh
controls the relative probability with which moves for the parametersr_v
will be attempted, andhstep
is the size of the step. The parameterp
controls the relative probability with which moves for the parametersglobal_beta
andr
will be attempted, andpstep
is the size of the step. The paramterxstep
determines the size of the attempted steps for the edge transmission probabilities.The remaining keyword parameters will be passed to
mcmc_sweep()
ormultiflip_mcmc_sweep()
, ifmultiflip=True
.
 collect_marginal(g=None)¶
Collect marginal inferred network during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal graph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"eprob"
, containing the marginal probabilities for each edge.
 g
Notes
The posterior marginal probability of an edge \((i,j)\) is defined as
\[\pi_{ij} = \sum_{\boldsymbol A}A_{ij}P(\boldsymbol A\boldsymbol D)\]where \(P(\boldsymbol A\boldsymbol D)\) is the posterior probability given the data.
 collect_marginal_multigraph(g=None)¶
Collect marginal latent multigraph during MCMC runs.
 Parameters
 g
Graph
(optional, default:None
) Previous marginal multigraph.
 g
 Returns
 g
Graph
New marginal graph, with internal edge
EdgePropertyMap
"w"
and"wcount"
, containing the edge multiplicities and their respective counts.
 g
Notes
The mean posterior marginal multiplicity distribution of a multiedge \((i,j)\) is defined as
\[\pi_{ij}(w) = \sum_{\boldsymbol G}\delta_{w,G_{ij}}P(\boldsymbol G\boldsymbol D)\]where \(P(\boldsymbol G\boldsymbol D)\) is the posterior probability of a multigraph \(\boldsymbol G\) given the data.
 entropy(latent_edges=True, density=True, **kwargs)¶
Return the entropy, i.e. negative loglikelihood.
 get_block_state()¶
Return the underlying block state, which can be either
BlockState
orNestedBlockState
.
 get_edge_prob(u, v, x, entropy_args={}, epsilon=1e08)¶
Return conditional posterior logprobability of edge \((u,v)\).
 get_edges_prob(elist, entropy_args={}, epsilon=1e08)¶
Return conditional posterior logprobability of an edge list, with shape \((E,2)\).
 get_graph()¶
Return the current inferred graph.
 multiflip_mcmc_sweep(**kwargs)¶
Alias for
mcmc_sweep()
withmultiflip=True
.
 set_state(g, w)¶
 virtual_add_edge(u, v, entropy_args={})¶
 virtual_remove_edge(u, v, entropy_args={})¶
 class graph_tool.inference.IsingBaseBlockState(g, s, beta, x=None, h=None, t=None, aE=nan, nested=True, state_args={}, bstate=None, self_loops=False, has_zero=False, **kwargs)[source]¶
Bases:
graph_tool.inference.uncertain_blockmodel.DynamicsBlockStateBase
Base state for network reconstruction based on the Ising model, using the stochastic block model as a prior. This class is not supposed to be instantiated directly. Instead one of its specialized subclasses must be used, which have the same signature:
IsingGlauberBlockState
,PseudoIsingBlockState
,CIsingGlauberBlockState
,PseudoCIsingBlockState
. Parameters
 g
Graph
Initial graph state.
 s
list
ofVertexPropertyMap
orVertexPropertyMap
Collection of timeseries with node states over time, or a single timeseries. Each timeseries must be a
VertexPropertyMap
with typevector<int>
containing the Ising states (1
or+1
) of each node in each time step.If the parameter
t
below is given, each property map value for a given node should contain only the states for the same points in time given by that parameter. beta
float
Initial value of the global inverse temperature.
 x
EdgePropertyMap
(optional, default:None
) Initial value of the local coupling for each edge. If not given, a uniform value of
1
will be used. h
VertexPropertyMap
(optional, default:None
) If given, this will set the initial local fields of each node. Otherwise a value of
0
will be used. t
list
ofVertexPropertyMap
(optional, default:[]
) If nonempty, this allows for a compressed representation of the timeseries parameter
s
, corresponding only to points in time where the state of each node changes. Each entry in this list must be aVertexPropertyMap
with typevector<int>
containing the points in time where the state of each node change. The corresponding state of the nodes at these times are given by parameters
. aE
float
(optional, default:NaN
) Expected total number of edges used in prior. If
NaN
, a flat prior will be used instead. nested
boolean
(optional, default:True
) If
True
, aNestedBlockState
will be used, otherwiseBlockState
. state_args
dict
(optional, default:{}
)
 g