Sunday, September 2, 2007

Linked by Albert-Laszlo Barabasi

Dr. Barabasi's book "Linked" is very readable overview of the math underlying a variety of network architectures, with many real-world examples in a variety of contexts. Briefly, three main types of networks are addressed. One, a random network, where links between nodes are created at random. Secondly, a "small-world" network, where most nodes are linked to nearby "neighbors," and a few links span across clusters. As studies by Watts and Strogatz, these types of networks lead to six degrees of separation types of architectures, where any node can reach any other node in a small number of hops.

However, he points out that neither type of network represents the type of structure one might find in, say, a telecommunications network or the World-Wide Web. Therefore a third type of network, a "scale-free" network, comprising a few larger hubs and many smaller hubs and endpoints is introduced. His research indicates that the node degree distribution matches the power-law distribution of many real-world structures, including neural networks and the World-Wide Web.

These real-world networks arise when two phenomena are present: one, growth, and two, preferential attachment for these growing networks. Also, implicit in the model is that each new node links to a fixed number k of existing nodes. Based on these assumptions, where a new node will tend to prefer to connect to existing nodes with more connections, a scale-free architecture emerges.

Interestingly, if we define the value of a link as a constant when it exists and as zero when it doesn't exist, the overall connectivity value of any of these networks is provably linear, based on the assumptions.

No comments: