Synopses & Reviews
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.
Synopsis
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.
Synopsis
"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
Synopsis
"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
Synopsis
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-Laszlo 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).
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
Chain-links, 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 world-wide web, R. Albert, H. Jeong, and A.-L. Barabási 182
Graph structure in the web, A. Broder et al. 183
On power-law relationships of the internet topology, M. Faloutsos, P. Faloutsos, and C. Faloutsos 195
Classes of small-world networks, L.A.N. Amaral, A. Scala, M. Barthélémy, and H. E. Stanley 207
The large-scale 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 applica-tions, M.E.J. Newman, S. H. Strogatz, and D. J. Watts 269
4.2 The small-world model 286
Collective dynamics of 'small-world' networks, D. J. Watts and S. H. Strogatz 301
Small-world networks: Evidence for a crossover picture, M. Barthélémy and L.A.N. Amaral 304
Comment on'Small-world networks: Evidence for crossover picture', A. Barrat, 1999 308
Scaling and percolation in the small-world network model, M.E.J. New-man and D. J. Watts 310
On the properties of small-world networks, A. Barrat and M. Weigt, 2000 321
4.3 Models of scale-free 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. Dorogov-tsev, 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 scale-free networks, K.-I. Goh, B. Kahng, and D. Kim 368
Spectra of "real-world" graphs: Beyond the semicircle law, I. J. Farkas, I. Derényi, A.-L. Barabási, and T. Vicsek 372
The degree sequence of a scale-free random graph process, B. Bol-lobás, O. Riordan, J. Spencer, and G. Tusnády 384
A model of large-scale proteome evolution, R.V. Solé, R. Pastor-Satorras, 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. Scalia-Tomba 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 scale-free networks, R. Pastor-Satorras 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. ben-Avraham, 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 power-law 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