MLE.」 NEWMAN 4 of verter and a single type of edge;(b)a network with a number of discrete verter and edge types;(c) a network with varying verter and edge weights;(d)a directed network in which each edge has a direction how well two people know each other. They can also be directed, pointing in only one direction. Graphs composed of directed edges are themselves called directed graphs or sometimes digraphs, for short. a graph representing telephone calls or email messages between individuals would be directed, since each message only goes in one direction Directed graphs can be either cyclic, meaning they contain closed loops of edges, or acyclic, meaning they do not. Some networks, such as food webs, are approximately but not perfectly acyclic One can also have hyperedges--edges that join more than two vertices together Graphs containing such edges are called hypergraphs. Hyperedges could be used to indicate family ties in a social network for example--n individuals connected to each other by virtue of belonging to the same immediate family could be represented by an n-edge joining them. Graphs may also be naturally partitioned in various ways. We will see a number of examples in this review of bipartite graphs: graphs that contain vertices of two distinct types, with edges running only between unlike types. So-called affiliation networks in which people are joined together by common membership of groups take this form, the two types of vertices representing the people and the groups Graphs may also evolve over time, with vertices or edges appearing or disappearing or values defined on those vertices and edges changing. And there are many other levels of sophistication one can add. The study of networks is by no means a complete ience yet, and many of the possibilities have yet to be explored in depth, but we will see examples of at least some of the variations described here in the work reviewed in The jargon of the study of networks is unfortunately confused by differing usages among investigators from different fields. To avoid (or at least reduce) confusion, we give in Box 1 a short glossary of terms as they are used in this paper. 1. 2. Other Resources. A number of other reviews of this area have appeared recently, which the reader may wish to consult. Albert and Barabasi [13 and Doro- govtsev and Mendes [120 have given extensive pedagogical reviews focusing on the physics literature. Both devote the larger part of their attention to the models of
172 M. E. J. NEWMAN (c) (b) (d) (a) Fig. 1.4 Examples of various types of networks: (a) an undirected network with only a single type of vertex and a single type of edge; (b) a network with a number of discrete vertex and edge types; (c) a network with varying vertex and edge weights; (d) a directed network in which each edge has a direction. how well two people know each other. They can also be directed, pointing in only one direction. Graphs composed of directed edges are themselves called directed graphs or sometimes digraphs, for short. A graph representing telephone calls or email messages between individuals would be directed, since each message only goes in one direction. Directed graphs can be either cyclic, meaning they contain closed loops of edges, or acyclic, meaning they do not. Some networks, such as food webs, are approximately but not perfectly acyclic. One can also have hyperedges—edges that join more than two vertices together. Graphs containing such edges are called hypergraphs. Hyperedges could be used to indicate family ties in a social network for example—n individuals connected to each other by virtue of belonging to the same immediate family could be represented by an n-edge joining them. Graphs may also be naturally partitioned in various ways. We will see a number of examples in this review of bipartite graphs: graphs that contain vertices of two distinct types, with edges running only between unlike types. So-called affiliation networks in which people are joined together by common membership of groups take this form, the two types of vertices representing the people and the groups. Graphs may also evolve over time, with vertices or edges appearing or disappearing, or values defined on those vertices and edges changing. And there are many other levels of sophistication one can add. The study of networks is by no means a complete science yet, and many of the possibilities have yet to be explored in depth, but we will see examples of at least some of the variations described here in the work reviewed in this paper. The jargon of the study of networks is unfortunately confused by differing usages among investigators from different fields. To avoid (or at least reduce) confusion, we give in Box 1 a short glossary of terms as they are used in this paper. 1.2. Other Resources. A number of other reviews of this area have appeared recently, which the reader may wish to consult. Albert and Barab´asi [13] and Dorogovtsev and Mendes [120] have given extensive pedagogical reviews focusing on the physics literature. Both devote the larger part of their attention to the models of
THE STRUC TURE AND FUNCTION OF COMPLEX NETWORKS 173 letter(pl. vertices): The fundamental unit of a network, also called a site (physics), a node(computer science), or an actor(sociology) Edge: The line connecting two vertices. Also called a bond (physics), a link (computer science), or a tie(sociology) Directed/undirected: An edge is directed if it runs in only one direction(such as a one-way road between two points), and undirected if it runs in both directions Directed edges, which are sometimes called arcs, can be thought of as sporting arrows indicating their orientation. A graph is directed if all of its edges are directed. An undirected graph can be represented by a directed one having two edges between each pair of connected vertices, one in each direction Degree: The number of edges connected to a vertex. Note that the degree is not necessarily equal to the number of vertices adjacent to a vertex, since there may be more than one edge between any two vertices. In a few recent articles, the degree is referred to as the "connectivity"of a vertex, but we avoid this usage because the word connectivity already has another meaning in graph theory. A directed graph has both an in-degree and an out-degree for each vertex, which are the numbers of Component: The component to which a vertex belongs is that set of vertices that can be reached from it by paths running along edges of the graph. In a directed graph a vertex has both an in-component and an out-component, which are the sets of vertices from which the vertex can be reached and which can be reached from it Geodesic path: A geodesic path is the shortest path through the network from one vertex to another. Note that there may be and often is more than one geodesic path between two vertices. Diameter: The diameter of a network is the length (in number of edges)of the longest geodesic path between any two vertices. A few authors have also used this term to mean the average geodesic distance in a graph, although strictly the two quantities are quite distinct. Box I A short glossary of terms. growing graphs that we describe in section 7. Shorter reviews taking other viewpoints have been given by Newman 308 and Hayes [188, 189, who both concentrate on the so-called small-world models( see section 6), and by Strogatz 386, who includes an interesting discussion of the behavior of dynamical systems on networks A number of books also make worthwhile reading Dorogovtsev and Mendes [122] have expanded their above-mentioned review into a book, which again focuses on models of growing graphs. The edited volumes by Bornholdt and Schuster 70 and by Pastor-Satorras and Rubi 329 both contain contributed essays on various topics by leading researchers. Detailed treatments of many of the topics covered in the esent work can be found there. The book by Newman, Barabasi, and Watts 319 is a collection of previously published papers and also contains some review material by the editors Three popular books on the subject of networks merit a mention. Barabasi's Linked 31 gives a personal account of recent developments in the study of net works, focusing particularly on Barabasi's work on scale-free networks. Watts's Sir Degrees [413 gives a sociologist's view, partly historical, of discoveries old and new Buchanan's Nerus [76 gives an entertaining portrait of the field from the point of view of a science journalist
THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS 173 Vertex (pl. vertices): The fundamental unit of a network, also called a site (physics), a node (computer science), or an actor (sociology). Edge: The line connecting two vertices. Also called a bond (physics), a link (computer science), or a tie (sociology). Directed/undirected: An edge is directed if it runs in only one direction (such as a one-way road between two points), and undirected if it runs in both directions. Directed edges, which are sometimes called arcs, can be thought of as sporting arrows indicating their orientation. A graph is directed if all of its edges are directed. An undirected graph can be represented by a directed one having two edges between each pair of connected vertices, one in each direction. Degree: The number of edges connected to a vertex. Note that the degree is not necessarily equal to the number of vertices adjacent to a vertex, since there may be more than one edge between any two vertices. In a few recent articles, the degree is referred to as the “connectivity” of a vertex, but we avoid this usage because the word connectivity already has another meaning in graph theory. A directed graph has both an in-degree and an out-degree for each vertex, which are the numbers of incoming and outgoing edges respectively. Component: The component to which a vertex belongs is that set of vertices that can be reached from it by paths running along edges of the graph. In a directed graph a vertex has both an in-component and an out-component, which are the sets of vertices from which the vertex can be reached and which can be reached from it. Geodesic path: A geodesic path is the shortest path through the network from one vertex to another. Note that there may be and often is more than one geodesic path between two vertices. Diameter: The diameter of a network is the length (in number of edges) of the longest geodesic path between any two vertices. A few authors have also used this term to mean the average geodesic distance in a graph, although strictly the two quantities are quite distinct. Box 1 A short glossary of terms. growing graphs that we describe in section 7. Shorter reviews taking other viewpoints have been given by Newman [308] and Hayes [188, 189], who both concentrate on the so-called small-world models (see section 6), and by Strogatz [386], who includes an interesting discussion of the behavior of dynamical systems on networks. A number of books also make worthwhile reading. Dorogovtsev and Mendes [122] have expanded their above-mentioned review into a book, which again focuses on models of growing graphs. The edited volumes by Bornholdt and Schuster [70] and by Pastor-Satorras and Rubi [329] both contain contributed essays on various topics by leading researchers. Detailed treatments of many of the topics covered in the present work can be found there. The book by Newman, Barab´asi, and Watts [319] is a collection of previously published papers and also contains some review material by the editors. Three popular books on the subject of networks merit a mention. Barab´asi’s Linked [31] gives a personal account of recent developments in the study of networks, focusing particularly on Barab´asi’s work on scale-free networks. Watts’s Six Degrees [413] gives a sociologist’s view, partly historical, of discoveries old and new. Buchanan’s Nexus [76] gives an entertaining portrait of the field from the point of view of a science journalist
MLE.」 NEWMAN Farther afield, there are a variety of books on the study of networks in particular fields. Within graph theory the books by Harary [187] and by Bollobas [62 are widely cited as are, among social network theorists, the books by Wasserman and Faust [408 and by Scott [362. The book by Ahuja, Magnanti, and Orlin 7 is a useful source for information on network algorithms 1.3. Outline of the Review. The outline of this paper is as follows. In section 2 we describe empirical studies of the structure of networks, including social networks. formation networks, technological networks, and biological networks. In section 3 we describe some of the common properties that are observed in many of these networks how they are measured, and why they are believed to be important for the functioning of networked systems. Sections 4 to 7 form the heart of the review. They describe work on the mathematical modeling of networks, including random graph models and their generalizations, exponential random graphs, p* models and Markov graphs the small-world model and its variations, and models of growing graphs including preferential attachment models and their many variations. In section 8 we discuss the progress, such as it is, that has been made on the study of processes taking place on networks, including epidemic processes, network failure, models displayin phase transitions, and dynamical systems like random Boolean networks and cellular automata. In section 9 we give our conclusions and point to directions for future research 2. Networks in the Real world. In this section we look at what is known about the structure of networks of different types. Recent work on the mathematics of networks has been driven largely by observations of the properties of actual networks and attempts to model them, so network data are the obvious starting point for a review such as this. It also makes sense to examine simultaneously data from different kinds of networks. One of the principal thrusts of recent work in this area, inspired particularly by a groundbreaking 1998 paper by Watts and Strogatz 415 has been the comparative study of networks from different branches of science, witl emphasis on properties that are common to many of them and the mathematical developments that mirror those properties. We here divide our summary into four loose categories of networks: social networks information networks technological networks, and biological networks. 2. 1. Social Networks. A social network is a set of people or groups of people with some pattern of contacts or interactions between them 362, 408. The pat terns of friendships between individuals 295, 347, business relationships between companies 268, 285, and intermarriages between families 326 are all examples of networks that have been studied in the past. Of the academic disciplines, the social ciences have the longest history of the substantial quantitative study of real-wor networks [162, 362. Of particular note among the early worl the following: Moreno's networks of friendships within small 295, of which Figure 1.3 is an example: the so-called southern women study Gardner 103, which focused on the social circles of women in an unnamed city in olleagues of social net works of factory workers in the late 1930s in Chicago 356; the mathematical models of Rapoport 1345, who was one of the first theorists, perhaps the first, to stress Occasionally social networks of animals have been investigated also, such as dolphins [96), not to mention networks of fictional characters, such as the protagonists of Tolstoy s Anna Karenina (243 or Marvel Comics superheroes [10]
174 M. E. J. NEWMAN Farther afield, there are a variety of books on the study of networks in particular fields. Within graph theory the books by Harary [187] and by Bollob´as [62] are widely cited as are, among social network theorists, the books by Wasserman and Faust [408] and by Scott [362]. The book by Ahuja, Magnanti, and Orlin [7] is a useful source for information on network algorithms. 1.3. Outline of the Review. The outline of this paper is as follows. In section 2 we describe empirical studies of the structure of networks, including social networks, information networks, technological networks, and biological networks. In section 3 we describe some of the common properties that are observed in many of these networks, how they are measured, and why they are believed to be important for the functioning of networked systems. Sections 4 to 7 form the heart of the review. They describe work on the mathematical modeling of networks, including random graph models and their generalizations, exponential random graphs, p∗ models and Markov graphs, the small-world model and its variations, and models of growing graphs including preferential attachment models and their many variations. In section 8 we discuss the progress, such as it is, that has been made on the study of processes taking place on networks, including epidemic processes, network failure, models displaying phase transitions, and dynamical systems like random Boolean networks and cellular automata. In section 9 we give our conclusions and point to directions for future research. 2. Networks in the Real World. In this section we look at what is known about the structure of networks of different types. Recent work on the mathematics of networks has been driven largely by observations of the properties of actual networks and attempts to model them, so network data are the obvious starting point for a review such as this. It also makes sense to examine simultaneously data from different kinds of networks. One of the principal thrusts of recent work in this area, inspired particularly by a groundbreaking 1998 paper by Watts and Strogatz [415], has been the comparative study of networks from different branches of science, with emphasis on properties that are common to many of them and the mathematical developments that mirror those properties. We here divide our summary into four loose categories of networks: social networks, information networks, technological networks, and biological networks. 2.1. Social Networks. A social network is a set of people or groups of people with some pattern of contacts or interactions between them [362, 408]. The patterns of friendships between individuals [295, 347], business relationships between companies [268, 285], and intermarriages between families [326] are all examples of networks that have been studied in the past.1 Of the academic disciplines, the social sciences have the longest history of the substantial quantitative study of real-world networks [162, 362]. Of particular note among the early works on the subject are the following: Moreno’s networks of friendships within small groups [295], of which Figure 1.3 is an example; the so-called southern women study of Davis, Gardner, and Gardner [103], which focused on the social circles of women in an unnamed city in the American south in 1936; the study by Elton Mayo and colleagues of social networks of factory workers in the late 1930s in Chicago [356]; the mathematical models of Rapoport [345], who was one of the first theorists, perhaps the first, to stress 1Occasionally social networks of animals have been investigated also, such as dolphins [96], not to mention networks of fictional characters, such as the protagonists of Tolstoy’s Anna Karenina [243] or Marvel Comics superheroes [10]
THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS the importance of the degree distribution in networks of all kinds, not just social networks; and the studies of friendship networks of school children by rapoport and others 347 In more recent years udies of business communities 167, 168, 268 and of patterns of sexual contacts 45, 217, 242, 265 have attracted particular atten- Another important set of experiments are the famous"small-world"experiments of Milgram 282, 392. No actual networks were reconstructed in these experiments, but nonetheless they tell us about network structure. The experiments probed the distribution of path lengths in an acquaintance network by asking participants to pass a letter to one of their first-name acquaintances in an attempt to get it to an assigned target individual. Most of the letters in the experiment were lost, but about a quarter reached the target and passed on average through the hands of only about six people in doing so. This experiment was the origin of the popular concept of the six degrees of separation, "although that phrase did not appear in Milgram's writing, being coined some decades later by Guare [182. A brief but useful early review of Milgram's work and work stemming from it was given by Garfield [1691 Traditional social network studies often suffer from problems of inaccuracy, sub- jectivity, and small sample size. With the exception of a few ingenious indirect studies such as Milgram's, data collection is usually carried out by querying participants di- rectly using questionnaires or interviews. Such methods are labor-intensive and there- fore limit the size of the network that can be observed. Survey data are, moreover, influenced by subjective biases on the part of respondents: how one respondent defines a friend, for example, could be quite different from how another does. Although much effort is put into eliminating possible sources of inconsistency, it is generally accepted that there are large and essentially uncontrolled errors in most of these studies. A review of the issues has been given by Marsden 270 Because of these problems many researchers have turned to other methods for probing social networks. One source of copious and relatively reliable data is col- laboration networks. These are typically affiliation networks in which participants collaborate in groups of one kind or another, and links between pairs of individuals are established by common group membership. A classic, though rather frivolous example of such a network is the collaboration network of film actors, which is thor- oughly documented in the online Internet Movie Database. In this network, actors collaborate in films and two actors are considered connected if they have appeared in a film together. Statistical properties of this network have been analyzed by a number of authors [ 4, 20, 322, 415. Other examples of networks of this type are networks of company directors, in which two directors are linked if they belong to the same board of directors [104, 105, 268: networks of coauthorship among aca- demics, in which individuals are linked if they have coauthored one or m 43, 68, 107, 181, 278, 291, 310, 311, 312: and coappearance networks, in which individuals are linked by mention in the same context, particularly on Web pages 3, 226 or in newspaper articles 99(see Figure 1. 2b) Another source of reliable data about personal connections between people is communication records of certain kinds. For example, one could construct a network in which each(directed)edge between two people represented a letter or package sent by mail from one to the other. No study of such a network has been published as far as ve are aware, but some similar things have. Aiello, Chung, and Lu 8, 9 have analyzed ler containing several documents
THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS 175 the importance of the degree distribution in networks of all kinds, not just social networks; and the studies of friendship networks of school children by Rapoport and others [347, 149]. In more recent years, studies of business communities [167, 168, 268] and of patterns of sexual contacts [45, 217, 242, 265] have attracted particular attention. Another important set of experiments are the famous “small-world” experiments of Milgram [282, 392]. No actual networks were reconstructed in these experiments, but nonetheless they tell us about network structure. The experiments probed the distribution of path lengths in an acquaintance network by asking participants to pass a letter2 to one of their first-name acquaintances in an attempt to get it to an assigned target individual. Most of the letters in the experiment were lost, but about a quarter reached the target and passed on average through the hands of only about six people in doing so. This experiment was the origin of the popular concept of the “six degrees of separation,” although that phrase did not appear in Milgram’s writing, being coined some decades later by Guare [182]. A brief but useful early review of Milgram’s work and work stemming from it was given by Garfield [169]. Traditional social network studies often suffer from problems of inaccuracy, subjectivity, and small sample size. With the exception of a few ingenious indirect studies such as Milgram’s, data collection is usually carried out by querying participants directly using questionnaires or interviews. Such methods are labor-intensive and therefore limit the size of the network that can be observed. Survey data are, moreover, influenced by subjective biases on the part of respondents; how one respondent defines a friend, for example, could be quite different from how another does. Although much effort is put into eliminating possible sources of inconsistency, it is generally accepted that there are large and essentially uncontrolled errors in most of these studies. A review of the issues has been given by Marsden [270]. Because of these problems many researchers have turned to other methods for probing social networks. One source of copious and relatively reliable data is collaboration networks. These are typically affiliation networks in which participants collaborate in groups of one kind or another, and links between pairs of individuals are established by common group membership. A classic, though rather frivolous, example of such a network is the collaboration network of film actors, which is thoroughly documented in the online Internet Movie Database.3 In this network, actors collaborate in films and two actors are considered connected if they have appeared in a film together. Statistical properties of this network have been analyzed by a number of authors [4, 20, 322, 415]. Other examples of networks of this type are networks of company directors, in which two directors are linked if they belong to the same board of directors [104, 105, 268]; networks of coauthorship among academics, in which individuals are linked if they have coauthored one or more papers [36, 43, 68, 107, 181, 278, 291, 310, 311, 312]; and coappearance networks, in which individuals are linked by mention in the same context, particularly on Web pages [3, 226] or in newspaper articles [99] (see Figure 1.2b). Another source of reliable data about personal connections between people is communication records of certain kinds. For example, one could construct a network in which each (directed) edge between two people represented a letter or package sent by mail from one to the other. No study of such a network has been published as far as we are aware, but some similar things have. Aiello, Chung, and Lu [8, 9] have analyzed 2Actually a folder containing several documents. 3http://www.imdb.com/
MLE.」 NEWMAN a network of telephone calls made over the at&T long-distance network on a single day. The vertices of this network represent telephone numbers and the directed edges calls from one number to another. Even for just a single day this graph is enormous, having about 50 million vertices, one of the largest graphs yet studied after the graph of the World Wide Web. Ebel, Mielsch, and Bornholdt [136 have reconstructed the pattern of email communications between five thousand students at Kiel University from logs maintained by email servers. In this network the vertices represent email addresses and directed edges represent a message passing from one address to another Email networks have also been studied by Newman, Forrest, and Balthrop 320 and by Guimera et al. [184, and similar networks have been constructed for an"instant messaging "system by Smith 370, and for an Internet community Web site by Holme Edling, and Liljeros [195. Dodds, Muhamad, and Watts [110 have carried out an email version of Milgram's small-world experiment in which participants were asked to forward an email message to one of their friends in an effort to get the message ultimately to some chosen target individual. Response rates for the experiment were quite low, but a few hundred completed chains of messages were recorded, enough to allow various statistical analyses 2. 2. Information Networks. Our second network category is what we will call information networks(also sometimes called"knowledge networks"). The classic example of an information network is the network of citations between academic [138. Most learned articles cite previous works by others on related topics These citations form a network in which the vertices are articles and a directed edge from article a to article b indicates that a cites b. the structure of the citation network then reflects the structure of the information stored at its vertices. hence the term"information network, although certainly there are social aspects to the citation patterns of papers too 419 Citation networks are acyclic(see section 1. 1)because papers can only cite other papers that have already been written, not those that have yet to be written. Thus all edges in the network point backwards in time, making closed loops impossible, or at least extremely rare(see Figure 2.1) As an object of scientific study, citation networks have a great advantage the copious and accurate data available for them. Quantitative study of publication patterns stretches back at least as far as Alfred Lotka's groundbreaking 1926 discover of the so-called Law of Scientific Productivity, which states that the distribution of the numbers of papers written by individual scientists follows a power law. That is, the number of scientists who have written k papers falls off as k-a for some constant a (In fact, this result extends to the arts and humanities as well. The first serious work on citation patterns was conducted in the 1960s as large citation databases became available through the work of Eugene Garfield and other pioneers in the field of bibliometrics. The network formed by citations was discussed in an early paper by Price 342, in which, among other things, the author points out for the first time that both the in- and out-degree distributions of the network follow power laws,a far-reaching discovery which we discuss further in section 3. 3. Many other studies of citation networks have been performed since then, using the ever better resources available in citation databases. Of particular note are the studies by Seglen 363 and Redner 350 4 An interesting development in the study of citation patterns has been the arrival of automatic citation "crawlers" that construct citation networks from online papers. Example seer(http://citeseer.nj.neccom/),SpirEs(hTtP://www.slac.stanfordedu/spires/hep/),andCite base(http://citebase.eprintsorg/)
176 M. E. J. NEWMAN a network of telephone calls made over the AT&T long-distance network on a single day. The vertices of this network represent telephone numbers and the directed edges calls from one number to another. Even for just a single day this graph is enormous, having about 50 million vertices, one of the largest graphs yet studied after the graph of the World Wide Web. Ebel, Mielsch, and Bornholdt [136] have reconstructed the pattern of email communications between five thousand students at Kiel University from logs maintained by email servers. In this network the vertices represent email addresses and directed edges represent a message passing from one address to another. Email networks have also been studied by Newman, Forrest, and Balthrop [320] and by Guimer`a et al. [184], and similar networks have been constructed for an “instant messaging” system by Smith [370], and for an Internet community Web site by Holme, Edling, and Liljeros [195]. Dodds, Muhamad, and Watts [110] have carried out an email version of Milgram’s small-world experiment in which participants were asked to forward an email message to one of their friends in an effort to get the message ultimately to some chosen target individual. Response rates for the experiment were quite low, but a few hundred completed chains of messages were recorded, enough to allow various statistical analyses. 2.2. Information Networks. Our second network category is what we will call information networks (also sometimes called “knowledge networks”). The classic example of an information network is the network of citations between academic papers [138]. Most learned articles cite previous works by others on related topics. These citations form a network in which the vertices are articles and a directed edge from article A to article B indicates that A cites B. The structure of the citation network then reflects the structure of the information stored at its vertices, hence the term “information network,” although certainly there are social aspects to the citation patterns of papers too [419]. Citation networks are acyclic (see section 1.1) because papers can only cite other papers that have already been written, not those that have yet to be written. Thus all edges in the network point backwards in time, making closed loops impossible, or at least extremely rare (see Figure 2.1). As an object of scientific study, citation networks have a great advantage in the copious and accurate data available for them. Quantitative study of publication patterns stretches back at least as far as Alfred Lotka’s groundbreaking 1926discovery of the so-called Law of Scientific Productivity, which states that the distribution of the numbers of papers written by individual scientists follows a power law. That is, the number of scientists who have written k papers falls off as k−α for some constant α. (In fact, this result extends to the arts and humanities as well.) The first serious work on citation patterns was conducted in the 1960s as large citation databases became available through the work of Eugene Garfield and other pioneers in the field of bibliometrics. The network formed by citations was discussed in an early paper by Price [342], in which, among other things, the author points out for the first time that both the in- and out-degree distributions of the network follow power laws, a far-reaching discovery which we discuss further in section 3.3. Many other studies of citation networks have been performed since then, using the ever better resources available in citation databases. Of particular note are the studies by Seglen [363] and Redner [350].4 4An interesting development in the study of citation patterns has been the arrival of automatic citation “crawlers” that construct citation networks from online papers. Examples include Citeseer (http://citeseer.nj.nec.com/), SPIRES (http://www.slac.stanford.edu/spires/hep/), and Citebase (http://citebase.eprints.org/)