Bond Percolation in GraphLab by Danny Bickson.
From the post:
I was asked by Prof. Scott Kirkpatrick to help and implement bond percolation in GraphLab. It is an oldie but goldie problem which is closely related to the connected components problem.
Here is an explanation about bond percolation from Wikipedia:
A representative question (and the source of the name) is as follows. Assume that some liquid is poured on top of some porous material. Will the liquid be able to make its way from hole to hole and reach the bottom? This physical question is modelled mathematically as a three-dimensional network of n × n × n vertices, usually called “sites”, in which the edge or “bonds” between each two neighbors may be open (allowing the liquid through) with probability p, or closed with probability 1 – p, and they are assumed to be independent. Therefore, for a given p, what is the probability that an open path exists from the top to the bottom? The behavior for large n is of primary interest. This problem, called now bond percolation, was introduced in the mathematics literature by Broadbent & Hammersley (1957), and has been studied intensively by mathematicians and physicists since.
In social networks, Danny notes this algorithm is used to find groups of friends.
Similar mazes appear in puzzle books.
My curiosity is about finding groups of subject identity properties.
A couple of other percolation resources of interest:
Percolation Exercises by Eric Mueller.
PercoVis (Mac), visualization of percolation by Daniel B. Larremore.