C 2003 Society for Industrial and Applied Mathematics L.45.Na.2,pp.167-256 The structure and function of Complex Networks E.J. Newma Abstract. Inspired by empirical studies of networked systems such as the Internet, social networks, 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 Key words. networks, graph theory, complex systems, computer networks, social networks, random AMS subject classifications. 05C75, 05C90, 94015 PIlS0036144503424804 Contents I Introduction 1.2 Other resources 172 1.3 Outline of the review 174 2 Networks in the real world l74 2.1 Social networks 2.2 Information networks 176 2.3 Technological Networks 2.4 Biological Networks 179 3 Properties of Networks 3.1 The smal-World effect 180 3.2 Transitivity or Clustering .3 Degree Distributions 185 3.1 Scale-Free Networks 3.3.2 Maximum Degr 3.4 Network resilience 3.5 Mixing patterns Received by the editors January 20, 2003; accepted for publication (in revised form) March 17 2003: published elect May 2, 2003. This work was supported in part by the U.S. National rants DMS-0109086 and DMS-0234188 and by the James S McDonnell http://www.siam.org/journa t Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, MI 48109(mejnQumich. edu)
SIAM REVIEW c 2003 Society for Industrial and Applied Mathematics Vol. 45,No. 2,pp. 167–256 The Structure and Function of Complex Networks∗ M. E. J. Newman† Abstract. 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 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. Key words. networks, graph theory, complex systems, computer networks, social networks, random graphs, percolation theory AMS subject classifications. 05C75, 05C90, 94C15 PII. S0036144503424804 Contents. 1 Introduction 168 1.1 Types of Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 1.2 Other Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 1.3 Outline of the Review . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 2 Networks in the Real World 174 2.1 Social Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 2.2 Information Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 2.3 Technological Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 178 2.4 Biological Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 3 Properties of Networks 180 3.1 The Small-World Effect . . . . . . . . . . . . . . . . . . . . . . . . . . 180 3.2 Transitivity or Clustering . . . . . . . . . . . . . . . . . . . . . . . . . 183 3.3 Degree Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 3.3.1 Scale-Free Networks . . . . . . . . . . . . . . . . . . . . . . . . 186 3.3.2 Maximum Degree . . . . . . . . . . . . . . . . . . . . . . . . . . 188 3.4 Network Resilience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 3.5 Mixing Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 ∗Received by the editors January 20, 2003; accepted for publication (in revised form) March 17, 2003; published electronically May 2, 2003. This work was supported in part by the U.S. National Science Foundation under grants DMS-0109086 and DMS-0234188 and by the James S. McDonnell Foundation and the Santa Fe Institute. http://www.siam.org/journals/sirev/45-2/42480.html †Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, MI 48109 (mejn@umich.edu). 167
MLE.」 NEWMAN 3.6 Degree Correlations 3.7 Community Structure 3.8 Network Navigation 3.9 Other Network Properties m era 196 4.1 Poisson Random Graphs 4.2 Generalized Random graphs 4.2.1 The Configuration Mod 4.2.2 Example: Power-Law Degree Distribution 4.2.3 Directed Graphs 4.2.4 Bipartite Graphs .204 4.2.5 Degree Correlations 5 Exponential Random Graphs and Markov Graphs 206 6 The small-World model 208 6.1 Clustering Coefficient 6.2 Degree Distribution 210 6.3 Average Path Length 7 Models of network growth 212 7. 1 Prices Model 13 7.2 The Model of Barabasi and Albert 215 7. 3 Generalizations of the model of Barabasi and Albert 219 7. 4 Other Growth Models 7.5 Vertex Copying Models 8 Processes Taking Place on Networks 224 8.1 Percolation Theory and Network Resilience 8.2 Epidemiological Processes 8.2.1 The SIR model 8.2.2 The SIS Model 8. 3 Search on Networks 8.3.1 Exhaustive Network Search 8.3.2 Guided Network Search 8.3.3 Network Navigation 8.4 Phase Transitions on networks 8.5 Other Processes on Networks 9 Summary and Directions for Future Research 240 I. Introduction A network is a set of items which we will call vertices or some- times nodes, with connections between them, called edges(Figure 1.1). Systems king the form of networks(also called"graphs"in much of the mathematical lit erature)abound in the world. Examples include the Internet, the World Wide Web social networks of acquaintance or other connections between individuals, organiza tional networks and networks of business relations between companies, neural net works. metabolic networks food webs distribution networks such as blood vessels
168 M. E. J. NEWMAN 3.6Degree Correlations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 3.7 Community Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 3.8 Network Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 3.9 Other Network Properties . . . . . . . . . . . . . . . . . . . . . . . . . 196 4 Random Graphs 196 4.1 Poisson Random Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 197 4.2 Generalized Random Graphs . . . . . . . . . . . . . . . . . . . . . . . 200 4.2.1 The Configuration Model . . . . . . . . . . . . . . . . . . . . . 200 4.2.2 Example: Power-Law Degree Distribution . . . . . . . . . . . . 202 4.2.3 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 203 4.2.4 Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 204 4.2.5 Degree Correlations . . . . . . . . . . . . . . . . . . . . . . . . 205 5 Exponential Random Graphs and Markov Graphs 206 6 The Small-World Model 208 6.1 Clustering Coefficient . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 6.2 Degree Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 6.3 Average Path Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 7 Models of Network Growth 212 7.1 Price’s Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 7.2 The Model of Barab´asi and Albert . . . . . . . . . . . . . . . . . . . . 215 7.3 Generalizations of the Model of Barab´asi and Albert . . . . . . . . . . 219 7.4 Other Growth Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 7.5 Vertex Copying Models . . . . . . . . . . . . . . . . . . . . . . . . . . 223 8 Processes Taking Place on Networks 224 8.1 Percolation Theory and Network Resilience . . . . . . . . . . . . . . . 225 8.2 Epidemiological Processes . . . . . . . . . . . . . . . . . . . . . . . . . 229 8.2.1 The SIR Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 8.2.2 The SIS Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 8.3 Search on Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 8.3.1 Exhaustive Network Search . . . . . . . . . . . . . . . . . . . . 234 8.3.2 Guided Network Search . . . . . . . . . . . . . . . . . . . . . . 235 8.3.3 Network Navigation . . . . . . . . . . . . . . . . . . . . . . . . 236 8.4 Phase Transitions on Networks . . . . . . . . . . . . . . . . . . . . . . 238 8.5 Other Processes on Networks . . . . . . . . . . . . . . . . . . . . . . . 239 9 Summary and Directions for Future Research 240 1. Introduction. A network is a set of items, which we will call vertices or sometimes nodes, with connections between them, called edges (Figure 1.1). Systems taking the form of networks (also called “graphs” in much of the mathematical literature) abound in the world. Examples include the Internet, the World Wide Web, social networks of acquaintance or other connections between individuals, organizational networks and networks of business relations between companies, neural networks, metabolic networks, food webs, distribution networks such as blood vessels or
THE STRUC TURE AND FUNCTION OF COMPLEX NETWORKS vertex Fig. II A small example network with eight vertices and ten edges. postal delivery routes, networks of citations between papers, and many others(Fig- ure 1.2). This paper reviews recent(and some not-so-recent) work on the structure and function of networked systems such as these The study of networks, in the form of mathematical graph theory, is one of the fundamental pillars of discrete mathematics. Eulers celebrated 1735 solution of the Konigsberg bridge problem is often cited as the first true proof in the theory of net- works, and during the twentieth century graph theory has developed into a substantial body of knowledge Networks have also been studied extensively in the social sciences. Already in the 1930s, sociologists realized the importance of the patterns of connection between peo- ple to the understanding of the functioning of human society(Figure 1.3). Typical net work studies in sociology involve the circulation of questionnaires, asking respondents to detail their interactions with others. One can then use the responses to reconstruct a network in which vertices represent individuals and edges the interactions between them. Typical social network studies address issues of centrality(which individuals are best connected to others or have most influence) and connectivity (whether and how individuals are connected to one another through the network) Recent years, however, have witnessed a substantial new movement in network research, with the focus shifting away from the analysis of single small graphs and the properties of individual vertices or edges within such graphs to consideration of large-scale statistical properties of graphs. This new approach has been driven largely by the availability of computers and communication networks that allow us to gather and analyze data on a scale far larger than previously possible. Where studies use to look at networks of maybe tens or in extreme cases hundreds of vertices, it is not uncommon now to see networks with millions or even billions of vertices. This change of scale forces upon us a corresponding change in 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 network's connectivity if it were removed? But such a question has little meaning in most networks of a million vertices-no single vertex in such a network will have much effect at when removed. On the other hand, one could reasonably ask a question like, "What percentage of vertices need to be removed to substantially affect network connectivity in some given way? " and this type of statistical question has real meaning even in a very large network However, there is another reason why our approach to the study of networks has changed in recent years, a reason whose importance should not be underestimated although it often is. For networks of tens or hundreds of vertices, it is a relatively straightforward matter to draw a picture of the network with actual points and lines
THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS 169 edge vertex Fig. 1.1 A small example network with eight vertices and ten edges. postal delivery routes, networks of citations between papers, and many others (Figure 1.2). This paper reviews recent (and some not-so-recent) work on the structure and function of networked systems such as these. The study of networks, in the form of mathematical graph theory, is one of the fundamental pillars of discrete mathematics. Euler’s celebrated 1735 solution of the K¨onigsberg bridge problem is often cited as the first true proof in the theory of networks, and during the twentieth century graph theory has developed into a substantial body of knowledge. Networks have also been studied extensively in the social sciences. Already in the 1930s, sociologists realized the importance of the patterns of connection between people to the understanding of the functioning of human society (Figure 1.3). Typical network studies in sociology involve the circulation of questionnaires, asking respondents to detail their interactions with others. One can then use the responses to reconstruct a network in which vertices represent individuals and edges the interactions between them. Typical social network studies address issues of centrality (which individuals are best connected to others or have most influence) and connectivity (whether and how individuals are connected to one another through the network). Recent years, however, have witnessed a substantial new movement in network research, with the focus shifting away from the analysis of single small graphs and the properties of individual vertices or edges within such graphs to consideration of large-scale statistical properties of graphs. This new approach has been driven largely by the availability of computers and communication networks that allow us to gather and analyze data on a scale far larger than previously possible. Where studies used to look at networks of maybe tens or in extreme cases hundreds of vertices, it is not uncommon now to see networks with millions or even billions of vertices. This change of scale forces upon us a corresponding change in 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 network’s connectivity if it were removed?” But such a question has little meaning in most networks of a million vertices—no single vertex in such a network will have much effect at all when removed. On the other hand, one could reasonably ask a question like, “What percentage of vertices need to be removed to substantially affect network connectivity in some given way?” and this type of statistical question has real meaning even in a very large network. However, there is another reason why our approach to the study of networks has changed in recent years, a reason whose importance should not be underestimated, although it often is. For networks of tens or hundreds of vertices, it is a relatively straightforward matter to draw a picture of the network with actual points and lines
Fig. 1. 2 Three eramples of the kinds of networks that are the topic of this review. (a) A visualization of the network structure of the Internet at the level of" autonomous systems"-local groups of computers each representing hundreds or thousands of machines. Picture by Hal Burc and Bill Cheswick, courtesy of Lumeta Corporation.(b)A social network, in this case of seral contacts, redrawn from the HIv data of Potterat et aL. 341].(c)A food web of predator-prey interactions between species in a freshwater lake [271]. Picture courtesy of ichard williams and to answer specific questions about network structure by examining this picture This has been one of the primary methods of network analysts since the field be- gan(see Figure 1.3). The human eye is an analytic tool of remarkable power, and eyeballing pictures of networks is an excellent way to gain an understanding of their
170 M. E. J. NEWMAN (b) (c) (a) Fig. 1.2 Three examples of the kinds of networks that are the topic of this review. (a) A visualization of the network structure of the Internet at the level of “autonomous systems”—local groups of computers each representing hundreds or thousands of machines. Picture by Hal Burch and Bill Cheswick, courtesy of Lumeta Corporation. (b) A social network, in this case of sexual contacts, redrawn from the HIV data of Potterat et al. [341]. (c) A food webof predator-prey interactions between species in a freshwater lake [271]. Picture courtesy of Richard Williams. and to answer specific questions about network structure by examining this picture. This has been one of the primary methods of network analysts since the field began (see Figure 1.3). The human eye is an analytic tool of remarkable power, and eyeballing pictures of networks is an excellent way to gain an understanding of their
THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS 17 Fig 1.3 An early hand-drawn twork from 1934 representing friendships between school children. After Moreno Reprinted with permission from ASGPP. structure. With a network of a million or a billion vertices, however, this approach is useless.( See Figure 1.2a for an example of a network that lies at the upper limit of hat can usefully be drawn on a piece of paper or computer screen. )One simply can- ot draw a meaningful picture of a million vertices, even with modern 3D computer rendering tools, and therefore direct analysis by eye is hopeless. The recent devel- ment of statistical methods for quantifying large networks is to a large extent an attempt to find something to play the part played by the eye in the network analysis of the twentieth century. Statistical methods answer the question, "How can I tell what this network looks like, when I can't actually look at it? The body of theory that is the primary focus of this review aims to do three things. First, it aims to find and highlight statistical properties, such as path lengths and degree distributions, that characterize the structure and behavior of networked systems, and to suggest appropriate ways to measure these properties. Second, it aims to create models of networks that can help us to understand the meaning of these properties--how they came to be as they are, and how they interact with one another Third, it aims to predict what the behavior of networked systems will be on the basis of measured structural properties and the local rules governing individual vertices. How, for example, will network structure affect traffic on the Internet, or the performance of a Web search engine, or the dynamics of social or biological systems? As we will see, the scientific community has, by drawing on ideas from a broad variety of and plines, made an excellent start on the first two of these aims, the characterization modeling of network structure. Studies of the effects of structure on system behavior on the other hand are still in their infancy. It remains to be seen what the crucial theoretical developments will be in this area I.I. Types of Networks. A set of vertices joined by edges is only the simplest type of network; there are many ways in which networks may be more this(Figure 1.4). For instance, there may be more than one different type of vertex n a network, or more than one different type of edge. And vertices or edges may have a variety of properties, numerical or otherwise, associated with them. Taking the example of a social network of people, the vertices may represent people of different nationalities, locations, ages, incomes, or many other things. Edges sent animosity acquaintance, or geographical proximity. They can carry weights, representing, say
THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS 171 Fig. 1.3 An early hand-drawn social network from 1934 representing friendships between school children. After Moreno [295]. Reprinted with permission from ASGPP. structure. With a network of a million or a billion vertices, however, this approach is useless. (See Figure 1.2a for an example of a network that lies at the upper limit of what can usefully be drawn on a piece of paper or computer screen.) One simply cannot draw a meaningful picture of a million vertices, even with modern 3D computer rendering tools, and therefore direct analysis by eye is hopeless. The recent development of statistical methods for quantifying large networks is to a large extent an attempt to find something to play the part played by the eye in the network analysis of the twentieth century. Statistical methods answer the question, “How can I tell what this network looks like, when I can’t actually look at it?” The body of theory that is the primary focus of this review aims to do three things. First, it aims to find and highlight statistical properties, such as path lengths and degree distributions, that characterize the structure and behavior of networked systems, and to suggest appropriate ways to measure these properties. Second, it aims to create models of networks that can help us to understand the meaning of these properties—how they came to be as they are, and how they interact with one another. Third, it aims to predict what the behavior of networked systems will be on the basis of measured structural properties and the local rules governing individual vertices. How, for example, will network structure affect traffic on the Internet, or the performance of a Web search engine, or the dynamics of social or biological systems? As we will see, the scientific community has, by drawing on ideas from a broad variety of disciplines, made an excellent start on the first two of these aims, the characterization and modeling of network structure. Studies of the effects of structure on system behavior on the other hand are still in their infancy. It remains to be seen what the crucial theoretical developments will be in this area. 1.1. Types of Networks. A set of vertices joined by edges is only the simplest type of network; there are many ways in which networks may be more complex than this (Figure 1.4). For instance, there may be more than one different type of vertex in a network, or more than one different type of edge. And vertices or edges may have a variety of properties, numerical or otherwise, associated with them. Taking the example of a social network of people, the vertices may represent men or women, people of different nationalities, locations, ages, incomes, or many other things. Edges may represent friendship, but they could also represent animosity, or professional acquaintance, or geographical proximity. They can carry weights, representing, say