MultilevelMCMCState#
- class graph_tool.inference.MultilevelMCMCState(entropy_args={})[source]#
Bases:
EntropyState
Base state that implements multilevel agglomerative MCMC sweeps.
Methods
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, c, d, ...])Perform
niter
sweeps 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.- 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, c=0.5, d=0.01, r=0.9, random_bisect=True, merge_sweeps=10, mh_sweeps=10, init_r=0.99, init_min_iter=5, init_beta=1.0, gibbs=False, B_min=1, B_max=18446744073709551615, b_min=None, b_max=None, M=None, cache_states=True, force_accept=False, parallel=False, entropy_args={}, verbose=False, **kwargs)[source]#
Perform
niter
sweeps 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.
- 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 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.
- 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 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:5
) Minimum number of iterations at the intialization phase.
- 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 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: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.- 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:False
) If
True
, the algorithm will run in parallel (if enabled during compilation).- 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
[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