 Shopping Bag ( 0 items )

All (11) from $61.08

New (7) from $67.96

Used (4) from $61.08
More About This Textbook
Overview
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 fastgrowing 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.
Editorial Reviews
MAA Reviews  Sarah Boslaugh
The Structure and Dynamics of Networks performs an important service by bringing together in one volume a number of papers on network theory, and placing them in their historical context. . . . [T]he volume will serve as an introduction to the topic for the novice and a resource for the more experienced researcher.Journal of Statistical Physics  Marian Boguna
Each and every one of the featured papers represents a fundamental breakthrough, forming altogether a highly coherent body of knowledge. Professors Newman, Barabási, and Watts succeed in their selection, and at the same time add an extra value to the book with enlightening and interesting discussions. I strongly recommend this book to researchers and students of the field and, in general, to anyone who wants to enter or learn more about this exciting field of research.Applied Animal Behavior Science  Sean A. Rands
The behavioural scientist interested in the wider picture of how their work fits into the world of networks is recommended this book as a first port of call for classic citations.Journal of Statistical Physics  Marián Boguñá
Each and every one of the featured papers represents a fundamental breakthrough, forming altogether a highly coherent body of knowledge. Professors Newman, Barabási, and Watts succeed in their selection, and at the same time add an extra value to the book with enlightening and interesting discussions. I strongly recommend this book to researchers and students of the field and, in general, to anyone who wants to enter or learn more about this exciting field of research.From the Publisher
"The Structure and Dynamics of Networks performs an important service by bringing together in one volume a number of papers on network theory, and placing them in their historical context. . . . [T]he volume will serve as an introduction to the topic for the novice and a resource for the more experienced researcher."—Sarah Boslaugh, MAA Reviews"Everyone with a serious interest in the networks studies will want to read the many fine papers this major collection contains. It is to be warmly recommended as a volume deserving to become compulsory reading for all scholars (and students) interested in the field of networks."—Current Engineering Practice
"Each and every one of the featured papers represents a fundamental breakthrough, forming altogether a highly coherent body of knowledge. Professors Newman, Barabsi, and Watts succeed in their selection, and at the same time add an extra value to the book with enlightening and interesting discussions. I strongly recommend this book to researchers and students of the field and, in general, to anyone who wants to enter or learn more about this exciting field of research."—Marin Boguñ, Journal of Statistical Physics
"The behavioural scientist interested in the wider picture of how their work fits into the world of networks is recommended this book as a first port of call for classic citations."—Sean A. Rands, Applied Animal Behavior Science
MAA Reviews
The Structure and Dynamics of Networks performs an important service by bringing together in one volume a number of papers on network theory, and placing them in their historical context. . . . [T]he volume will serve as an introduction to the topic for the novice and a resource for the more experienced researcher.— Sarah Boslaugh
Current Engineering Practice
Everyone with a serious interest in the networks studies will want to read the many fine papers this major collection contains. It is to be warmly recommended as a volume deserving to become compulsory reading for all scholars (and students) interested in the field of networks.Journal of Statistical Physics
Each and every one of the featured papers represents a fundamental breakthrough, forming altogether a highly coherent body of knowledge. Professors Newman, Barabási, and Watts succeed in their selection, and at the same time add an extra value to the book with enlightening and interesting discussions. I strongly recommend this book to researchers and students of the field and, in general, to anyone who wants to enter or learn more about this exciting field of research.— Marián Boguñá
Applied Animal Behavior Science
The behavioural scientist interested in the wider picture of how their work fits into the world of networks is recommended this book as a first port of call for classic citations.— Sean A. Rands
Product Details
Related Subjects
Meet the Author
Mark Newman is Professor of Physics at the University of Michigan. AlbertLaszlo Barabasi 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 AlbertLászló Barabási Duncan J. Watts
Princeton University Press
Copyright © 2006 Princeton University PressAll right reserved.
ISBN: 0691113564
Chapter One
INTRODUCTIONNetworks 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 brainteaser 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 grapha 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 anythingpeople 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 analysisactor centrality, path lengths, cliques, connected components, and so forthwas 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 influenceinformation and disease in particularcould 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 distributionsan 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 realworld 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 realworld 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 realworld 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 networkslike transportation networks, power grids, and the physical Internetthat 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 graphtheoretic models that can account for the structural features of realworld 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, largescale 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 kindsocalled "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 socalled "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 toyet nearly 40% of these isolates are married! It is possible that these findings reveal significant patterns of behavior in contemporary social lifeperhaps 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, surveybased 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 fewprobably because other networkoriented disciplines have lacked the empirical focus of sociology. The lack of high quality, largescale 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 analysiscentrality indices, structural measures, and measures of social capitalare 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 verticesa 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 propertieslike local clustering and skewed degree distributionsthat 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.
(Continues...)
Table of Contents
Preface ix
Chapter 1. Introduction 1
1.1 A brief history of the study of networks 1
1.2 The "new" science of networks 4
1.3 Overview of the volume 8
Chapter 2: Historical developments 9
Chainlinks, F. Karinthy 21
Connectivity of random nets, R. Solomonoff and A. Rapoport 27
On the evolution of random graphs, P. Erdo os and A. Rényi 38
Contacts and influence, I. de S. Pool and M. Kochen 83
An experimental study of the small world problem, J. Travers and S. Milgram 130
Networks of scientific papers, D. J. de S. Price 149
Famous trails to Paul Erdos, R. de Castro and J. W. Grossman 155
Chapter 3: Empirical Studies 167
Diameter of the worldwide web, R. Albert, H. Jeong, and A.L. Barabási 182
Graph structure in the web, A. Broder et al. 183
On powerlaw relationships of the internet topology, M. Faloutsos, P. Faloutsos, and C. Faloutsos 195
Classes of smallworld networks, L.A.N. Amaral, A. Scala, M. Barthélémy, and H. E. Stanley 207
The largescale organization of metabolic networks, H. Jeong et al. 211
The small world of metabolism, A. Wagner and D. Fell 215
Network motifs: Simple building blocks of complex networks, R. Milo et al. 217
The structure of scientific collaboration networks, M. E. J. Newman 221
The web of human sexual contacts, F. Liljeros et al. 227
Chapter 4: Models of networks 229
4.1 Random graph models 229
A critical point for random graphs with a given degree sequence, M. Molloy and B. Reed 240
A random graph model for massive graphs, W. Aiello, F. Chung, and L. Lu 259
Random graphs with arbitrary degree distributions and their applications, M.E.J. Newman, S. H. Strogatz, and D. J. Watts 269
4.2 The smallworld model 286
Collective dynamics of 'smallworld' networks, D. J. Watts and S. H. Strogatz 301
Smallworld networks: Evidence for a crossover picture, M. Barthélémy and L.A.N. Amaral 304
Comment on'Smallworld networks: Evidence for crossover picture', A. Barrat, 1999 308
Scaling and percolation in the smallworld network model, M.E.J. Newman and D. J. Watts 310
On the properties of smallworld networks, A. Barrat and M. Weigt, 2000 321
4.3 Models of scalefree networks 335
Emergence of scaling in random networks, A.L. Barabási and R. Albert 349
Structure of growing networks with preferential linking, S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin 353
Connectivity of growing random networks, P. L. Krapivsky, S. Redner, and F. Leyvraz 357
Competition and multiscaling in evolving networks, G. Bianconi and A.L. Barabási 361
Universal behavior of load distribution in scalefree networks, K.I. Goh, B. Kahng, and D. Kim 368
Spectra of "realworld" graphs: Beyond the semicircle law, I. J. Farkas, I. Derényi, A.L. Barabási, and T. Vicsek 372
The degree sequence of a scalefree random graph process, B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády 384
A model of largescale proteome evolution, R.V. Solé, R. PastorSatorras, E. Smith, and T. B. Kepler 396
Modeling of protein interaction networks, A. Vázquez, A. Flammini, A. Maritan, and A. Vespignani 408
Chapter 5: Applications 415
5.1 Epidemics and rumors 415
5.2 Robustness of networks 424
5.3 Searching networks 428
Epidemics with two levels of mixing, F. Ball, D. Mollison, and G. ScaliaTomba 436
The effects of local spatial structure on epidemiological invasions, M. J. Keeling 480
Small world effect in an epidemiological model, M. Kuperman and G. Abramson 489
Epidemic spreading in scalefree networks, R. PastorSatorras and A. Vespignani 493
A simple model of global cascades on random networks, D. J. Watts 497
Error and attack tolerance of complex networks, R. Albert, H. Jeong, and A.L. Barabási 503
Resilience of the Internet to random breakdowns, R. Cohen, K. Erez, D. benAvraham, and S. Havlin 507
Network robustness and fragility: Percolation on random graphs, D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts 510
Authoritative sources in a hyperlinked environment, J. M. Kleinberg 514
Search in powerlaw networks, L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman 543
Navigation in a small world, J. M. Kleinberg 551
Chapter 6: Outlook 553
References 559
Index 575