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. Renyi 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. Barabasi 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. Barthelemy, 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. Barthelemy 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. Barabasi 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. Barabasi 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. Derenyi, A.-L. Barabasi, and T. Vicsek 372 The degree sequence of a scale-free random graph process, B. Bol-lobas, O. Riordan, J. Spencer, and G. Tusnady 384 A model of large-scale proteome evolution, R.V. Sole, R. Pastor-Satorras, E. Smith, and T. B. Kepler 396 Modeling of protein interaction networks, A. Vazquez, 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. Barabasi 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
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
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).
"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, Barabasi, 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."--Marian Bogu?a, 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