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#

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#

State classes#

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.

DynamicsBlockStateBase

Base state for network reconstruction based on dynamical 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.

IsingBaseBlockState

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.

Expectation-maximization Inference#

latent_multigraph

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

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.