Linked: The New Science of Networks
Albert-Lázló Barabási
Cambridge, MA: Perseus Publishing
2002
Cloth: ISBN 0-738-20667-9
Order this book
Nexus: Small Worlds and the Groundbreaking Science of Networks
Mark Buchanan
New York, NY: W. W. Norton
2002
Cloth: ISBN 0-393-04153-0
Order this book
Reviewed by
Frédéric
Amblard
Laboratory of
Engineering for Complex Systems (LISC), Cemagref,
Clermont-Ferrand, France.
The
Not-So-New Science of Networks ...From the day Watts published his book Small Worlds in 1999, or perhaps after his article in Nature (Watts and Strogatz 1998), a huge number of other publications arose, particularly in physics but also in many other fields from epidemiology to ecology. At the time, if you wanted your publication to be accepted, no matter what the subject, the two magic words "Small Worlds" seemed to open doors at many journals and conferences. Watts's book is very interesting as it demonstrates in several empirical data sets (the neural network of C. Elegans, the power grid of the Western States) the signature of a power law in the distribution for the degrees of nodes. The book also proposes several algorithms to reproduce the so-called "Small Worlds" graphs. Moreover, despite the absence of more formal proofs which he published a few years later (Watts et al. 2002), he initiated a considerable research programme within the physics community. First of all, many other data sets could be tested to see whether or not they had the Small Worlds property. This systematic retesting of pre-existing data on networks recalls what happened after Zipf's work on the power law or Mandelbrot's development of fractals. In addition, simple explanations of such a widespread property were lacking. I think it was at this stage (as indicated by the publications on his web page) that the physicist Albert-Lázló Barabási started to work on networks. First of all, while verifying the effectiveness of such a power law on several data sets - the World Wide Web (Albert et al. 1999), metabolic networks (Jeong et al. 2000), scientific collaboration networks (Barabási et al. 2002) and food webs in ecology (Williams et al. 2002) - he then proposes models for what seems to be a universal law of organisation based on the notion of preferential attachment (Bianconi and Barabási 2001). Many subsequent works (like Amaral et al. 2000; Dorogovtsev and Mendes 2000; Pastor-Satorras and Vespignani 2001; Liljeros et al. 2001) have been based on the study of these complex networks in different areas and applied or extended Barabási's insights. According to Barabási and Buchanan, we are actually facing a paradigm shift (Kuhn 1962) in all fields of science. However, as Gad Yair (senior lecturer at the Hebrew University of Jerusalem) observed on the socnet list when talking about these books: "Less satisfactory was the ignorance of both writers of the more general collective contribution of sociologists (other than Granovetter) to the science of networks. Many more studies, measures, and rationales have been developed in network paradigms and social capital theories which are simply absent from the reviews in these books. Though we can trust these authors to know physics better than sociology, they might reinvent some of our taken-for-granted intuitions". We also have to note that the whole scientific community does not support these findings and some objections have arisen, especially concerning results by Barabási's team about the structure of the World Wide Web. These objections (for instance Adamic and Huberman 2000 which Barabási fairly draws attention to on his own web page) indicate that the Internet may be a far more complex system than that which Barabási tends to present.
I will begin by presenting a brief individual review of each book. Then I will comment generally on the complex networks approach taken by these three books but also endorsed by much other research. I will conclude with a short comparison of the different contributions that, I hope, may help the reader to find his way through this literature.
Small Worlds: The Dynamics of Networks between Order and
Randomness
Duncan J. Watts, the author of Small Worlds: The Dynamics of Networks between Order and Randomness, is assistant professor of sociology at Columbia University. He completed this book at the end of his PhD studies. Although it seems preliminary and his insights have been greatly enriched by his subsequent research, this book is still considered as one of the first steps towards the study of complex networks. The content is very straightforward. Watts starts by explaining his motivations for studying the problem of Small Worlds. This wasn't the subject he had originally picked as he had planned to work on cricket synchronisation. Curiously, Barab´si also carried out some related work on clapping synchronisation (Neda et al. 2000). Watts then refers to the legendary work of Milgram (1967) concerning the "six degrees of separation" experiment. (I won't go into this as it is so well known and since the experiment is described in full in all three books.) He then proposes three interesting models to generate graphs that display such properties as having a diameter that doesn't depend (too much) on the network size (as is the case for random networks but not for regular networks) but that also have a high clustering degree (conversely a property of regular and not random graphs). His algorithms enable us to generate these Small Worlds in which (if each node corresponds to an individual) we can observe communities strongly linked by internal connections and relative proximity between each pair of individuals within the population. After his propositions about generative mechanisms for Small World graphs, which could be regarded as having (for the moment) no connections with real systems, Watts presents investigations of some real networks such as the visual neural network of C. Elegans and the power grid of the Western States. It appears that if we evaluate the general properties of these networks, the examples he proposes have more or less the same properties as the Small World graphs.
As presented above, this book has had a huge impact on the community as it offers a problem that is both intriguing and well-defined. There is also clearly a lot more work to do in the area.
After this book, Watts did part of his postdoctoral studies at the Santa Fe Institute where he worked with Mark Newmann towards a better formalisation of Small World graphs (Watts et al. 2002). After the publications of two further books on the subject, Watts now seems a little bit old-fashioned. In fact, it is probably to overcome some limitations of his preliminary work that he has just finished a new book called Six Degrees: The Science of a Connected Age published by Norton and available in February 2003.
Linked: The New Science of Networks
The author of this book Albert-Lászl&oacaute; Barabási is the Emil T. Hofman Professor of Physics at the University of Notre Dame, where he teaches and directs research on complex networks. His seminal and varied contributions, described in his book, have been featured and acclaimed in the media, including Nature (cover story), Science, Science News, The New York Times, USA Today, The Washington Post, American Scientist, Discover, Business Week, National Geographic, The Chronicle of Higher Education and New Scientist. He has also been interviewed by BBC Radio, NPR, CBS, NBC, ABC, CNN and many other media outlets.
The book itself is simply an example to each one of us. Its style and organisation are straightforward. Barabási articulates a series of anecdotes some of which come from biographical sketches of Euler and Erdös (the two mathematicians who made graph theory what it is now or rather what it was before the intervention of Barabási and his team) and some of which are provided by his own work. What is quite admirable is the way he puts his own work into perspective with other famous contributions. This shows a great scientific culture. To put it shortly, this book is a must.
To describe the content of the book in an anecdotal way Barabási begins with a cocktail party to illustrate a who-knows-who social network that could exemplify a general graph theoretic perspective. Then, using biographies of Euler and Erdös he takes us through the scientific history and development of graph theory on which some sociologists in the late 60s and early 70s built ideas about how social networks might function. The phrase "six degrees of separation" came out of their work. Barabási begins by amusing readers with the example that helped boost this phrase into general circulation - a web site that calculates the movie-credit connections between Kevin Bacon and any other Hollywood actor. Then he shifts to his own fascinating studies of the World Wide Web. His research group showed that its domination by hub sites like Hotmail or Yahoo adheres to a graphical relation called the power law. Limning this property in diverse contexts such as Vernon Jordan's links among corporate boards, Barabási imparts the central concepts of networks while maintaining his intention to use approachable examples from everyday life. Moreover, the particularly impressive part of this presentation is that his theoretical work, the development of models taking into account preferential attachment (and dynamics on this attachment) as well as aging and other factors, is based strongly on several well-defined empirical studies in different domains: the World Wide Web, metabolic networks and AIDS virus spread for example. The only real criticism of the book is that it doesn't go very deep into his work. As far as I remember, there are no equations or algorithms presented. However, the references given in footnotes enable the curious reader to get more information easily and freely for instance through his web site or other preprint databases. The only other criticism of this work could be a tendency to present it in a partial way, i.e. as a physicist interested through his work in many diverse areas but forgetting most of the time what professionals in these domains may have to say about networks or his findings.
Nexus: Small Worlds and the Groundbreaking Science of
Networks
Mark Buchanan, the author of this book, is a scientific writer and holds a PhD in physics. He has been an editor at Nature and New Scientist and authored a previous book Ubiquity: The Science of History ... or Why the World is Simpler Than We Think. Before giving my opinion of this book, I have to say that I read Barabási's Linked before Buchanan's Nexus. As the two books largely overlap, the two reviews are not totally independent from one another.
In any event Nexus is an engagingly written book. It begins with the seminal Milgram experiment in the field of social networks. Buchanan then offers a very readable account of the rudiments of graph theory. He then draws on a variety of sources from his experience as an editor for Nature to present some applications of the Small World phenomenon. Compared to Barabási he delivers a nice and original chapter on the brain and neural networks. After a more standard descriptive section on Internet networks the reader gains a perspective on a variety of phenomena involving fractals, self-similarity and power laws along with their application to scientific phenomena like landscape accidents and river formation. Buchanan then makes a fair presentation of Barabási's work on scale-free networks (given that they might be seen as "competitors" for a "best book on complex networks" award). Here Buchanan gets a little carried away when he concludes that Small Worlds "work magic" and are essential to the "fabric of life" ignoring sometimes contradictory scientific evidence. Beyond simply presenting clear accounts of the work of other scientists, Buchanan's particular contribution comes from his reflections about the interest of complex networks as a tool to be added to the existing toolkit for complex systems. His thoughts on the processes at work in the formation of these complex networks are also inspiring. The book, which is indeed worth a reading, is an effective piece of scientific journalism which gives an external view of recent developments in complex systems and makes a wider audience think about their potential uses.
What About This New Science of Networks?As pointed out by Prabhakar Raghavan, consulting professor of Computer Science at Stanford, in his review of Buchanan's Nexus, three kinds of evidence should have been distinguished: mathematically proven facts, empirical observations and simulations on computer-generated networks. This remark is generally valid as all three books have the tendency to present complex networks or Small Worlds as things that "work magic" (to use Buchanan's words) and that don't need additional explanation. But this might be seen as an easy criticism since the field is currently working on building mechanisms to explain these phenomena. To caricature somewhat, research in complex networks seems to follow this scheme: scientists in a given discipline (be it computer science, biology, ecology or sociology) are faced with a problem and a physicist proposes a complex network explanation for this problem, ignoring what the scientists from the discipline concerned have to say before, during or after this explanation. In some cases (the observation of power laws for instance) there are a number of alternative explanations in the literature, some of which are more compelling than others from the standpoint of human behaviour. In this context, the fact that the authors don't mention the contribution of sociology to the "science of networks" is disappointing. Many empirical studies (in Social Networks or JoSS for instance), measures (Wassermann and Faust 1994) and rationales (Coleman 1990) have been developed in network research and social capital theory but these are totally absent from the books reviewed. Although it could be argued that the authors are physicists rather than sociologists, it is not at all clear that there is no necessity to take account of the concepts and approaches developed in sociology.
In sum then, it is misleading to label any of these books as presenting "the science of networks". Any claim to effective coverage of this wide discipline would need to include far more consideration of graph theory, queuing theory and social network analysis.
ComparisonI believe that what a reviewer should aim to do is help potential readers in their choice, especially in this particular case. In my opinion, the choice depends on the time you want to dedicate to the task. If you only have time for one book, I would probably advise you to go for Barabási's Linked. But if you have more time and want to know more about complex networks, reading Nexus is anything but a waste of your time. I am still quite doubtful about the value of reading Small Worlds, as Watts's new book Six Degrees: The Science of a Connected Age appears to be more accomplished and thus seems likely to be a good book on the subject. However, as the field is growing quickly, it is probably always worth giving serious consideration to the latest published book at any point in time.
ReferencesADAMIC L. and B. A. Huberman 2000. Power law distribution of the World Wide Web. Science, 287:2115.
AMARAL N., A. Scala, M. Barthélémy and H. E. Stanley 2000. Classes of small world networks. Proceedings of the National Academy of Sciences, 97:11149-11152.
ALBERT R., H. Jeong and A.-L. Barabási 1999. Diameter of the World Wide Web. Nature, 401:130-131.
BARABÁSI A.-L., H. Jeong, R. Ravasz, Z. Néda, T. Vicsek and A. Schubert 2002. On the topology of the scientific collaboration networks. Physica A, 311:590-614.
BIANCONI G. and A.-L. Barabási 2001. Competition and multi-scaling in evolving networks. Europhysics Letters, 54:436-442.
COLEMAN J. S. 1990. Foundations of Social Theory. Belknap/Harvard University Press, Cambridge, MA.
DOROGOVTSEV S. N. and J. F. F. Mendes 2000. Evolution of reference networks with aging. Physical Review E, 62:1842.
JEONG H., B. Tombor, R. Albert, Z. N. Oltvai and A.-L. Barabási 2000. The large-scale organisation of metabolic networks. Nature, 407:651-654.
KUHN T. 1962. The Structure of Scientific Revolutions. University of Chicago Press, Chicago, IL.
LILJEROS F., C. R. Edling, L. A. Nunes Amaral, H. E. Stanley and Y. Aberg 2001. The web of human sexual contacts. Nature, 411:907-908.
MILGRAM S. 1967. The small world problem. Psychology Today, 2:60-67.
NEDA Z., E. Ravasz, Y. Brechet, T. Vicsek and A.-L. Barabási 2000. Self-organising processes: The sound of many hands clapping. Nature, 403:849-850.
PASTOR-SATORRAS R. and A. Vespignani 2001. Epidemic spreading in scale-free networks. Physica Review Letters, 86:3200-3203.
WASSERMAN S. and K. Faust 1994. Social Network Analysis: Methods and Application. Cambridge University Press, Cambridge.
WATTS D. J. and S. H. Strogatz 1998. Collective dynamics of 'small-world' networks. Nature, 393:440-442.
WATTS D. J., P. S. Dodds and M. Newmann 2002. Identity and search in social networks. Science, 296:1303-1305.
WILLIAMS R. J., E. L. Berlow, J. A. Dunne, A.-L. Barabási and N. D. Martinez 2002. Two degrees of separation in complex food webs. Proceedings of the National Academy of Sciences, 99:12913-12916.
Return to Contents
of this issue
© Copyright Journal of Artificial Societies and Social Simulation, 2003