minimize_nested_blockmodel_dl

graph_tool.inference.minimize_nested_blockmodel_dl(g, state=<class 'graph_tool.inference.nested_blockmodel.NestedBlockState'>, base_state=<class 'graph_tool.inference.blockmodel.BlockState'>, state_args={}, base_state_args={}, multilevel_mcmc_args={}, simple_init=False, base_factor=10.0, B_min_base=1000, top_factor=2.0, refine=True, epsilon=0.001)

Fit the nested stochastic block model, by minimizing its description length using an agglomerative heuristic.

Parameters:

gGraph

The graph.

statenested SBM state class (optional, default: NestedBlockState)

Type of next model that will be used.

base_statebase SBM state class (optional, default: BlockState)

Type of model that will be used at the bottom of the hierarchy.

state_argsdict (optional, default: {})

Arguments to be passed to appropriate state constructor (e.g. NestedBlockState)

base_state_argsdict (optional, default: {})

Arguments to be passed to appropriate base state constructor (e.g. BlockState)

multilevel_mcmc_argsdict (optional, default: {})

Arguments to be passed to multilevel_mcmc_sweep().

simple_initbool (optional, default: False)

If True, a simple initialization scheme will be used, where the hierarchy shape will be upper bounded by an initial guess based on the number of nodes and the paramters base_factor, top_factor, and B_min_base. This is meant to be used with refine == True for an alternative to the more expensive multilevel minimization algorithm.

base_factorfloat (optional, default: 10.)

If simple_init == True, this will determine the minimum number of groups at the lowest level of the hierarchy as N/base_factor, where N is the number of vertices at the base level.

B_min_baseint (optional, default: 1000)

If simple_init == True, this will determine the smallest minimum number of groups at the lowest level during initialization, regardless of the value of base_factor.

top_factorfloat (optional, default: 2.)

If simple_init == True, this will determine the minimum number of groups at the upper levels of the hierarchy as N/top_factor, where N is the number of vertices at a particular level.

refinebool (optional, default: True)

If True, a refinement loop will be run as a final step, controlled by the relative convergence criterion epsilon.

epsilonfloat (optional, default: 0.001)

If refine == True, this value determines the relative convergence criterion of the refinement step.

Returns:

min_statetype given by parameter state

State with minimum description length.

Notes

This function is a convenience wrapper around multilevel_mcmc_sweep().

See [peixoto-hierarchical-2014] 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.

Parallel implementation.

If enabled during compilation, this algorithm will run in parallel using OpenMP. See the parallel algorithms section for information about how to control several aspects of parallelization.

References

[peixoto-hierarchical-2014]

Tiago P. Peixoto, “Hierarchical block structures and high-resolution model selection in large networks “, Phys. Rev. X 4, 011047 (2014), DOI: 10.1103/PhysRevX.4.011047 [sci-hub, @tor], arXiv: 1310.4377.

Examples

>>> g = gt.collection.data["power"]
>>> state = gt.minimize_nested_blockmodel_dl(g)
>>> state.draw(output="power_nested_mdl.pdf")
(...)

Hierarchical Block partition of a power-grid network, which minimizes the description length of the network according to the nested (degree-corrected) stochastic blockmodel.

>>> g = gt.collection.data["celegansneural"]
>>> state = gt.minimize_nested_blockmodel_dl(g, base_state=gt.OverlapBlockState)
>>> state.draw(output="celegans_nested_mdl_overlap.pdf")
(...)

Overlapping block partition of the C. elegans neural network, which minimizes the description length of the network according to the nested overlapping degree-corrected stochastic blockmodel.