Jeremy Hylton : weblog : 2003-10-17 |
Friday, October 17, 2003, 9:30 a.m.
I just finished Linked: The New Science of Networks, Albert László Barabási's book about the study of networks -- specifically scale-free networks and their use in describing the Internet, biological systems, social networks, and the economy. It was an interesting but rather unsatisfying book.
The writing was at times forced. The opening chapters discuss mathematical models of random networks. Each section begins with a vignette about Paul Erdos or some other bit of history. They had some interest, but served primarily as an interruption to the main narrative. The writing is best when it sticks to the science. There's also some interesting personal background about the author's own exploration of the field, but it's not as good as Alan Guth's book The Inflationary Universe.
My main gripe, however, was never being sure whether the mathematical model of a scale-free network -- i.e. one in which power law distributions exist and there is no typical node, no characteristic scale -- was intended to be just a mathematical convenience or whether it was really a representative model of the networks in question.
Walter Willinger and others have a critique of the Barabási-Albert model that suggests my uneasiness was well-founded. The paper Scaling phenomena in the Internet: Critically examining criticality (Proceedings of the National Academy of Science, Feb. 19, 2002):
bring[s] to bear a simple validation framework that aims at testing whether a proposed model is merely evocative, in that it can reproduce the the phenomenon of interest but does not necessarily capture and incorporate the true underlying cause, or indeed explanatory, in that it also captures the causal mechanisms (why and how, in addition to what).
The Barabási-Albert model is widely known. In addition to Linked, it has been described by papers in Science and Nature. It explains the evolution of a graph relying on two simple phenomena -- incremental growth and preferential attachment. In the resulting model, the number of links per node follows a power law distribution; we expect to see many nodes with few links and a few nodes with very many links.
Willinger et al. conclude that this model is evocative:
In particular, we examine a number of recently proposed dynamical models of Internet traffic and Internet topology at the AS level that explain the entirely unexpected scaling behavior in terms of critical phenomena. In the process, we offer conclusive evidence that even though the models produce the self-similar scaling phenomena of interest, they do not explain why or how the observed phenomena arise in the Internet. Some of these criticality-based explanations can still be put to good use.
I'll have to read the article more carefully.