Scale-Free Networks


Today Scoble writes about a conversation he had with Steven Levy about being on the A-List. Robert says he consciously combs through less read bloggers to find things not seen before. This of course, brings to mind Clay Shirky's piece on power laws. That, reminded me that I wanted to post something about Peter Denning's latest column in Communications of the ACM on Network Laws (PDF).

Denning, as usual, gives a wonderfully cogent tutorial on power laws and talks about scale-free networks. Scale-free networks are networks that have power-law connection statistics. Scale-free networks have two properties:

  • Growth: new nodes appear at random times
  • Preferential attachment: a new node connects to an existing node with probability proportional to the number of connections already at that node.

Note that I'm paraphrasing rather than quoting because the PDF won't let me grabs snippets conviniently.

The bottom line is that the power-law distribution is self-reinforcing in scale-free networks. Denning mentions that viruses spread quickly in scale-free networks. The same is true of ideas. Other important thoughts: failure of a random node in a scale-free network has negligible effect on connectivity, but failure of a hub does significant damage.

Large social networks are scale-free. To spread an innovative idea, bring the hubs (think Scoble, Doc, or Winer here) on board. To stop an innovative idea, convince the hubs its of no value. The business of spreading innovations is a skill that improves over time.

Denning also talks about the idea that many of the biggest innovations of our time like the Internet, Web, and Linux were built by consortia. Viewed from the perspective of the network a consortium is a consciously built hub in the scale-free social network.