Extension of Hoshen–Kopelman algorithm to non-lattice environments

https://doi.org/10.1016/S0378-4371(02)01586-8Get rights and content

Abstract

We extend the Hoshen–Kopelman (HK) algorithm for cluster labeling to non-lattice environments, where sites are placed at random at non-lattice points. This extension is useful for continuum systems and disordered networks. Our extension of the HK algorithm relies on several data structures that describe network connectivity regardless of its dimensionality. Just as for the classic HK algorithm on lattices, our extension is completed in a single pass through the sites of the network and cluster relabeling operates on a vector whose size is much smaller than the size of the network. Our extension of the HK algorithm works for any environment (lattice or non-lattice) of any dimensionality, type (sites, bonds or both), and with arbitrary connectivity between the sites. The proposed extension is illustrated through a simple network consisting of 16 sites and 24 bonds, and applied to a complex network extracted from a 3D micro-focused X-ray CT image of Bentheimer sandstone consisting of 3677 sites and 8952 bonds.

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 (2.5mm)3 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)

  • D.C. Rapaport

    Cluster number scaling in two-dimensional percolation

    J. Phys. A

    (1986)
  • D.C. Rapaport

    Cluster size distribution at criticality

    J. Stat. Phys.

    (1986)
  • A.V. Aho et al.

    The Design and Analysis of Computer Algorithms

    (1974)
  • F. Eddi et al.

    Transient synaptic redundancy in the developing cerebellum and isostatic random stacking of hard spheres

    Biol. Cybern.

    (1996)
  • S. Hamimov et al.

    Classification of radar signatures by autoregressive model-fitting and cluster-analysis

    IEEE Trans. Geosci. Remote Sens.

    (1989)
  • P.R.A. Campos et al.

    Cluster-size statistics of site-bond-correlated percolation models

    Phys. Rev. B

    (1997)
  • Cited by (0)

    View full text