The Structure and Dynamics of Networks / Edition 1 available in Paperback
- Pub. Date:
- Princeton University Press
From the Internet to networks of friendship, disease transmission, and even terrorism, the concept--and the reality--of networks has come to pervade modern society. But what exactly is a network? What different types of networks are there? Why are they interesting, and what can they tell us? In recent years, scientists from a range of fields--including mathematics, physics, computer science, sociology, and biology--have been pursuing these questions and building a new "science of networks." This book brings together for the first time a set of seminal articles representing research from across these disciplines. It is an ideal sourcebook for the key research in this fast-growing field.
The book is organized into four sections, each preceded by an editors' introduction summarizing its contents and general theme. The first section sets the stage by discussing some of the historical antecedents of contemporary research in the area. From there the book moves to the empirical side of the science of networks before turning to the foundational modeling ideas that have been the focus of much subsequent activity. The book closes by taking the reader to the cutting edge of network science--the relationship between network structure and system dynamics. From network robustness to the spread of disease, this section offers a potpourri of topics on this rapidly expanding frontier of the new science.
About the Author
Mark Newman is Professor of Physics at the University of Michigan. Albert-László Barabási is Emil T. Hofman Professor of Physics at the University of Notre Dame. He is the author of Linked: The New Science of Networks (Perseus Books). Duncan J. Watts is Associate Professor of Sociology at Columbia University. He is the author of Six Degrees: The Science of a Connected Age (W. W. Norton) and Small Worlds: The Dynamics of Networks Between Order and Randomness (Princeton).
Read an Excerpt
The Structure and Dynamics of Networks
By Mark Newman Albert-László Barabási Duncan J. Watts
Princeton University PressCopyright © 2006 Princeton University Press
All right reserved.
Networks are everywhere. From the Internet and its close cousin the World Wide Web to networks in economics, networks of disease transmission, and even terrorist networks, the imagery of the network pervades modern culture.
What exactly do we mean by a network? What different kinds of networks are there? And how does their presence affect the way that events play out? In the past few years, a diverse group of scientists, including mathematicians, physicists, computer scientists, sociologists, and biologists, have been actively pursuing these questions and building in the process the new research field of network theory, or the "science of networks" (Barabási 2002; Buchanan 2002; Watts 2003).
Although it is still in a period of rapid development and papers are appearing daily, a significant literature has already accumulated in this new field, and it therefore seems appropriate to summarize it in a way that is accessible to researchers unfamiliar with the topic. That is the purpose of this book. We begin by sketching in this introductory chapter a brief history of the study of networks, whose beginnings lie in mathematics and more recentlysociology. We then place the "new" science of networks in context by describing a number of features that distinguish it from what has gone before, and explain why these features are important. At the end of the chapter we give a short outline of the remainder of the book.
1.1 A BRIEF HISTORY OF THE STUDY OF NETWORKS
The study of networks has had a long history in mathematics and the sciences. In 1736, the great mathematician Leonard Euler became interested in a mathematical riddle called the Königsberg Bridge Problem. The city of Königsberg was built on the banks of the Pregel River in what was then Prussia, and on two islands that lie in midstream. Seven bridges connected the land masses, as shown in Figure 1.1. (There are many more than that today.) A popular brain-teaser of the time asked, "Does there exist any single path that crosses all seven bridges exactly once each?" Legend has it that the people of Königsberg spent many fruitless hours trying to find such a path before Euler proved the impossibility of its existence. The proof, which perhaps seems rather trivial to us now, but which apparently wasn't obvious in 1736, makes use of a graph-a mathematical object consisting of points, also called vertices or nodes, and lines, also called edges or links, which abstracts away all the details of the original problem except for its connectivity. In this graph there are four vertices representing the four land masses and seven edges joining them in the pattern of the Königsberg bridges (Figure 1.2). Then the bridge problem can be rephrased in mathematical language as the question of whether there exists any Eulerian path on the network. An Eulerian path is precisely a path that traverses each edge exactly once. Euler proved that there is not, by observing that, since any such path must both enter and leave every vertex it passes through, except the first and last, there can at most be two vertices in the network with an odd number of edges attached. In the language of graph theory, we say that there can at most be two vertices with odd degree, the degree of a vertex being the number of edges attached to it. Since all four vertices in the Königsberg graph have odd degree, the bridge problem necessarily has no solution. The problem of the existence of Eulerian paths on networks, as well as the related problem of Hamiltonian paths (paths that visit each vertex exactly once), is still of great interest to mathematicians, with new results being discovered all the time.
Many consider Euler's proof to be the first theorem in the now highly developed field of discrete mathematics known as graph theory, which in the past three centuries has become the principal mathematical language for describing the properties of networks (Harary 1995; West 1996). In its simplest form, a network is nothing more than a set of discrete elements (the vertices), and a set of connections (the edges) that link the elements, typically in a pairwise fashion. The elements and their connections can be almost anything-people and friendships (Rapoport and Horvath 1961), computers and communication lines (Faloutsos et al. 1999), chemicals and reactions (Jeong et al. 2000; Wagner and Fell 2001), scientific papers and citations (Price 1965; Redner 1998)-causing some to wonder how so broad a definition could generate anything of substantive interest. But its breadth is precisely why graph theory is so powerful. By abstracting away the details of a problem, graph theory is capable of describing the important topological features with a clarity that would be impossible were all the details retained. As a consequence, graph theory has spread well beyond its original domain of pure mathematics, especially in the past few decades, to applications in engineering (Ahuja et al. 1993), operations research (Nagurney 1993), and computer science (Lynch 1996). Nowhere, however, has graph theory found a more welcome home than in sociology.
Starting in the 1950s, in response to a growing interest in quantitative methods in sociology and anthropology, the mathematical language of graph theory was coopted by social scientists to help understand data from ethnographic studies (Wasserman and Faust 1994; Degenne and Forsé 1999; Scott 2000). Much of the terminology of social network analysis-actor centrality, path lengths, cliques, connected components, and so forth-was either borrowed directly from graph theory or else adapted from it, to address questions of status, influence, cohesiveness, social roles, and identities in social networks. Thus, in addition to its role as a language for describing abstract models, graph theory became a practical tool for the analysis of empirical data. Also starting in the 1950s, mathematicians began to think of graphs as the medium through which various modes of influence-information and disease in particular-could propagate (Solomonoff and Rapoport 1951; Erdos and Rényi 1960). Thus the structural properties of networks, especially their connectedness, became linked with behavioral characteristics like the expected size of an epidemic or the possibility of global information transmission. Associated with this trend was the notion that graphs are properly regarded as stochastic objects (Erdos and Rényi 1960 ...; Rapoport 1963), rather than purely deterministic ones, and therefore that graph properties can be thought of in terms of probability distributions-an approach that has been developed a great deal in recent years.
1.2 THE "NEW" SCIENCE OF NETWORKS
So what is there to add? If graph theory is such a powerful and general language and if so much beautiful and elegant work has already been done, what room is there for a new science of networks? We argue that the science of networks that has been taking shape over the last few years is distinguished from preceding work on networks in three important ways: (1) by focusing on the properties of real-world networks, it is concerned with empirical as well as theoretical questions; (2) it frequently takes the view that networks are not static, but evolve in time according to various dynamical rules; and (3) it aims, ultimately at least, to understand networks not just as topological objects, but also as the framework upon which distributed dynamical systems are built. As we will see in Chapter 3, elements of all these themes predate the recent explosion of interest in networks, but their synthesis into a coherent research agenda is new.
Modeling real-world networks
The first difference between the old science of networks and the new is that, social network analysis aside, traditional theories of networks have not been much concerned with the structure of naturally occurring networks. Much of graph theory qualifies as pure mathematics, and as such is concerned principally with the combinatorial properties of artificial constructs. Pure graph theory is elegant and deep, but it is not especially relevant to networks arising in the real world. Applied graph theory, as its name suggests, is more concerned with real-world network problems, but its approach is oriented toward design and engineering. By contrast, the recent work that is the topic of this book is focused on networks as they arise naturally, evolving in a manner that is typically unplanned and decentralized. Social networks and biological networks are naturally occurring networks of this kind, as are networks of information like citation networks and the World Wide Web. But the category is even broader, including networks-like transportation networks, power grids, and the physical Internet-that are intended to serve a single, coordinated purpose (transportation, power delivery, communications), but which are built over long periods of time by many independent agents and authorities. Social network analysis, for its part, is strongly empirical, but tends to be descriptive rather than constructive in nature. With the possible exception of certain types of random graph models (Holland and Leinhardt 1981; Strauss 1986; Anderson et al. 1999), network analysis in the social sciences has largely avoided modeling, preferring simply to describe the properties of networks as observed in collected data.
In contrast to traditional graph theory on the one hand, and social network analysis on the other, the work described in this book takes a view that is both theoretical and empirical. In order to develop new graph-theoretic models that can account for the structural features of real-world networks, we must first be able to say what those features are and hence empirical data are essential. But adequate theoretical models are equally essential if the significance of any particular empirical finding is to be correctly understood. Just as in traditional science, where theory and experiment continually stimulate one another, the science of networks is being built on the twin foundations of empirical observation and modeling.
That such an obvious requirement for scientific validity should have made its first appearance in the field so recently seems surprising at first, but is understandable given the historical difficulty of obtaining high quality, large-scale network data. For most of the past fifty years, the collection of network data has been confined to the field of social network analysis, in which data have to be collected through survey instruments that not only are onerous to administer, but also suffer from the inaccurate or subjective responses of subjects. People, it turns out, are not good at remembering who their friends are, and the definition of a "friend" is often quite ambiguous in the first place.
For example, the General Social Survey requests respondents to name up to six individuals with whom they discuss "important matters." The assumption is that people discuss matters that are important to them with people who are important to them, and hence that questions of this kind-so-called "name generators"-are a reliable means of identifying strong social ties. However, a recent study by Bearman and Parigi (2004) shows that when people are asked about the so-called "important matters" they are discussing, they respond with just about every topic imaginable, including many that most of us wouldn't consider important at all. Even worse, some topics are discussed with family members, some with close friends, some with coworkers, and others with complete strangers. Thus, very little can be inferred about the network ties of respondents simply by looking at the names generated by the questions in the General Social Survey. Bearman and Parigi also find that some 20% of respondents name no one at all. One might assume that these individuals are "social isolates"-people with no one to talk to-yet nearly 40% of these isolates are married! It is possible that these findings reveal significant patterns of behavior in contemporary social life-perhaps many people, even married people, really do not have anyone to talk to, or anything important to talk about. But apparently the respondent data are so contaminated by diverse interpretations of the survey instrument, along with variable recollection and even laziness, that any inferences about the corresponding social network must be regarded with skepticism.
The example of the General Social Survey is instructive because it typifies the uncertainties associated with traditional, survey-based collection of network data. If people have difficulty identifying even their closest confidants, how can one expect to extract reliable information concerning more subtle relations? And if, in response to this obstacle, survey instruments become more elaborate and specific, then as the size of the surveyed population increases, the work required of the researcher to analyze and understand the resulting volume of raw data becomes prohibitive. A better approach would be to record the activities and interactions of subjects directly, thus avoiding recall problems and allowing us to apply consistent criteria to define relationships. In the absence of accurate recording technologies, however, such direct observation methods are even more onerous than the administration of surveys.
Because of the effort involved in compiling them, social network datasets rarely document populations of more than a hundred people and almost never more than a thousand. And although other kinds of (nonsocial) networks have not suffered from the same difficulties, empirical examples prior to the last decade have been few-probably because other network-oriented disciplines have lacked the empirical focus of sociology. The lack of high quality, large-scale network data has, in turn, delayed the development of the kind of statistical models with which much of the work in this book is concerned. Such models, as we will see, can be very successful and informative when applied to large networks, but tend to break down, or simply don't address the right questions, when applied to small ones. As an example, networks of contacts between terrorists have been studied recently by, for instance, Krebs (2002), but they are poor candidates for statistical modeling because the questions of interest in these networks are not statistical in nature, focusing more on the roles of individuals and small groups within the network as a whole. The traditional tools of social network analysis-centrality indices, structural measures, and measures of social capital-are more useful in such cases.
Recent years, however, have witnessed a dramatic increase in the availability of network datasets that comprise many thousands and sometimes even millions of vertices-a consequence of the widespread availability of electronic databases and, even more important, the Internet. Not only has the Internet focused popular and scientific attention alike on the topic of networks and networked systems, but it has led to data collection methods for social and other networks that avoid many of the difficulties of traditional sociometry. Networks of scientific collaborations, for example, can now be recorded in real time through electronic databases like Medline and the Science Citation Index (Newman 2001a; Barabási et al. 2002), and even more promising sources of network data, such as email logs (Ebel et al. 2002; Guimerà et al. 2003; Tyler et al. 2003) and instant messaging services (Smith 2002; Holme et al. 2004), await further exploration. Being far larger than the datasets of traditional social network analysis, these networks are more amenable to the kinds of statistical techniques with which physicists and mathematicians are familiar. As the papers in Chapter 3 of this volume demonstrate, real networks, from citation networks and the World Wide Web to networks of biochemical reactions, display properties-like local clustering and skewed degree distributions-that were not anticipated by the idealized models of graph theory, and that have forced the development of new modeling approaches, some of which are introduced in Chapter 4.
Networks as evolving structures
A second distinguishing feature of the work described in this book is that, whereas in the past both graph theory and social network analysis have tended to treat networks as static structures, recent work has recognized that networks evolve over time (Barabási and Albert 1999; Watts 1999). Many networks are the product of dynamical processes that add or remove vertices or edges. For instance, a social network of friendships changes as individuals make and break ties with others. An individual with many acquaintances might, by virtue of being better connected or better known, be more likely to make new friends than someone else who is less well connected. Or individuals seeking friends might be more likely to meet people with whom they share a common acquaintance. The ties people make affect the form of the network, and the form of the network affects the ties people make. Social network structure therefore evolves in a historically dependent manner, in which the role of the participants and the patterns of behavior they follow cannot be ignored.
Excerpted from The Structure and Dynamics of Networks by Mark Newman Albert-László Barabási Duncan J. Watts Copyright © 2006 by Princeton University Press . Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
Chapter 1. Introduction 1
1.1 A brief history of the study of networks 11.2 The "new" science of networks 41.3 Overview of the volume 8
Chapter 2: Historical developments 9
Chain-links, F. Karinthy 21Connectivity of random nets, R. Solomonoff and A. Rapoport 27On the evolution of random graphs, P. Erdo os and A. Rényi 38Contacts and influence, I. de S. Pool and M. Kochen 83An experimental study of the small world problem, J. Travers and S. Milgram 130Networks of scientific papers, D. J. de S. Price 149Famous trails to Paul Erdos, R. de Castro and J. W. Grossman 155
Chapter 3: Empirical Studies 167
Diameter of the world-wide web, R. Albert, H. Jeong, and A.-L. Barabási 182Graph structure in the web, A. Broder et al. 183On power-law relationships of the internet topology, M. Faloutsos, P. Faloutsos, and C. Faloutsos 195Classes of small-world networks, L.A.N. Amaral, A. Scala, M. Barthélémy, and H. E. Stanley 207The large-scale organization of metabolic networks, H. Jeong et al. 211The small world of metabolism, A. Wagner and D. Fell 215Network motifs: Simple building blocks of complex networks, R. Milo et al. 217The structure of scientific collaboration networks, M. E. J. Newman 221The web of human sexual contacts, F. Liljeros et al. 227
Chapter 4: Models of networks 229
4.1 Random graph models 229A critical point for random graphs with a given degree sequence, M. Molloy and B. Reed 240A random graph model for massive graphs, W. Aiello, F. Chung, and L. Lu 259Random graphs with arbitrary degree distributions and their applica-tions, M.E.J. Newman, S. H. Strogatz, and D. J. Watts 2694.2 The small-world model 286Collective dynamics of 'small-world' networks, D. J. Watts and S. H. Strogatz 301Small-world networks: Evidence for a crossover picture, M. Barthélémy and L.A.N. Amaral 304Comment on'Small-world networks: Evidence for crossover picture', A. Barrat, 1999 308Scaling and percolation in the small-world network model, M.E.J. New-man and D. J. Watts 310On the properties of small-world networks, A. Barrat and M. Weigt, 2000 3214.3 Models of scale-free networks 335Emergence of scaling in random networks, A.-L. Barabási and R. Albert 349Structure of growing networks with preferential linking, S. N. Dorogov-tsev, J. F. F. Mendes, and A. N. Samukhin 353Connectivity of growing random networks, P. L. Krapivsky, S. Redner, and F. Leyvraz 357Competition and multiscaling in evolving networks, G. Bianconi and A.-L. Barabási 361Universal behavior of load distribution in scale-free networks, K.-I. Goh, B. Kahng, and D. Kim 368Spectra of "real-world" graphs: Beyond the semicircle law, I. J. Farkas, I. Derényi, A.-L. Barabási, and T. Vicsek 372The degree sequence of a scale-free random graph process, B. Bol-lobás, O. Riordan, J. Spencer, and G. Tusnády 384A model of large-scale proteome evolution, R.V. Solé, R. Pastor-Satorras, E. Smith, and T. B. Kepler 396Modeling of protein interaction networks, A. Vázquez, A. Flammini, A. Maritan, and A. Vespignani 408
Chapter 5: Applications 415
5.1 Epidemics and rumors 4155.2 Robustness of networks 4245.3 Searching networks 428Epidemics with two levels of mixing, F. Ball, D. Mollison, and G. Scalia-Tomba 436The effects of local spatial structure on epidemiological invasions, M. J. Keeling 480Small world effect in an epidemiological model, M. Kuperman and G. Abramson 489Epidemic spreading in scale-free networks, R. Pastor-Satorras and A. Vespignani 493A simple model of global cascades on random networks, D. J. Watts 497Error and attack tolerance of complex networks, R. Albert, H. Jeong, and A.-L. Barabási 503Resilience of the Internet to random breakdowns, R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin 507Network robustness and fragility: Percolation on random graphs, D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts 510Authoritative sources in a hyperlinked environment, J. M. Kleinberg 514Search in power-law networks, L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman 543Navigation in a small world, J. M. Kleinberg 551
Chapter 6: Outlook 553
References 559Index 575
What People are Saying About This
This excellent collection of papers will provide great one-stop shopping to those working in the evolving world of network research. It may very well become a standard resource for the growing number of courses on networks now beginning to pervade curricula. Indeed, a current difficulty in teaching such a course is that there are no good texts, and a quick look around the Web reveals that almost all these courses are taught using research papers, many of which appear in this collection.
Dan Rockmore, Dartmouth College
"I read this anthology with great interest. The editors took pains to locate (and even translate) a significant number of papers predating the recent surge of interest in the science of networks, and they do a fine job of clarifying what exactly is new (and what is not so new) in the modern approach as reflected in the vast literature on the subject. The introduction to each section nicely summarizes the main findings of the featured articles."Sergei Maslov, Brookhaven National Laboratory
I read this anthology with great interest. The editors took pains to locate (and even translate) a significant number of papers predating the recent surge of interest in the science of networks, and they do a fine job of clarifying what exactly is new (and what is not so new) in the modern approach as reflected in the vast literature on the subject. The introduction to each section nicely summarizes the main findings of the featured articles.
Sergei Maslov, Brookhaven National Laboratory