graph_tool.inference

This module contains algorithms for the identification of large-scale 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

High-level functions

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

State classes

BlockState	The stochastic block model state of a given graph.
OverlapBlockState	The overlapping stochastic block model state of a given graph.
LayeredBlockState	The (possibly overlapping) block state of a given graph, where the edges are divided into discrete layers.
NestedBlockState	The nested stochastic block model state of a given graph.
PPBlockState	Obtain the partition of a network according to the Bayesian planted partition model.
RankedBlockState	Obtain the ordered partition of a network according to the ranked stochastic block model.
ModularityState	Obtain the partition of a network according to the maximization of Newman's modularity.
NormCutState	Obtain the partition of a network according to the normalized cut.
TemperingState	This class aggregates several state classes and corresponding inverse-temperature values to implement parallel tempering MCMC.
CliqueState	The state of a clique decomposition of a given graph.

Abstract base classes

EntropyState	Base state that implements entropy arguments.
MCMCState	Base state that implements single-flip MCMC sweeps.
MultiflipMCMCState	Base state that implements multiflip (merge-split) MCMC sweeps.
MultilevelMCMCState	Base state that implements multilevel agglomerative MCMC sweeps.
GibbsMCMCState	Base state that implements single flip MCMC sweeps.
MulticanonicalMCMCState	Base state that implements multicanonical MCMC sweeps.
ExhaustiveSweepState	Base state that implements exhaustive enumerative sweeps.
DrawBlockState	Base state that implements group-based drawing.

Sampling and minimization

mcmc_equilibrate	Equilibrate a MCMC with a given starting state.
mcmc_anneal	Equilibrate a MCMC at a specified target temperature by performing simulated annealing.
multicanonical_equilibrate	Equilibrate a multicanonical Monte Carlo sampling using the Wang-Landau algorithm.

MulticanonicalState

The density of states of a multicanonical Monte Carlo algorithm.

Comparing and manipulating partitions

PartitionModeState	The random label model state for a set of labelled partitions, which attempts to align them with a common group labelling.
ModeClusterState	The mixed random label model state for a set of labelled partitions, which attempts to align them inside clusters with a common group labelling.
PartitionCentroidState	Obtain the center of a set of partitions, according to the variation of information metric or reduced mutual information.

partition_overlap	Returns the maximum overlap between partitions, according to an optimal label alignment.
nested_partition_overlap	Returns the hierarchical maximum overlap between nested partitions, according to an optimal recursive label alignment.
variation_information	Returns the variation of information between two partitions.
mutual_information	Returns the mutual information between two partitions.
reduced_mutual_information	Returns the reduced mutual information between two partitions.
contingency_graph	Returns the contingency graph between both partitions.
shuffle_partition_labels	Returns a copy of partition x, with the group labels randomly shuffled.
order_partition_labels	Returns a copy of partition x, with the group labels ordered decreasingly according to group size.
order_nested_partition_labels	Returns a copy of nested partition x, with the group labels ordered decreasingly according to group size at each level.
align_partition_labels	Returns a copy of partition x, with the group labels aligned as to maximize the overlap with y.
align_nested_partition_labels	Returns a copy of nested partition x, with the group labels aligned as to maximize the overlap with y.
partition_overlap_center	Find a partition with a maximal overlap to all items of the list of partitions given.
nested_partition_overlap_center	Find a nested partition with a maximal overlap to all items of the list of nested partitions given.
nested_partition_clear_null	Returns a copy of nested partition x where the null values -1 are replaced with 0.
contiguous_map	Remap the values of prop in the contiguous range \([0, N-1]\).
nested_contiguous_map	Remap the values of the nested partition bs in the contiguous range \([0, N_l-1]\) for each level \(l\).

Auxiliary functions

mf_entropy	Compute the "mean field" entropy given the vertex block membership marginals.
bethe_entropy	Compute the Bethe entropy given the edge block membership marginals.
microstate_entropy	Compute microstate entropy given a histogram of partitions.
marginal_multigraph_entropy	Compute the entropy of the marginal latent multigraph distribution.
half_edge_graph	Generate a half-edge graph, where each half-edge is represented by a node, and an edge connects the half-edges like in the original graph.
get_block_edge_gradient	Get edge gradients corresponding to the block membership at the endpoints of the edges given by the be edge property map.

Auxiliary classes

PartitionHist	Histogram of partitions, implemented in C++.
BlockPairHist	Histogram of block pairs, implemented in C++.

Nonparametric network reconstruction

Reconstruction from direct measurements

LatentLayerBaseState	Base state for uncertain latent layer network inference.
LatentMultigraphBlockState	Inference state of an erased Poisson multigraph, using the stochastic block model as a prior.
LatentClosureBlockState	Inference state of the stochastic block model with latent triadic closure edges.
MeasuredBlockState	Inference state of a measured graph, using the stochastic block model as a prior.
MeasuredClosureBlockState	Inference state of a measured graph, using the stochastic block model with triadic closure as a prior.
MixedMeasuredBlockState	Inference state of a measured graph with heterogeneous errors, using the stochastic block model as a prior.
UncertainBlockState	Inference state of an uncertain graph, using the stochastic block model as a prior.
UncertainBaseState	Base state for uncertain network inference.

Expectation-maximization inference

latent_multigraph

Infer latent Poisson multigraph model given an "erased" simple graph.

Reconstruction from dynamics and behavior

DynamicsBlockStateBase	Base state for network reconstruction based on dynamical or behavioral data, using the stochastic block model as a prior.
BPBlockStateBase	Base state for network reconstruction where the respective model can be used with belief-propagation.
PseudoNormalBlockState	State for network reconstruction based on the multivariate normal distribution, using the Pseudolikelihood approximation and the stochastic block model as a prior.
NormalGlauberBlockState	State for network reconstruction based on the dynamical multivariate normal distribution, using the Pseudolikelihood approximation and the stochastic block model as a prior.
LinearNormalBlockState	State for network reconstruction based on a linear dynamical model.
LVBlockState	Base state for network reconstruction based on dynamical or behavioral data, using the stochastic block model as a prior.
EpidemicsBlockState	Inference state for network reconstruction based on epidemic dynamics, using the stochastic block model as a prior.
IsingBlockStateBase	Base state for network reconstruction based on the Ising model, using the stochastic block model as a prior.
IsingGlauberBlockState	State for network reconstruction based on the Glauber dynamics of the Ising model, using the stochastic block model as a prior.
CIsingGlauberBlockState	State for network reconstruction based on the Glauber dynamics of the continuous Ising model, using the stochastic block model as a prior.
PseudoIsingBlockState	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.
PseudoCIsingBlockState	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.

Semiparametric stochastic block model inference

State classes

EMBlockState

The parametric, undirected stochastic block model state of a given graph.

Expectation-maximization Inference

em_infer

Infer the model parameters and latent variables using the expectation-maximization (EM) algorithm with initial state given by state.

Large-scale descriptors

modularity

Calculate Newman's (generalized) modularity of a network partition.