Do the links in a Facebook account with thousands of “friends” mean the same thing as those in an account with tens or even hundreds of friends? Probably not.
What happens as more and more links are made in a network of a given size? The network moves from sparsely interconnected towards fully connected. A sparsely connected network embodies a large amount of potential information (high entropy). A link in a fully connected network has no potential information (no entropy). Therefore networks that form internal connections faster than their overall growth are in danger of becoming less informative. In the worst case scenario they may become entirely connected up and lack any useful information at all.
The movement from sparse connectivity towards fully connected graphs is generally thought to be continuous over time for random networks. The paper “Explosive Percolation in Random Networks” published March 13, 2009 in Science shows that the transition can be abrupt like when water turns into ice at zero degrees centigrade.
The paper’s result is important since it suggests that networks, from ontologies to social networks, may be in danger of suddenly transitioning into a highly connected and information poor state under certain circumstances. We need to understand what these circumstances are so we may steer our networks clear of explosive transformations (phase transitions) to information poor states.