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.

On Metcalfe's Law

I recently wrote an article addressing Metcalfe's Law and related analyses from Reed and Briscoe, Odlyzko, and Tilly of network value. The summary of my analysis is that a number of factors can cause real world networks to have value substantially less than n squared. One factor is convergent value distributions, where each connection does not have equal value. Instead, if the distribution of connection values from each node converges to a limit, that drives the total network value to be only of order (n), in other words, linearly proportional to the size of the network.

Another factor is limits of consumption that are intrinsic to the type of network. If each user can hit an upper bound in money or time spent extracting value from the network, then the value of the network is also just linear. The actual article was published in Business Communications Review, but is available here as a pdf.

The analysis also applies indirectly to Reed's 2^n valuation of Web 2.0 networks based on their group-forming capabilities. Briefly, while it is true that there are 2^n (2 to the nth power) subgroups of a network, it is unlikely that they are all equally valuable. This makes the total value substantially less than 2^n.