MultilevelMCMCState#
- class graph_tool.inference.MultilevelMCMCState(entropy_args={})[source]#
Bases:
EntropyStateBase state that implements multilevel agglomerative MCMC sweeps.
Methods
copy(**kwargs)Copies the block state.
get_N()Return the current default values for the parameters of the function
entropy(), together with other operations that depend on them.multilevel_mcmc_sweep([niter, beta, ...])Perform
nitersweeps of a multilevel agglomerative acceptance-rejection pseudo-MCMC (i.e. detailed balance is not preserved) to sample network partitions, that uses a bisection search on the number of groups, together with group merges and singe-node moves.Reset the current default values for the parameters of the function
entropy(), together with other operations that depend on them.update_entropy_args(**kwargs)Update the default values for the parameters of the function
entropy()from the keyword arguments, in a stateful way, together with other operations that depend on them.- copy(**kwargs)#
Copies the block state. The parameters override the state properties, and have the same meaning as in the constructor.
- get_entropy_args()#
Return the current default values for the parameters of the function
entropy(), together with other operations that depend on them.
- multilevel_mcmc_sweep(niter=1, beta=inf, bisection=True, random_bisection=True, refine=False, c=0.5, d=0.01, r=0.9, dB_epsilon=0.01, merge_sweeps=10, mh_sweeps=10, init_r=0.99, init_min_iter=8, init_min_iter_beta=4, init_beta=1.0, gibbs=False, B_min=1, B_max=18446744073709551615, b_min=None, b_max=None, M=None, sample_group_thres=1000, cache_states=True, force_accept=False, parallel=True, parallel_thres=1000, parallel_merge=True, vertices=None, entropy_args={}, verbose=False, **kwargs)[source]#
Perform
nitersweeps of a multilevel agglomerative acceptance-rejection pseudo-MCMC (i.e. detailed balance is not preserved) to sample network partitions, that uses a bisection search on the number of groups, together with group merges and singe-node 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:numpy.inf) Inverse temperature.
- bisection
bool(optional, default:True) If
True, the algorithm will perform a bisection search over the number of groups. Otherwise, a simpler agglomerative approach will be used instead.- random_bisection
bool(optional, default:True) If
True, bisections are done at intervals chosen uniformly at random. Otherwise a Fibonacci sequence is used.- refine
bool(optional, default:True) If
True, a strictly agglomerative run will be appended to the end of the algorithm.- c
float(optional, default:.5) Sampling parameter
cfor 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 single-node move.
- r
float(optional, default:0.9) Group shrink ratio. The number of groups is reduced by this fraction at each merge sweep.
- merge_sweeps
int(optional, default:10) Number of sweeps spent to find good merge proposals.
- mh_sweeps
int(optional, default:10) Number of single-node Metropolis-Hastings 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 single-node Metropolis-Hastings sweeps is done until the number of groups is shrunk by a factor that is larger than this parameter.
- init_min_iter
int(optional, default:8) Minimum number of iterations at the intialization phase.
- init_min_iter_beta
int(optional, default:4) Minimum number of iterations at the intialization phase with beta given by
init_beta.- init_beta
float(optional, default:1.) Inverse temperature to be used for the first
init_min_iter_betasweeps of the initialization phase.- gibbs
bool(optional, default:False) If
True, the single node moves use (slower) Gibbs sampling, rather than Metropolis-Hastings.- 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:numpy.iinfo(numpy.uint64).max) 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
Noneis provided, then all groups are always elected.- cache_states
bool(optional, default:True) If
True, intermediary states will be cached during the bisection search.- force_accept
bool(optional, default:False) If
True, new state will be accepted even if it does not improve the objective function.- parallel
bool(optional, default:True) If
True, the algorithm will run in parallel (if enabled during compilation).- parallel_thres
int(optional, default:1000) If the number of nodes to be moved fall below this thershold, the operation is performed serially. Otherwise, the moves are done in parallel.
- verticesiterable of
int`(optional, default:None): If provided, this specified the list of vertices to be considerd. Otherwise, all vertices are considered.
- 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).
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-efficient-2014]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 [sci-hub, @tor], arXiv: 1310.4378