Scale Free Networks

Networks that grow organically don't always distribute connections/node as a BellCurve?. Networks such as the Internet, the WorldWideWeb, social networks, metabolic systems, and--I suspect--wikis, grow to favor hubs, or popular nodes.

Such networks have some interesting properties. They tend to be resistant to the loss of random nodes, but not to the loss of hubs.

When I read the article in the May 2003 issue of ScientificAmerican, I realized that the Wiki follows the rules of a scale-free network, and wondered at the implications. -- RobMyers

Current events reveal the importance of this new way to categorize a network.

While listening to a program on NationalPublicRadio recently, I realized that terrorist cells probably form as scale-free networks. This should inform our anti-terrorist plans.

And then there's the power grid, which is clearly not a scale-free network, and thus vulnerable to catastrophic failures caused by the collapse of minor nodes. -- RobMyers

from email correspondence ...

An emerging area of research which might be of interest are Scale Free Networks which have some rather unique properties... both in the structure of their connectedness, and their resistance to random failure/attacks.

"Put simply, the nodes of a scale-free network aren't randomly or evenly connected. Scale-free networks include many "very connected" nodes, hubs of connectivity that shape the way the network operates. The ratio of very connected nodes to the number of nodes in the rest of the network remains constant as the network changes in size."

Scale-free networks, show almost no degradation as random nodes fail. With their very connected nodes, which are statistically unlikely to fail under random conditions, connectivity in the network is maintained. It takes quite a lot of random failure before the hubs are wiped out, and only then does the network stop working"

Scale free networks seem to apply to the structure of the Web, terrorist networks, links in scientific citations, degrees of separation from Kevin Bacon.

The key is that networks grow (they are not static) and that nodes are more likely to be attached to nodes that are already well connected.

A good source of information is http://www.nd.edu/~networks/papers.htm (the power point presentation about 3 down is good but big) and the visual companion to the book Linked is interesting...

Applying the theory to creating sustainable communities of practice - the trick would appear to be about the creation of centres (groups or individuals) who are the hubs of connectivity which link every one to every one else with just a few degrees of separation. -- RichardHelm

Richard's comment prompted me to explore the scale of this wiki. I studied the statistics of two measures, outbound link counts (unique pages cited by a page), and inbound link counts (unique pages citing a page). Here is the raw distribution data collected at the end of 2003.

A summary of my findings are as follows.

Outbound links are scale free, with a half-count of of about four. Half-count is a measure of the shape of the exponential distribution much like half-life for radioactive decay. A half-count of four says that for any number of outbound links, if we looked for pages with four more outbound links, we could expect to find half as many.
Inbound links are hyperscaled. That is, the hub pages are cited far more than would be expected by the proportions of a scale free network.

I'm surprised that the statistics are so different. I suppose it could have something to do with mental limits on the number of page names that an author might carry around. -- WardCunningham

That's no explanation. There are physical and psychological limits to how many people a person can know, but I doubt the distribution of friendships are hyperscaled as a consequence. The crucial difference is that friendship is symmetric whereas citation is not.

See WikiWordStatistics for an analysis of links to one particular WikiWord. The analysis supports Ward's conclusions.

CategoryWikiStructure