Percolation Theory and the Web

Have you ever wondered how water finds its way through a sponge down to the surface beneath the sponge? Have you ever wondered why rain droplets form paths as they flow down your windshield, rather than just drop straight to the lowest point on your vehicle?

Percolation Theory attempts to explain some aspects of these phenomena.

There are two branches of Percolation Theory: Bond Percolation and Site Percolation. Bond Percolation deals with the connections formed by edges in a matrix and Site Percolation deals with the patterns formed by connected nodes. in a matrix.

In Percolation Theory you can take any system comprised of separate but equal parts (equality being essentially identical with uniqueness) and gauge the degree of connectivity between the parts. Suppose you can map all the parts in a matrix, each part being identified by its own node. We say the system has perfect connectivity or P = 1 if you can reach any side of the matrix from any node within the matrix. That is, there is at least one pathway connecting every node to every other node.

We say the system has no connectivity or P = 0 if the nodes are all completely disconnected — that is, you cannot reach any node from any other node in the matrix. More simply and intuitively put, when you have zero connections you have no connectivity.

Percolation Theory holds that in every system there must be a threshold point, a value P_c where things change. When measured for any system, if P is less than P_c you have broken connectivity. In other words, starting with no connectivity at all, you can connect nodes at random and not create a pathway from one side of the matrix to the other as long as you have fewer then P_c connections.

Conversely, if you start with a completely connected matrix where P = 1, you can break connections randomly and as long as P remains greater than P_c you’re guaranteed at least one pathway across the matrix (every node is still somehow connected to the rest).

Percolation Theory has been used to study materials and particle physics. It has also been used to explain the Fermi Paradox (which is a faulty scientific question that asks, “If there are X space-faring, colonizing civilizations in the galaxy, why haven’t they found us yet?”).

Brief Tangent – Why is the Fermi Paradox a faulty question? Because it it presupposes that any space aliens visiting Earth would want to land in Washington, D.C. and make contact with our government. This assumption does not explain how space aliens would know where to land or why they would want to make contact. The question (the paradox) assumes that all UFO sightings are bogus.

If it’s not obvious by now, then let me say that Percolation Theory can be applied to the Web in several ways. We can use it to measure connectivity between Web documents, Web sites, and Web communities. We can use it to measure crawl pathways. We can use it to explain why search engine A is less likely to crawl and index the exact same set of documents as search engine B.

In short, Percolation Theory is the lens we must use to understand why two backlink profiles differ (or why they are essentially equal). You can easily see Percolation Theory in action on the Web by playing with tools like TouchGraph, which uses Google’s related: report to map connections between Web sites. (TouchGraph now offers reports for Amazon and Facebook, too.)

TouchGraph and similar tools provide you with a high-level view of a site’s connectivity. You cannot see a complete picture of the Web or even of the communities in which most individual sites participate but these tools provide approximations that, when compared to each other, reveal some interesting relationships. If you wonder how a site might be algorithmically classified as of “type A” versus as of “type B”, the relationships graph may provide you with some insight.

Of course, the analysis cannot be better than the data provided to it, so take all such analyses with a heavy dose of salt.

Percolation Theory can also be used to analyze social media use. For example, suppose you want to know how active I am in social media. You can set up a matrix of social media sites and plot where you find my activity. Do I appear on Sphinn, DIGG, StumbleUpon, LinkedIn, Facebook, etc.? Do my various social media profiles link to each other?

Let’s give this matrix of my social media profiles a name — let’s call it a Social Media Matrix. So the Michael Martinez Social Media Matrix can be evaluated in terms of connective saturation. That is, the more connections there are between my social profiles, the more saturated my connectivity is. Connective saturation is not necessarily a good thing. After all, a link farm displays a connective saturation value of 1 (if we look at connective saturation as a probability distribution).

In other words, we need to ask the question, “How likely is it that a set of connections between Web sites of a given class is artificial?”

Don’t fuss over what a class is. It’s just a collection of objects grouped together by arbitrary (as opposed to random) criteria. So you can define classes of Web sites all day long and measure their connectivity saturation. The more saturated a group of related sites’ connectivity is, the more likely that connectivity is artificial.

However, this is a thesis that has not been proven to hold true in all cases. For example, in a very young community where all the members know about each other, you should expect to have a connectivity saturation equal to 1 without any arbitration. Arbitration is the action of an individual (a person or an organized group). When individuals connect through mutual interest without deliberate coordination they are not being arbitrary, they are being random.

The distinction might seem very narrow on first glance but we can illustrate with some numbers. Suppose, for example, you teach a class over the Internet. Let’s say you have 30 students. There is a probability P_s that your students will gradually link to each other’s sites on their own simply because they get to know each other.

Now let’s say you have 300 students. It should be intuitively obvious that P_s is smaller for 300 students than for 30 students. Why? Well, for one thing it takes more time to index 300 Web sites and for another thing it’s not easy to get to know 300 strangers all at once.

In a natural situation, P_s decreases as the size of the class (group) increases. That means there is an inverse relationship between P_s and the group for which it is measured.

Now, let’s suppose we can compare 3 or more classes, each with about 3000 students, and we find that 1 of those classes has a higher connectivity saturation than P_s predicts there should be. That is an example of an arbitrary connectivity saturation.

It may seem like Percolation Theory offers more value to the search industry than to the SEO industry. After all, the potential benefit for Web spam analysis seems self-evident to me. Although Percolation Theory is more easily applied to infinite groups the Web itself is sufficiently large enough that a major search engine should be able to develop some interesting modeling algorithms using Percolation Theory.

On the other hand, the SEO industry can apply simplistic Percolation Theory to gauge the naturality of its linking profiles, social media connections, and Web site neighborhoods. In other words, we can develop methods (and perhaps tools) to help us measure the extent to which we are relying on any specific resources or techniques. If, for example, you follow three main practices in your optimization and you use Percolation Theory to compare your connectivity saturation values, if one of the three has a higher value than the other point then you may reasonably conclude you’re overdoing it.

It’s something to think about as we enter the new year.