percolate package¶
Submodules¶
percolate.hpc module¶
Low-level routines to implement the Newman-Ziff algorithm for HPC
See also
percolate
- The high-level module
-
percolate.hpc.
bond_canonical_statistics
(microcanonical_statistics, convolution_factors, **kwargs)[source]¶ canonical cluster statistics for a single run and a single probability
Parameters: - microcanonical_statistics (ndarray) – Return value of bond_microcanonical_statistics
- convolution_factors (1-D array_like) – The coefficients of the convolution for the given probabilty
p
and for each occupation numbern
.
Returns: - ret (ndarray of size
1
) – Structured array with dtype as returned by canonical_statistics_dtype - ret[‘percolation_probability’] (ndarray of float) –
The “percolation probability” of this run at the value of
p
. Only exists if microcanonical_statistics argument has thehas_spanning_cluster
field. - ret[‘max_cluster_size’] (ndarray of int) – Weighted size of the largest cluster (absolute number of sites)
- ret[‘moments’] (1-D
numpy.ndarray
of float) – Array of size5
. Thek
-th entry is the weightedk
-th raw moment of the (absolute) cluster size distribution, withk
ranging from0
to4
.
-
percolate.hpc.
bond_initialize_canonical_averages
(canonical_statistics, **kwargs)[source]¶ Initialize the canonical averages from a single-run cluster statistics
Parameters: canonical_statistics (1-D structured ndarray) – Typically contains the canonical statistics for a range of values of the occupation probability p
. The dtype is the result of canonical_statistics_dtype.Returns: - ret (structured ndarray) – The dype is the result of canonical_averages_dtype.
- ret[‘number_of_runs’] (1-D ndarray of int) –
Equals
1
(initial run). - ret[‘percolation_probability_mean’] (1-D array of float) –
Equals
canonical_statistics['percolation_probability']
(ifpercolation_probability
is present) - ret[‘percolation_probability_m2’] (1-D array of float) –
Each entry is
0.0
- ret[‘max_cluster_size_mean’] (1-D array of float) –
Equals
canonical_statistics['max_cluster_size']
- ret[‘max_cluster_size_m2’] (1-D array of float) –
Each entry is
0.0
- ret[‘moments_mean’] (2-D array of float) –
Equals
canonical_statistics['moments']
- ret[‘moments_m2’] (2-D array of float) –
Each entry is
0.0
-
percolate.hpc.
bond_microcanonical_statistics
(perc_graph, num_nodes, num_edges, seed, spanning_cluster=True, auxiliary_node_attributes=None, auxiliary_edge_attributes=None, spanning_sides=None, **kwargs)[source]¶ Evolve a single run over all microstates (bond occupation numbers)
Return the cluster statistics for each microstate
Parameters: - perc_graph (networkx.Graph) – The substrate graph on which percolation is to take place
- num_nodes (int) – Number
N
of sites in the graph - num_edges (int) – Number
M
of bonds in the graph - seed ({None, int, array_like}) – Random seed initializing the pseudo-random number generator. Piped through to numpy.random.RandomState constructor.
- spanning_cluster (bool, optional) – Whether to detect a spanning cluster or not.
Defaults to
True
. - auxiliary_node_attributes (optional) – Value of
networkx.get_node_attributes(graph, 'span')
- auxiliary_edge_attributes (optional) – Value of
networkx.get_edge_attributes(graph, 'span')
- spanning_sides (list, optional) – List of keys (attribute values) of the two sides of the auxiliary
nodes.
Return value of
list(set(auxiliary_node_attributes.values()))
Returns: - ret (ndarray of size
num_edges + 1
) – Structured array with dtypedtype=[('has_spanning_cluster', 'bool'), ('max_cluster_size', 'uint32'), ('moments', 'uint64', 5)]
- ret[‘n’] (ndarray of int) – The number of bonds added at the particular iteration
- ret[‘edge’] (ndarray of int) –
The index of the edge added at the particular iteration.
Note that
ret['edge'][0]
is undefined! - ret[‘has_spanning_cluster’] (ndarray of bool) –
True
if there is a spanning cluster,False
otherwise. Only exists if spanning_cluster argument is set toTrue
. - ret[‘max_cluster_size’] (int) – Size of the largest cluster (absolute number of sites)
- ret[‘moments’] (2-D
numpy.ndarray
of int) – Array of shape(num_edges + 1, 5)
. Thek
-th entry is thek
-th raw moment of the (absolute) cluster size distribution, withk
ranging from0
to4
.
See also
bond_sample_states()
,microcanonical_statistics_dtype()
,numpy.random.RandomState()
-
percolate.hpc.
bond_reduce
(row_a, row_b)[source]¶ Reduce the canonical averages over several runs
This is a “true” reducer. It is associative and commutative.
This is a wrapper around simoa.stats.online_variance.
Parameters: row_b (row_a,) – Output of this function, or initial input from bond_initialize_canonical_averages Returns: ret – Array is of dtype as returned by canonical_averages_dtype Return type: structured ndarray See also
bond_initialize_canonical_averages()
,canonical_averages_dtype()
,simoa.stats.online_variance()
-
percolate.hpc.
bond_sample_states
(perc_graph, num_nodes, num_edges, seed, spanning_cluster=True, auxiliary_node_attributes=None, auxiliary_edge_attributes=None, spanning_sides=None, **kwargs)[source]¶ Generate successive sample states of the bond percolation model
This is a generator function to successively add one edge at a time from the graph to the percolation model. At each iteration, it calculates and returns the cluster statistics. CAUTION: it returns a reference to the internal array, not a copy.
Parameters: - perc_graph (networkx.Graph) – The substrate graph on which percolation is to take place
- num_nodes (int) – Number
N
of sites in the graph - num_edges (int) – Number
M
of bonds in the graph - seed ({None, int, array_like}) – Random seed initializing the pseudo-random number generator. Piped through to numpy.random.RandomState constructor.
- spanning_cluster (bool, optional) – Whether to detect a spanning cluster or not.
Defaults to
True
. - auxiliary_node_attributes (optional) – Return value of
networkx.get_node_attributes(graph, 'span')
- auxiliary_edge_attributes (optional) – Return value of
networkx.get_edge_attributes(graph, 'span')
- spanning_sides (list, optional) – List of keys (attribute values) of the two sides of the auxiliary
nodes.
Return value of
list(set(auxiliary_node_attributes.values()))
Yields: - ret (ndarray) –
Structured array with dtype
dtype=[('has_spanning_cluster', 'bool'), ('max_cluster_size', 'uint32'), ('moments', 'int64', 5)]
- ret[‘n’] (ndarray of int) – The number of bonds added at the particular iteration
- ret[‘edge’] (ndarray of int) –
The index of the edge added at the particular iteration
Note that in the first step, when
ret['n'] == 0
, this value is undefined! - ret[‘has_spanning_cluster’] (ndarray of bool) –
True
if there is a spanning cluster,False
otherwise. Only exists if spanning_cluster argument is set toTrue
. - ret[‘max_cluster_size’] (int) – Size of the largest cluster (absolute number of sites)
- ret[‘moments’] (1-D
numpy.ndarray
of int) – Array of size5
. Thek
-th entry is thek
-th raw moment of the (absolute) cluster size distribution, withk
ranging from0
to4
.
Raises: ValueError
– If spanning_cluster isTrue
, but graph does not contain any auxiliary nodes to detect spanning clusters.See also
numpy.random.RandomState()
,microcanonical_statistics_dtype()
Notes
Iterating through this generator is a single run of the Newman-Ziff algorithm. [12] The first iteration yields the trivial state with \(n = 0\) occupied bonds.
Spanning cluster
Raw moments of the cluster size distribution
References
[12] (1, 2) Newman, M. E. J. & Ziff, R. M. Fast monte carlo algorithm for site or bond percolation. Physical Review E 64, 016706+ (2001), doi:10.1103/physreve.64.016706. [13] Stauffer, D. & Aharony, A. Introduction to Percolation Theory (Taylor & Francis, London, 1994), second edn. [14] Binder, K. & Heermann, D. W. Monte Carlo Simulation in Statistical Physics (Springer, Berlin, Heidelberg, 2010), doi:10.1007/978-3-642-03163-2.
-
percolate.hpc.
canonical_averages_dtype
(spanning_cluster=True)[source]¶ The NumPy Structured Array type for canonical averages over several runs
Helper function
Parameters: spanning_cluster (bool, optional) – Whether to detect a spanning cluster or not. Defaults to True
.Returns: ret – A list of tuples of field names and data types to be used as dtype
argument in numpy ndarray constructorsReturn type: list of pairs of str See also
http()
- //docs.scipy.org/doc/numpy/user/basics.rec.html
canonical_statistics_dtype()
,finalized_canonical_averages_dtype()
-
percolate.hpc.
canonical_statistics_dtype
(spanning_cluster=True)[source]¶ The NumPy Structured Array type for canonical statistics
Helper function
Parameters: spanning_cluster (bool, optional) – Whether to detect a spanning cluster or not. Defaults to True
.Returns: ret – A list of tuples of field names and data types to be used as dtype
argument in numpy ndarray constructorsReturn type: list of pairs of str See also
http()
- //docs.scipy.org/doc/numpy/user/basics.rec.html
microcanoncial_statistics_dtype()
,canonical_averages_dtype()
-
percolate.hpc.
finalize_canonical_averages
(number_of_nodes, ps, canonical_averages, alpha)[source]¶ Finalize canonical averages
-
percolate.hpc.
finalized_canonical_averages_dtype
(spanning_cluster=True)[source]¶ The NumPy Structured Array type for finalized canonical averages over several runs
Helper function
Parameters: spanning_cluster (bool, optional) – Whether to detect a spanning cluster or not. Defaults to True
.Returns: ret – A list of tuples of field names and data types to be used as dtype
argument in numpy ndarray constructorsReturn type: list of pairs of str
-
percolate.hpc.
microcanonical_statistics_dtype
(spanning_cluster=True)[source]¶ Return the numpy structured array data type for sample states
Helper function
Parameters: spanning_cluster (bool, optional) – Whether to detect a spanning cluster or not. Defaults to True
.Returns: ret – A list of tuples of field names and data types to be used as dtype
argument in numpy ndarray constructorsReturn type: list of pairs of str
percolate.percolate module¶
Low-level routines to implement the Newman-Ziff algorithm
See also
percolate
- The high-level module
-
percolate.percolate.
alpha_1sigma
¶ The alpha for the 1 sigma confidence level
-
percolate.percolate.
canonical_averages
(ps, microcanonical_averages_arrays)[source]¶ Compute the canonical cluster statistics from microcanonical statistics
This is according to Newman and Ziff, Equation (2). Note that we also simply average the bounds of the confidence intervals according to this formula.
Parameters: - ps (iterable of float) – Each entry is a probability for which to form the canonical ensemble and compute the weighted statistics from the microcanonical statistics
- microcanonical_averages_arrays – Typically the output of
microcanonical_averages_arrays()
Returns: - ret (dict) – Canonical ensemble cluster statistics
- ret[‘ps’] (iterable of float) – The parameter ps
- ret[‘N’] (int) – Total number of sites
- ret[‘M’] (int) – Total number of bonds
- ret[‘spanning_cluster’] (1-D
numpy.ndarray
of float) – The percolation probability: The normalized average number of runs that have a spanning cluster. - ret[‘spanning_cluster_ci’] (2-D
numpy.ndarray
of float, size 2) – The lower and upper bounds of the percolation probability. - ret[‘max_cluster_size’] (1-D
numpy.ndarray
of float) – The percolation strength: Average relative size of the largest cluster - ret[‘max_cluster_size_ci’] (2-D
numpy.ndarray
of float) – Lower and upper bounds of the normal confidence interval of the percolation strength. - ret[‘moments’] (2-D
numpy.ndarray
of float, shape (5, M + 1)) – Average raw moments of the (relative) cluster size distribution. - ret[‘moments_ci’] (3-D
numpy.ndarray
of float, shape (5, M + 1, 2)) – Lower and upper bounds of the normal confidence interval of the raw moments of the (relative) cluster size distribution.
-
percolate.percolate.
microcanonical_averages
(graph, runs=40, spanning_cluster=True, model='bond', alpha=<Mock name='mock().__rmul__()' id='139727673719832'>, copy_result=True)[source]¶ Generate successive microcanonical percolation ensemble averages
This is a generator function to successively add one edge at a time from the graph to the percolation model for a number of independent runs in parallel. At each iteration, it calculates and returns the averaged cluster statistics.
Parameters: - graph (networkx.Graph) – The substrate graph on which percolation is to take place
- runs (int, optional) – Number of independent runs.
Defaults to
40
. - spanning_cluster (bool, optional) – Defaults to
True
. - model (str, optional) –
The percolation model (either
'bond'
or'site'
). Defaults to'bond'
.Note
Other models than
'bond'
are not supported yet. - alpha (float, optional) – Significance level.
Defaults to 1 sigma of the normal distribution.
1 - alpha
is the confidence level. - copy_result (bool, optional) – Whether to return a copy or a reference to the result dictionary.
Defaults to
True
.
Yields: - ret (dict) – Cluster statistics
- ret[‘n’] (int) – Number of occupied bonds
- ret[‘N’] (int) – Total number of sites
- ret[‘M’] (int) – Total number of bonds
- ret[‘spanning_cluster’] (float) –
The average number (Binomial proportion) of runs that have a spanning
cluster.
This is the Bayesian point estimate of the posterior mean, with a
uniform prior.
Only exists if spanning_cluster is set to
True
. - ret[‘spanning_cluster_ci’] (1-D
numpy.ndarray
of float, size 2) – The lower and upper bounds of the Binomial proportion confidence interval with uniform prior. Only exists if spanning_cluster is set toTrue
. - ret[‘max_cluster_size’] (float) – Average size of the largest cluster (absolute number of sites)
- ret[‘max_cluster_size_ci’] (1-D
numpy.ndarray
of float, size 2) – Lower and upper bounds of the normal confidence interval of the average size of the largest cluster (absolute number of sites) - ret[‘moments’] (1-D
numpy.ndarray
of float, size 5) – Thek
-th entry is the averagek
-th raw moment of the (absolute) cluster size distribution, withk
ranging from0
to4
. - ret[‘moments_ci’] (2-D
numpy.ndarray
of float, shape (5,2)) –ret['moments_ci'][k]
are the lower and upper bounds of the normal confidence interval of the averagek
-th raw moment of the (absolute) cluster size distribution, withk
ranging from0
to4
.
Raises: ValueError
– If runs is not a positive integerValueError
– If alpha is not a float in the interval (0, 1)
See also
sample_states()
,percolate.percolate._microcanonical_average_spanning_cluster()
,percolate.percolate._microcanonical_average_max_cluster_size()
Notes
Iterating through this generator corresponds to several parallel runs of the Newman-Ziff algorithm. Each iteration yields a microcanonical percolation ensemble for the number \(n\) of occupied bonds. [9] The first iteration yields the trivial microcanonical percolation ensemble with \(n = 0\) occupied bonds.
Spanning cluster
See also
Raw moments of the cluster size distribution
See also
References
[9] Newman, M. E. J. & Ziff, R. M. Fast monte carlo algorithm for site or bond percolation. Physical Review E 64, 016706+ (2001), doi:10.1103/physreve.64.016706.
-
percolate.percolate.
microcanonical_averages_arrays
(microcanonical_averages)[source]¶ Compile microcanonical averages over all iteration steps into single arrays
Helper function to aggregate the microcanonical averages over all iteration steps into single arrays for further processing
Parameters: microcanonical_averages (iterable) – Typically, this is the microcanonical_averages()
generatorReturns: - ret (dict) – Aggregated cluster statistics
- ret[‘N’] (int) – Total number of sites
- ret[‘M’] (int) – Total number of bonds
- ret[‘spanning_cluster’] (1-D
numpy.ndarray
of float) – The percolation probability: The normalized average number of runs that have a spanning cluster. - ret[‘spanning_cluster_ci’] (2-D
numpy.ndarray
of float, size 2) – The lower and upper bounds of the percolation probability. - ret[‘max_cluster_size’] (1-D
numpy.ndarray
of float) – The percolation strength: Average relative size of the largest cluster - ret[‘max_cluster_size_ci’] (2-D
numpy.ndarray
of float) – Lower and upper bounds of the normal confidence interval of the percolation strength. - ret[‘moments’] (2-D
numpy.ndarray
of float, shape (5, M + 1)) – Average raw moments of the (relative) cluster size distribution. - ret[‘moments_ci’] (3-D
numpy.ndarray
of float, shape (5, M + 1, 2)) – Lower and upper bounds of the normal confidence interval of the raw moments of the (relative) cluster size distribution.
See also
-
percolate.percolate.
percolation_graph
(graph, spanning_cluster=True)[source]¶ Prepare the (internal) percolation graph from a given graph
Helper function to prepare the given graph for spanning cluster detection (if required). Basically it strips off the auxiliary nodes and edges again. It also returns fundamental graph quantitities (number of nodes and edges).
Parameters: - graph –
- spanning_cluster –
Returns: ret
Return type:
-
percolate.percolate.
sample_states
(graph, spanning_cluster=True, model='bond', copy_result=True)[source]¶ Generate successive sample states of the percolation model
This is a generator function to successively add one edge at a time from the graph to the percolation model. At each iteration, it calculates and returns the cluster statistics.
Parameters: - graph (networkx.Graph) – The substrate graph on which percolation is to take place
- spanning_cluster (bool, optional) – Whether to detect a spanning cluster or not.
Defaults to
True
. - model (str, optional) –
The percolation model (either
'bond'
or'site'
). Defaults to'bond'
.Note
Other models than
'bond'
are not supported yet. - copy_result (bool, optional) – Whether to return a copy or a reference to the result dictionary.
Defaults to
True
.
Yields: - ret (dict) – Cluster statistics
- ret[‘n’] (int) – Number of occupied bonds
- ret[‘N’] (int) – Total number of sites
- ret[‘M’] (int) – Total number of bonds
- ret[‘has_spanning_cluster’] (bool) –
True
if there is a spanning cluster,False
otherwise. Only exists if spanning_cluster argument is set toTrue
. - ret[‘max_cluster_size’] (int) – Size of the largest cluster (absolute number of sites)
- ret[‘moments’] (1-D
numpy.ndarray
of int) – Array of size5
. Thek
-th entry is thek
-th raw moment of the (absolute) cluster size distribution, withk
ranging from0
to4
.
Raises: ValueError
– If model does not equal'bond'
.ValueError
– If spanning_cluster isTrue
, but graph does not contain any auxiliary nodes to detect spanning clusters.
See also
microcanonical_averages()
- Evolves multiple sample states in parallel
Notes
Iterating through this generator is a single run of the Newman-Ziff algorithm. [2] The first iteration yields the trivial state with \(n = 0\) occupied bonds.
Spanning cluster
Raw moments of the cluster size distribution
References
[2] (1, 2) Newman, M. E. J. & Ziff, R. M. Fast monte carlo algorithm for site or bond percolation. Physical Review E 64, 016706+ (2001), doi:10.1103/physreve.64.016706. [3] Stauffer, D. & Aharony, A. Introduction to Percolation Theory (Taylor & Francis, London, 1994), second edn. [4] Binder, K. & Heermann, D. W. Monte Carlo Simulation in Statistical Physics (Springer, Berlin, Heidelberg, 2010), doi:10.1007/978-3-642-03163-2.
-
percolate.percolate.
single_run_arrays
(spanning_cluster=True, **kwargs)[source]¶ Generate statistics for a single run
This is a stand-alone helper function to evolve a single sample state (realization) and return the cluster statistics.
Parameters: - spanning_cluster (bool, optional) – Whether to detect a spanning cluster or not.
Defaults to
True
. - kwargs (keyword arguments) – Piped through to
sample_states()
Returns: - ret (dict) – Cluster statistics
- ret[‘N’] (int) – Total number of sites
- ret[‘M’] (int) – Total number of bonds
- ret[‘max_cluster_size’] (1-D
numpy.ndarray
of int, sizeret['M'] + 1
) – Array of the sizes of the largest cluster (absolute number of sites) at the respective occupation number. - ret[‘has_spanning_cluster’] (1-D
numpy.ndarray
of bool, sizeret['M'] + 1
) – Array of booleans for each occupation number. The respective entry isTrue
if there is a spanning cluster,False
otherwise. Only exists if spanning_cluster argument is set toTrue
. - ret[‘moments’] (2-D
numpy.ndarray
of int) – Array of shape(5, ret['M'] + 1)
. The(k, m)
-th entry is thek
-th raw moment of the (absolute) cluster size distribution, withk
ranging from0
to4
, at occupation numberm
.
See also
- spanning_cluster (bool, optional) – Whether to detect a spanning cluster or not.
Defaults to
-
percolate.percolate.
spanning_1d_chain
(length)[source]¶ Generate a linear chain with auxiliary nodes for spanning cluster detection
Parameters: length (int) – Number of nodes in the chain, excluding the auxiliary nodes. Returns: A linear chain graph with auxiliary nodes for spanning cluster detection Return type: networkx.Graph See also
sample_states()
- spanning cluster detection
-
percolate.percolate.
spanning_2d_grid
(length)[source]¶ Generate a square lattice with auxiliary nodes for spanning detection
Parameters: length (int) – Number of nodes in one dimension, excluding the auxiliary nodes. Returns: A square lattice graph with auxiliary nodes for spanning cluster detection Return type: networkx.Graph See also
sample_states()
- spanning cluster detection
Module contents¶
Implements the Newman-Ziff algorithm for Monte Carlo simulation of percolation
This module implements the Newman-Ziff algorithm for Monte Carlo simulation of Bernoulli percolation on arbitrary graphs.
The percolate
module provides these high-level functions from the
percolate.percolate
module:
percolate.sample_states (graph[, ...]) |
Generate successive sample states of the percolation model |
percolate.single_run_arrays ([spanning_cluster]) |
Generate statistics for a single run |
percolate.microcanonical_averages (graph[, ...]) |
Generate successive microcanonical percolation ensemble averages |
percolate.microcanonical_averages_arrays (...) |
Compile microcanonical averages over all iteration steps into single arrays |
percolate.canonical_averages (ps, ...) |
Compute the canonical cluster statistics from microcanonical statistics |
percolate.spanning_1d_chain (length) |
Generate a linear chain with auxiliary nodes for spanning cluster detection |
percolate.spanning_2d_grid (length) |
Generate a square lattice with auxiliary nodes for spanning detection |
percolate.statistics (graph, ps[, ...]) |
Helper function to compute percolation statistics |
See also
percolate.percolate
- low-level functions
Notes
Currently, the module only implements bond percolation. Spanning cluster detection is implemented, but wrapping detection is not.
The elementary unit of computation is the sample state:
This is one particular realization with a given number of edges—one member of
the microcanonical ensemble.
As Newman & Ziff suggest [1], the module evolves a sample state by
successively adding edges, in a random but predetermined order.
This is implemented as a generator function sample_states()
to iterate
over.
Each step of the iteration adds one edge.
A collection of sample states (realizations) evolved in parallel form a
microcanonical ensemble at each iteration step.
A microcanonical ensemble is hence a collection of different sample states
(realizations) but with the same number of edges (occupation number).
The microcanonical_averages()
generator function evolves a microcanonical
ensemble.
At each step, it calculates the cluster statistics over all realizations in the
ensemble.
The microcanonical_averages_arrays()
helper function collects these
statistics over all iteration steps into single numpy arrays.
Finally, the canonical_averages()
function calculates the statistics of
the canonical ensemble from the microcanonical ensembles.
References
[1] | Newman, M. E. J. & Ziff, R. M. Fast monte carlo algorithm for site or bond percolation. Physical Review E 64, 016706+ (2001), 10.1103/physreve.64.016706 |