Hoshen–Kopelman algorithm: Difference between revisions

Revision as of 21:36, 22 September 2016

Revision as of 21:40, 22 September 2016

Line 1:

{{Refimprove|date=September 2016}}

{{Machine learning bar}}

The '''Hoshen–Kopelman algorithm''' is a simple and efficient [[algorithm]] for labeling [[Cluster analysis|clusters]] on a grid. Where the grid is a regular [[network]] of cells,with the cells being either occupied or unoccupied. This algorithm is based on a well-known [[Disjoint-set data structure|union-finding algorithm]].<ref> https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf </ref>. The algorithm was originally described in by J. Hoshen and R. Kopelman in their 1976 paper <a href="[http://journals.aps.org/prb/abstract/10.1103/PhysRevB.14.3438" target="_blank">Percolation and Cluster Distribution. I. Cluster Multiple Labeling Technique and Critical Concentration Algorithm</a>].<ref>{{cite journal|url=http://link.aps.org/doi/10.1103/PhysRevB.14.3438|title=Percolation and cluster distribution. I. Cluster multiple labeling technique and critical concentration algorithm|first1=J.|last1=Hoshen|first2=R.|last2=Kopelman|date=15 October 1976|publisher=|journal=Phys. Rev. B|volume=14|issue=8|pages=3438–3445|via=APS|doi=10.1103/PhysRevB.14.3438}}</ref>

== Percolation theory ==

[[Percolation theory]] is the study of the behavior and [[statistics]] of [[Cluster|clusters]] on [[Lattice graph|lattices]]. Suppose we have a large square lattice where each cell can be occupied with the [[probability]] ''p'' and can be empty with the probability 1&nbsp;–&nbsp;''p''. Each group of neighboring occupied cells forms a cluster. Neighbors are defined as cells having a common side but not those sharing only a corner i.e. we consider 4x4 neighborhood. (top, bottom, left, right). Each occupied cell is occupied independently of the status of its neighborhood. The number of clusters, a size of each cluster and their distribution are important topics in percolation theory.

<center>

{|