The Structure And Dynamics of Networks

by Watts, Duncan J.; Barabasi, Albert-Laszlo

• ISBN13: 9780691113579
• ISBN10: 0691113572
• Format: Paperback
• Copyright: 2006-04-17
• Publisher: Princeton Univ Pr

Summary

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.

Author Biography

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
Introduction	1	(8)
A brief history of the study of networks	1	(3)
The ``new'' science of networks	4	(4)
Overview of the volume	8	(1)
Historical developments	9	(158)
Chain-links	21	(6)
F. Karinthy
Connectivity of random nets	27	(11)
R. Solomonoff
A. Rapoport
On the evolution of random graphs	38	(45)
P. Erdos
A. Renyi
Contacts and influence	83	(47)
I. de S. Pool
M. Kochen
An experimental study of the small world problem	130	(19)
J. Travers
S. Milgram
Networks of scientific papers	149	(6)
D. J. de S. Price
Famous trails to Paul Erdos	155	(12)
R. de Castro
J. W. Grossman
Empirical Studies	167	(62)
Diameter of the world-wide web	182	(1)
R. Albert
H. Jeong
A.-L. Barabasi
Graph structure in the web	183	(12)
A. Broder
On power-law relationships of the internet topology	195	(12)
M. Faloutsos
P. Faloutsos
C. Faloutsos
Classes of small-world networks	207	(4)
L.A.N. Amaral
A. Scala
M. Barthelemy
H. E. Stanley
The large-scale organization of metabolic networks	211	(4)
H. Jeong
The small world of metabolism	215	(2)
A. Wagner
D. Fell
Network motifs: Simple building blocks of complex networks	217	(4)
R. Milo
The structure of scientific collaboration networks	221	(6)
M. E. J. Newman
The web of human sexual contacts	227	(2)
F. Liljeros
Models of networks	229	(186)
Random graph models	229	(57)
A critical point for random graphs with a given degree sequence	240	(19)
M. Molloy
B. Reed
A random graph model for massive graphs	259	(10)
W. Aiello
F. Chung
L. Lu
Random graphs with arbitrary degree distributions and their applications	269	(17)
M.E.J. Newman
S. H. Strogatz
D. J. Watts
The small-world model	286	(49)
Collective dynamics of `small-world' networks	301	(3)
D. J. Watts
S. H. Strogatz
Small-world networks: Evidence for a crossover picture	304	(4)
M. Barthelemy
L.A.N. Amaral
Comment on `Small-world networks: Evidence for crossover picture'	308	(2)
A. Barrat
Scaling and percolation in the small-world network model	310	(11)
M. E. J. Newman
D. J. Watts
On the properties of small-world networks	321	(14)
A. Barrat
M. Weigt
Models of scale-free networks	335	(80)
Emergence of scaling in random networks	349	(4)
A.-L. Barabasi
R. Albert
Structure of growing networks with preferential linking	353	(4)
S. N. Dorogovtsev
J. F. F. Mendes
A. N. Samukhin
Connectivity of growing random networks	357	(4)
P. L. Krapivsky
S. Redner
F. Leyvraz
Competition and multiscaling in evolving networks	361	(7)
G. Bianconi
A.-L. Barabasi
Universal behavior of load distribution in scale-free networks	368	(4)
K.-I. Goh
B. Kahng
D. Kim
Spectra of ``real-world'' graphs: Beyond the semicircle law	372	(12)
I. J. Farkas
I. Derenyi
A.-L. Barabasi
T. Vicsek
The degree sequence of a scale-free random graph process	384	(12)
B. Bollobas
O. Riordan
J. Spencer
G. Tusnady
A model of large-scale proteome evolution	396	(12)
R. V. Sole
R. Pastor-Satorras
E. Smith
T. B. Kepler
Modeling of protein interaction networks	408	(7)
A. Vazquez
A. Flammini
A. Maritan
A. Vespignani
Applications	415	(138)
Epidemics and rumors	415	(9)
Robustness of networks	424	(4)
Searching networks	428	(125)
Epidemics with two levels of mixing	436	(44)
F. Ball
D. Mollison
G. Scalia Tomba
The effects of local spatial structure on epidemiological invasions	480	(9)
M. J. Keeling
Small world effect in an epidemiological model	489	(4)
M. Kuperman
G. Abramson
Epidemic spreading in scale-free networks	493	(4)
R. Pastor-Satorras
A. Vespignani
A simple model of global cascades on random networks	497	(6)
D. J. Watts
Error and attack tolerance of complex networks	503	(4)
R. Albert
H. Jeong
A.-L. Barabasi
Resilience of the Internet to random breakdowns	507	(3)
R. Cohen
K. Erez
D. ben-Avraham
S. Havlin
Network robustness and fragility: Percolation on random graphs	510	(4)
D. S. Callaway
M. E. J. Newman
S. H. Strogatz
D. J. Watts
Authoritative sources in a hyperlinked environment	514	(29)
J. M. Kleinberg
Search in power-law networks	543	(8)
L. A. Adamic
R. M. Lukose
A. R. Puniyani
B. A. Huberman
Navigation in a small world	551	(2)
J. M. Kleinberg
Outlook	553	(6)
References	559	(16)
Index	575