Thursday, 14 December 2006

Power laws as emergent behavior

Power laws describe relationships with an exponential scaling effect. The party game 6 degrees of Kevin Bacon works on the basis of this principle--some actors have been in only a few movies or co-starred with only a few other actors. Others, like Kevin Bacon, have been in a lot of movies and co-starred with a lot of other actors. There are many more people with few connections, but only a few people with many connections. In fact, the distribution by number of relationships follows a power law: y=x^k.

One intriguing feature of power laws emerge automatically from random connections. Imagine a board with N nails sticking out of it and K strands of yarn ties between various pairs of nails. We can count the number of strands tied to each nail. If the pairs of nails are selected randomly, it will just happen that some nails get selected more often than others, and in fact, the number of connections to each nail follows a power law. Suppose there are 128 nails. Then perhaps 64 have just 1 connection, 32 have 2, 16 have 3, 8 have 4, 4 have 8, 2 have 16, and 1 lucky nail has 32 connections! The point is that there's nothing magical or mysterious about power scaling; it emerges naturally. It says something genuine and interesting about the sort of phenomenon you're examining, and functions as an "explanation" of sorts, but it's an unusual explanation: it's actually an equilibrium condition, an assertion that this behavior is normal and doesn't require detailed explanation.

No comments: