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 number n.
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 the has_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 size 5. The k-th entry is the weighted k-th raw moment of the (absolute) cluster size distribution, with k ranging from 0 to 4.

See also

bond_microcanonical_statistics(), canonical_statistics_dtype()

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'] (if percolation_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

See also

canonical_averages_dtype(), bond_canonical_statistics()

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 dtype dtype=[('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 to True.
  • 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). The k-th entry is the k-th raw moment of the (absolute) cluster size distribution, with k ranging from 0 to 4.

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 to True.
  • ret[‘max_cluster_size’] (int) – Size of the largest cluster (absolute number of sites)
  • ret[‘moments’] (1-D numpy.ndarray of int) – Array of size 5. The k-th entry is the k-th raw moment of the (absolute) cluster size distribution, with k ranging from 0 to 4.
Raises:

ValueError – If spanning_cluster is True, 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

In order to detect a spanning cluster, graph needs to contain auxiliary nodes and edges, cf. Reference [12], Figure 6. The auxiliary nodes and edges have the 'span' attribute. The value is either 0 or 1, distinguishing the two sides of the graph to span.

Raw moments of the cluster size distribution

The \(k\)-th raw moment of the (absolute) cluster size distribution is \(\sum_s' s^k N_s\), where \(s\) is the cluster size and \(N_s\) is the number of clusters of size \(s\). [13] The primed sum \(\sum'\) signifies that the largest cluster is excluded from the sum. [14]

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 constructors
Return 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 constructors
Return 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 constructors
Return type:list of pairs of str

See also

http()
//docs.scipy.org/doc/numpy/user/basics.rec.html

canonical_averages_dtype()

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 constructors
Return type:list of pairs of str

See also

http()
//docs.scipy.org/doc/numpy/user/basics.rec.html

canonical_statistics_dtype()

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.

See also

microcanonical_averages(), microcanonical_averages_arrays()

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 to True.
  • 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) – The k-th entry is the average k-th raw moment of the (absolute) cluster size distribution, with k ranging from 0 to 4.
  • 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 average k-th raw moment of the (absolute) cluster size distribution, with k ranging from 0 to 4.
Raises:
  • ValueError – If runs is not a positive integer
  • ValueError – 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

sample_states()

Raw moments of the cluster size distribution

See also

sample_states()

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() generator
Returns:
  • 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

microcanonical_averages()

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:

tuple
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 to True.
  • ret[‘max_cluster_size’] (int) – Size of the largest cluster (absolute number of sites)
  • ret[‘moments’] (1-D numpy.ndarray of int) – Array of size 5. The k-th entry is the k-th raw moment of the (absolute) cluster size distribution, with k ranging from 0 to 4.
Raises:
  • ValueError – If model does not equal 'bond'.
  • ValueError – If spanning_cluster is True, 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

In order to detect a spanning cluster, graph needs to contain auxiliary nodes and edges, cf. Reference [2], Figure 6. The auxiliary nodes and edges have the 'span' attribute. The value is either 0 or 1, distinguishing the two sides of the graph to span.

Raw moments of the cluster size distribution

The \(k\)-th raw moment of the (absolute) cluster size distribution is \(\sum_s' s^k N_s\), where \(s\) is the cluster size and \(N_s\) is the number of clusters of size \(s\). [3] The primed sum \(\sum'\) signifies that the largest cluster is excluded from the sum. [4]

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, size ret['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, size ret['M'] + 1) – Array of booleans for each occupation number. The respective entry is True if there is a spanning cluster, False otherwise. Only exists if spanning_cluster argument is set to True.
  • ret[‘moments’] (2-D numpy.ndarray of int) – Array of shape (5, ret['M'] + 1). The (k, m)-th entry is the k-th raw moment of the (absolute) cluster size distribution, with k ranging from 0 to 4, at occupation number m.

See also

sample_states()

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
percolate.percolate.statistics(graph, ps, spanning_cluster=True, model='bond', alpha=<Mock name='mock().__rmul__()' id='139727673719832'>, runs=40)[source]

Helper function to compute percolation statistics

See also

canonical_averages(), microcanonical_averages(), sample_states()

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