Physica A: Statistical Mechanics and its Applications
Extension of Hoshen–Kopelman algorithm to non-lattice environments
Introduction
The introduction of the Hoshen–Kopelman (HK) algorithm [1] in 1976 was an important breakthrough in the analysis of cluster size statistics in percolation theory. Only after the introduction of this algorithm, did Monte-Carlo simulations of very large lattices become possible [2], [3], [4]. The algorithm's single and sequential pass through the lattice linearizes the time and memory space requirement as a function of the lattice size [5]. Although the algorithm was initially applied in statistical physics, nowadays it is applied in many diverse fields [6], [7], [8], [9], [10]. The algorithm is not restricted to pure site or pure node lattices; it has been extended to lattices that consist of sites and bonds [11], [12], [13]. In the enhanced Hoshen–Kopelman (EHK) algorithm [14], the HK algorithm has been extended to determine information not only on the cluster size but also on the structure of the clusters, such as the radius of gyration, internal perimeter, or spatial moments. The EHK algorithm has been applied to large images [15], and used to calculate cluster properties and entropy in percolation models [16]. Different approaches have been proposed to parallelize the HK algorithm [17], [18], [19], [20].
The majority of the HK algorithm adaptations and implementations were for lattice environments (discrete systems). Only a few studies were devoted to discussing the HK algorithm implementation in non-lattice environments (continuous systems). In such systems, the positions of the sites are arbitrary, and not restricted to the discrete points of a regular lattice. J. Hoshen comments:1 “... The HK algorithm can also be used for a non-lattice environment, where sites are placed at random at non-lattice points, but it is more complicated...”. Gawlinski and Stanley [21] were the first to adapt the HK algorithm to handle continuum percolation by overlaying an imaginary covering mesh onto a square area. Their adaptation was implemented in other continuum percolation models on discs and spheres [22], [23]. Non-lattice environments exist not only in the percolation theory of disordered discs and spheres, but also in the networks of many interacting units that are observed in complex systems. Researchers are only now beginning to unravel the structure and dynamics of such complex networks [24].
This paper describes an extension of the HK algorithm to complex networks. Such networks can be lattices or non-lattices in two, three or higher-dimensions; they can consist of sites, bonds or both; and each site can have a different number of connecting bonds. The data structures we introduce here describe an arbitrary network. Clusters of sites, bonds, or sites-and-bonds in such a network can be labeled with our implementation of the HK algorithm.
The paper is organized as follows: First, we present the data structures that suffice to describe any network. Then, the HK algorithm implementation that uses these data structures is proposed. After that, the results of labeling a simple network consisting of sites and bonds are reported. Then, we discuss the applicability of our HK algorithm implementation to networks consisting of sites or bonds only. Finally, we apply our procedure to a complex network extracted from the 3D image of a real porous rock.
Section snippets
Data structures
Applying the HK algorithm to a non-lattice environment becomes easier if we arrange the network description in a certain format. This format should be the same for a 2D lattice, 3D lattice, and a non-lattice environment, where sites are placed at random at non-lattice points. Moreover, network traversal does not need to be sequential from one fixed direction to another, but ought be carried out from any point in the network to any other point in the network. With these two considerations in
The HK algorithm implementation
Here we implement the HK algorithm with the data structures described above. Even though an arbitrary network consists of nodes and links, we will traverse the network only by the nodes. Each node in the network is scanned based on its order in the array Node. In what follows, our implementation of the HK algorithm is described in seven steps. In each step, we record the result of the step when applied to the network shown in Fig. 1. The description of the algorithm is also translated into the
Networks consisting of nodes or links only
In networks consisting of nodes only, we can assume that all links are occupied (i.e., their LinkS entries are equal to one) and then run the algorithm described in Section 3. For the output, we read the array NodeL only. If we do not want to construct the LinksOfNode array and use the NodeNext only, minor changes in the algorithm are necessary. In Step 1, read the data Node, NodeS, and NodeNext. In Steps 2 and 3, initialize the variables NodeL, NodeLP. Then for traversing the network in Step
Application: a pore network extracted from 3D images of a porous medium
The second example uses a network, Fig. 2, that represents the void space of a real rock. The network was extracted from a 3D micro-focused X-ray CT image and represents a sample of Bentheimer sandstone.2 It consists of 3677 nodes and 8952 links. Due to the network size, we plot only the links. The network connectivity varies from zero to sixteen links (pore throats) connected to a node (a pore body).
In the network, the
Conclusions
The Hoshen–Kopelman (HK) algorithm has been extended to non-lattice environments, where network elements (sites or bonds) are positioned at random points in space. The extension has been facilitated by the use of two data structures, NodeNext and LinksOfNode, that describe the connectivity of an arbitrary network. Our extension of the HK algorithm is not restricted to a non-lattice environment, and can be applied to lattices in two, three or higher dimensions. It can also be applied to networks
References (33)
- et al.
The X-Ray tomographic microscope3-dimensional perspectives of evolving microstructures
Nucl. Instrum. Methods A
(1994) - et al.
Spatial distribution of oil after deep-fat frying of tortilla chips from a stochastic model
J. Food Eng.
(1996) - et al.
Simulation of catalyst fouling at the particle and reactor levels
Chem. Eng. Sci.
(1996) Percolation analog for a two component liquid vapor system
Chem. Phys. Lett.
(1980)On the application of the enhanced Hoshen–Kopelman algorithm for image analysis
Pattern Recogn. Lett.
(1998)- et al.
Parallelization of a cluster algorithm
Comput. Phys. Commun.
(1989) - et al.
Parallel cluster labeling for large-scale Monte-Carlo simulations
Physica A
(1995) - et al.
A direct parallel implementation of the Hoshen–Kopelman algorithm for distributed memory architectures
Comput. Phys. Commun.
(2000) - et al.
Percolation and cluster distribution I. Cluster multiple labeling technique and critical concentration algorithm
Phys. Rev. B
(1976) - et al.
Monte Carlo and series study of corrections to scaling in two-dimensional percolation
J. Phys. A
(1984)