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 bio- logical networks, researchers have in recent years developed a variety of techniques and models 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

I. Introduction  

A. Types of networks     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    3. Directed graphs     4. Bipartite graphs    5. Degree correlations  

V. Exponential random graphs and Markov graphs

VI. The small-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 ́asi and Albert     C. Generalizations of the Barab ́asi–Albert model     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. The SIS 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