Estructura funcional

The structure and function of complex networks
M. E. J. Newman
Department of Physics, University of Michigan, Ann Arbor, MI 48109, U.S.A. and Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, U.S.A.
Inspired by empirical studies of networked systems such as the Internet, social networks, and biological networks, researchers have in recent years developed a variety of techniques andmodels to help us understand or predict the behavior of these systems. Here we review developments in this field, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.

Contents
Acknowledgments I. Introduction A. Types ofnetworks B. Other resources C. Outline of the review II. Networks in the real world A. Social networks B. Information networks C. Technological networks D. Biological networks III. Properties of networks A. The small-world effect B. Transitivity or clustering C. Degree distributions 1. Scale-free networks 2. Maximum degree D. Network resilience E. Mixing patterns F. Degree correlations G.Community structure H. Network navigation I. Other network properties IV. Random graphs A. Poisson random graphs B. Generalized random graphs 1. The configuration model 2. Example: power-law degree distribution 1 2 3 4 4 4 5 6 8 8 9 9 11 12 13 14 15 16 17 17 19 19 20 20 22 22 23

3. Directed graphs 4. Bipartite graphs 5. Degree correlations V. Exponential random graphs and Markov graphs VI. Thesmall-world model A. Clustering coefficient B. Degree distribution C. Average path length VII. Models of network growth A. Price’s model B. The model of Barab´si and Albert a C. Generalizations of the Barab´si–Albert model a D. Other growth models E. Vertex copying models VIII. Processes taking place on networks A. Percolation theory and network resilience B. Epidemiological processes 1. The SIR model 2. TheSIS model C. Search on networks 1. Exhaustive network search 2. Guided network search 3. Network navigation D. Phase transitions on networks E. Other processes on networks IX. Summary and directions for future research References

24 24 25 26 27 28 28 29 30 30 31 34 35 37 37 38 40 40 42 43 43 44 45 46 47 47 48

Acknowledgments
For useful feedback on early versions of this article, the authorwould particularly like to thank Lada Adamic, Michelle Girvan, Petter Holme, Randy LeVeque, Sidney Redner, Ricard Sol´, Steve Strogatz, Alexei V´zquez, and an anonymous referee. For e a other helpful conversations and comments about networks thanks go to Lada Adamic, L´szl´ Barab´si, Stefan Bornholdt, a o a Duncan Callaway, Peter Dodds, Jennifer Dunne, Rick Durrett, Stephanie Forrest, MichelleGirvan, Jon Kleinberg, James Moody, Cris Moore, Martina Morris, Juyong Park, Richard Rothenberg, Larry Ruzzo, Matthew Salganik, Len Sander, Steve Strogatz, Alessandro Vespignani, Chris Warren, Duncan Watts, and Barry Wellman. For providing data used in calculations and figures, thanks go to Lada Adamic, L´szl´ Barab´si, Jerry Davis, Jennifer Dunne, Ram´n Ferrer i Cancho, Paul Ginsparg, a o a o JerryGrossman, Oleg Khovayko, Hawoong Jeong, David Lipman, Neo Martinez, Stephen Muth, Richard Rothenberg, Ricard Sol´, Grigoriy Starchenko, Duncan Watts, Geoffrey West, and Janet Wiener. Figure 2a was kindly provided by Neo Martinez e and Richard Williams and Fig. 8 by James Moody. This work was supported in part by the US National Science Foundation under grants DMS–0109086 and DMS–0234188 and by theJames S. McDonnell Foundation and the Santa Fe Institute.

2
I. INTRODUCTION

The structure and function of complex networks our analytic approach. Many of the questions that might previously have been asked in studies of small networks are simply not useful in much larger networks. A social network analyst might have asked, “Which vertex in this network would prove most crucial to the...