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.

Preface ixChapter 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