THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS 177 tation network World-Wide Web in which the vertices are papers and the directed edges are citations of one paper by another. Since papers can only cite those that came before them(lower down in the figure) the graph -it has no closed loops. Right: the World wide Web, a network of tert page ccessible over the Internet, in which the vertices are pages and the directed edges are yperlinks. There are no constraints on the Web that forbid cycles and hence it is in Another very important example of an information network is the World Wide Web, which is a network of Web pages containing information, linked together by hyperlinks from one page to another 202. The Web should not be confused with the Internet, which is a physical network of computers linked together by optical fiber and other data connections. Unlike a citation network. the World Wide Web is cyclic: there is no natural ordering of sites and no constraints that prevent the appearance of closed loops(Figure 2.1). The Web has been very heavily studied since its first appearance in the early 1990s, with the studies by Albert et al. 14, 34 Kleinberg et al. 1240, and Broder et al. [74 being particularly influential. The Web also appears to have power-law in- and out-degree distributions(section 3. 3), as well as a variety of other interesting properties 2, 14, 74, 158, 240, 253 One important point to notice about the Web is that our data about it come from"crawls"of the network, in which Web pages are found by following hyperlinks from other pages[74. Our picture of the network structure of the World Wide Web is therefore necessarily biased. A page will only be found if another page points to it, 6 and in a crawl that covers only a part of the Web(as all crawls do at present) pages e more likely to be found the more other pages point to them 262. This suggests, for instance, that our measurements of the fraction of pages with low in-degree migh be an underestimate. This behavior contrasts with that of a citation network. A While the Web is primarily an information network, it, like citation networks, has social aspects to its structure also 3 6This is not always strictly true. Some Web search engines allow the submission of nembers of the public for inclusion in databases, and such pages need not be the target of links from ly other pages. However, such pages also form a very small fraction of all Web pages, and certainly the biases discussed here remain very much present. ?The degree distribution for the Web shown in Figure 3.2 falls off slightly at low values of the degree, which may perhaps reflect this bias
THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS 177 citation network World−Wide Web Fig. 2.1 The two best studied information networks. Left: the citation network of academic papers in which the vertices are papers and the directed edges are citations of one paper by another. Since papers can only cite those that came before them (lower down in the figure) the graph is acyclic—it has no closed loops. Right: the World Wide Web, a network of text pages accessible over the Internet, in which the vertices are pages and the directed edges are hyperlinks. There are no constraints on the Webthat forbid cycles and hence it is in general cyclic. Another very important example of an information network is the World Wide Web, which is a network of Web pages containing information, linked together by hyperlinks from one page to another [202]. The Web should not be confused with the Internet, which is a physical network of computers linked together by optical fiber and other data connections.5 Unlike a citation network, the World Wide Web is cyclic; there is no natural ordering of sites and no constraints that prevent the appearance of closed loops (Figure 2.1). The Web has been very heavily studied since its first appearance in the early 1990s, with the studies by Albert et al. [14, 34], Kleinberg et al. [240], and Broder et al. [74] being particularly influential. The Web also appears to have power-law in- and out-degree distributions (section 3.3), as well as a variety of other interesting properties [2, 14, 74, 158, 240, 253]. One important point to notice about the Web is that our data about it come from “crawls” of the network, in which Web pages are found by following hyperlinks from other pages [74]. Our picture of the network structure of the World Wide Web is therefore necessarily biased. A page will only be found if another page points to it,6 and in a crawl that covers only a part of the Web (as all crawls do at present) pages are more likely to be found the more other pages point to them [262]. This suggests, for instance, that our measurements of the fraction of pages with low in-degree might be an underestimate.7 This behavior contrasts with that of a citation network. A 5While the Web is primarily an information network, it, like citation networks, has social aspects to its structure also [3]. 6This is not always strictly true. Some Web search engines allow the submission of pages by members of the public for inclusion in databases, and such pages need not be the target of links from any other pages. However, such pages also form a very small fraction of all Web pages, and certainly the biases discussed here remain very much present. 7The degree distribution for the Web shown in Figure 3.2 falls off slightly at low values of the in-degree, which may perhaps reflect this bias
MLE.」 NEWMAN paper can appear in the citation indices even if it has never been cited(and in fact a plurality of papers in the indices are never cited) A few other examples of information networks have been studied to a lesser extent Jaffe and Trajtenberg 206), for instance, have studied the network of citations between U.S. patents, which is similar in some respects to citations between academic papers A number of authors have looked at peer-to-peer networks 5, 6, 204, which are virtual networks of computers that allow sharing of files between computer users over local- or wide-area networks The network of relations between word classes in a thesaurus has been studied by Knuth 243 and more recently by various other authors 233, 383, 303. This network can be looked upon as an information network- users of a thesaurus "surf" the network from one word to another looking for the particular word that perfectly captures the idea they have in mind. However, it can also be looked at as a conceptual network representing the structure of the language, or possibly even the mental constructs used to represent the language. A number of other semantic word networks have also been investigated [119, 157, 368, 383 Preference networks provide an example of a bipartite information network. A preference network is a network with two kinds of vertices representing individuals and the objects of their preference, such as books or films, with an edge connect- ing each individual to the books or films they like.(Preference networks can also be weighted to indicate strength of likes or dislikes. ) A widely studied example of a preference network is the Each Movie database of film preferences. 8 Networks of this kind form the basis for collaborative filtering algorithms and recommender system which are techniques for predicting new likes or dislikes based on comparison of in- dividuals preferences with those of others [175, 351, 366. Collaborative filtering has found considerable commercial success for product recommendation and targeted ad- vertising, particularly with online retailers. Preference networks can also be of as social networks, linking not only people to objects, but also people to other people with similar preferences. This approach has been adopted occasionally in the literature 226 2.3. Technological Networks. Our third class of networks is technological net- works, man-made networks designed typically for distribution of some commodity or resource, such as electricity or information. The electric power grid is a good example This is a network of high-voltage three-phase transmission lines that spans a country or a portion of a country(as opposed to the local low-voltage AC power delivery lines that span individual neighborhoods ) Statistical studies of power grids have been made by, for example, Watts and Strogatz [415, Watts [ 411, and Amaral et al. 20 Other distribution networks that have been studied include the network of airline routes 20 and networks of roads 220, railways 261, 365, and pedestrian traffic [87 River networks could be regarded as a naturally occurring form of distribution network (actually a collection network)[111, 269, 352, 355, as could the vascular networks discussed in section 2.4. The telephone network and delivery networks such as those used by the post office or parcel delivery companies also fall into this general category and are presumably studied within the relevant corporations, if not yet by academic researchers. (We distinguish here between the physical telephone network of wires and cables and the network of who calls whom, discussed in section 2. 1 )Electron circuits [155 fall somewhere between distribution and communication networks Shttp://research.compaqcom/src/eachmovIe/
178 M. E. J. NEWMAN paper can appear in the citation indices even if it has never been cited (and in fact a plurality of papers in the indices are never cited). A few other examples of information networks have been studied to a lesser extent. Jaffe and Trajtenberg [206], for instance, have studied the network of citations between U.S. patents, which is similar in some respects to citations between academic papers. A number of authors have looked at peer-to-peer networks [5, 6, 204], which are virtual networks of computers that allow sharing of files between computer users over local- or wide-area networks. The network of relations between word classes in a thesaurus has been studied by Knuth [243] and more recently by various other authors [233, 383, 303]. This network can be looked upon as an information network— users of a thesaurus “surf” the network from one word to another looking for the particular word that perfectly captures the idea they have in mind. However, it can also be looked at as a conceptual network representing the structure of the language, or possibly even the mental constructs used to represent the language. A number of other semantic word networks have also been investigated [119, 157, 368, 383]. Preference networks provide an example of a bipartite information network. A preference network is a network with two kinds of vertices representing individuals and the objects of their preference, such as books or films, with an edge connecting each individual to the books or films they like. (Preference networks can also be weighted to indicate strength of likes or dislikes.) A widely studied example of a preference network is the EachMovie database of film preferences.8 Networks of this kind form the basis for collaborative filtering algorithms and recommender systems, which are techniques for predicting new likes or dislikes based on comparison of individuals’ preferences with those of others [175, 351, 366]. Collaborative filtering has found considerable commercial success for product recommendation and targeted advertising, particularly with online retailers. Preference networks can also be thought of as social networks, linking not only people to objects, but also people to other people with similar preferences. This approach has been adopted occasionally in the literature [226]. 2.3. Technological Networks. Our third class of networks is technological networks, man-made networks designed typically for distribution of some commodity or resource, such as electricity or information. The electric power grid is a good example. This is a network of high-voltage three-phase transmission lines that spans a country or a portion of a country (as opposed to the local low-voltage AC power delivery lines that span individual neighborhoods). Statistical studies of power grids have been made by, for example, Watts and Strogatz [415], Watts [411], and Amaral et al. [20]. Other distribution networks that have been studied include the network of airline routes [20] and networks of roads [220], railways [261, 365], and pedestrian traffic [87]. River networks could be regarded as a naturally occurring form of distribution network (actually a collection network) [111, 269, 352, 355], as could the vascular networks discussed in section 2.4. The telephone network and delivery networks such as those used by the post office or parcel delivery companies also fall into this general category and are presumably studied within the relevant corporations, if not yet by academic researchers. (We distinguish here between the physical telephone network of wires and cables and the network of who calls whom, discussed in section 2.1.) Electronic circuits [155] fall somewhere between distribution and communication networks. 8http://research.compaq.com/SRC/eachmovie/
THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS Another very widely studied technological network is the Internet, i.e., the net- work of physical connections between computers. Since there is a large and ever changing number of computers on the Internet, the structure of the network is usu- ally examined at a coarse-grained level, either the level of routers, special-purpose computers on the network that control the movement of data, or"autonomous sys- tems, " which are groups of computers within which networking is handled locally, but between which data flows over the public Internet(Figure 1. 2a). The computers at a single company or university would probably form a single autonomous system autonomous systems often correspond roughly with domain names In fact, the network of physical connections on the Internet is not easy to discover ince the infrastructure is maintained by many separate organizations. Typically, therefore, researchers reconstruct the network by reasoning from large samples of point-to-point data routes. So-called"traceroute"programs can report the sequence of network nodes that a data packet passes through when traveling between two points and if we assume an edge in the network between any two consecutive nodes along such a path, then a sufficiently large sample of paths will give us a fairly complete picture of the entire network. There may, however, be some edges that never get sampled so the reconstruction is typically a good, but not perfect, representation of the true physical structure of the Internet. Studies of Internet structure have been carried out by, among others, Faloutsos et al. [148, Broida and Claffy [75, and Chen et al.[86 One of the interesting features of all of these technological networks is that their structure is clearly governed to some extent by space and geography. Power grids the Internet, air, road, and rail networks all span continents, and which vertices in the network are connected to which others is presumably both a function of what is technologically desirable and what is geographically feasible [425. It is not yet well understood what the interplay of these factors is 2. 4. Biological Networks. A number of biological systems can be usefully repre- ented as networks. Perhaps the classic example of a biological network is the network of metabolic pathways, which is a representation of metabolic substrates and products with directed edges joining them if a known metabolic reaction exists that acts on a given substrate and produces a given product. Most of us will probably have seen at some point the giant maps of metabolic pathways that many molecular biologists pin to their walls. Studies of the statistical properties of metabolic networks have been performed by, for example, Jeong et al. 213, 339, Fell and Wagner [153, 404 and Stelling et al. 382. A separate network is the network of mechanistic physical interactions between proteins(as opposed to chemical reactions among metabolites which is usually referred to as a protein interaction network. Interaction networks have been studied by a number of authors 205, 211, 273, 375, 393 Another important class of biological network is the genetic regulatory network The expression of a gene, i. e, the production by transcription and translation of the protein for which the gene codes, can be controlled by the presence of other proteins both activators and inhibitors, so that the genome itself forms a switching network ith vertices representing the proteins and directed edges representing dependence of protein production on the proteins at other vertices. The statistical structure of regulatory networks has been studied recently by various authors [152, 183, 367] Genetic regulatory networks were in fact one of the first networked dynamical sy gThe st metabolites appear in more than one place on the chart, so that some pairs of
THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS 179 Another very widely studied technological network is the Internet, i.e., the network of physical connections between computers. Since there is a large and everchanging number of computers on the Internet, the structure of the network is usually examined at a coarse-grained level, either the level of routers, special-purpose computers on the network that control the movement of data, or “autonomous systems,” which are groups of computers within which networking is handled locally, but between which data flows over the public Internet (Figure 1.2a). The computers at a single company or university would probably form a single autonomous system— autonomous systems often correspond roughly with domain names. In fact, the network of physical connections on the Internet is not easy to discover since the infrastructure is maintained by many separate organizations. Typically, therefore, researchers reconstruct the network by reasoning from large samples of point-to-point data routes. So-called “traceroute” programs can report the sequence of network nodes that a data packet passes through when traveling between two points, and if we assume an edge in the network between any two consecutive nodes along such a path, then a sufficiently large sample of paths will give us a fairly complete picture of the entire network. There may, however, be some edges that never get sampled, so the reconstruction is typically a good, but not perfect, representation of the true physical structure of the Internet. Studies of Internet structure have been carried out by, among others, Faloutsos et al. [148], Broida and Claffy [75], and Chen et al. [86]. One of the interesting features of all of these technological networks is that their structure is clearly governed to some extent by space and geography. Power grids, the Internet, air, road, and rail networks all span continents, and which vertices in the network are connected to which others is presumably both a function of what is technologically desirable and what is geographically feasible [425]. It is not yet well understood what the interplay of these factors is. 2.4. Biological Networks. A number of biological systems can be usefully represented as networks. Perhaps the classic example of a biological network is the network of metabolic pathways, which is a representation of metabolic substrates and products with directed edges joining them if a known metabolic reaction exists that acts on a given substrate and produces a given product. Most of us will probably have seen at some point the giant maps of metabolic pathways that many molecular biologists pin to their walls.9 Studies of the statistical properties of metabolic networks have been performed by, for example, Jeong et al. [213, 339], Fell and Wagner [153, 404], and Stelling et al. [382]. A separate network is the network of mechanistic physical interactions between proteins (as opposed to chemical reactions among metabolites), which is usually referred to as a protein interaction network. Interaction networks have been studied by a number of authors [205, 211, 273, 375, 393]. Another important class of biological network is the genetic regulatory network. The expression of a gene, i.e., the production by transcription and translation of the protein for which the gene codes, can be controlled by the presence of other proteins, both activators and inhibitors, so that the genome itself forms a switching network with vertices representing the proteins and directed edges representing dependence of protein production on the proteins at other vertices. The statistical structure of regulatory networks has been studied recently by various authors [152, 183, 367]. Genetic regulatory networks were in fact one of the first networked dynamical sys- 9The standard chart of the metabolic network is somewhat misleading. For reasons of clarity and aesthetics, many metabolites appear in more than one place on the chart, so that some pairs of vertices are actually the same vertex
MLE.」 NEWMAI tems for which large-scale modeling attempts were made. The early work on random Boolean nets by Kauffman [ 223, 224, 225 is a classic in this field and anticipated recent developments by several decades Another much-studied example of a biological network is the food web, in which the vertices represent species in an ecosystem and a directed edge from species A to species B indicates that A preys on B 91, 338-see Figure 1.2c.(Sometimes the relationship is drawn the other way around, because ecologists tend to think in terms of energy or carbon flows through food webs; a predator-prey interaction is thus drawn as an arrow pointing from prey to predator, indicating energy How from prey to predator when the prey is eaten. )Construction of complete food webs is a laborious business, but a number of quite extensive data sets have become available in recent years 27, 176, 203, 271. Statistical studies of the topologies of food webs have been carried out by Sole and Montoya[289, 374, Camacho, Guimera, and Amaral [82, and Dunne et al. [132, 133, 422, among others. A particularly thorough study of webs of plants and herbivores has been conducted by Jordano, Bascompte, and Olesen 218 hich includes statistics for no less than 53 different networks Neural networks are another class of biological networks of considerable impor tance. Measuring the topology of real neural networks is extremely difficult, but has been done successfully in a few cases. The best known example is the reconstruction of the 282-neuron neural network of the nematode C. elegans by White et al. [ 420. The etwork structure of the brain at larger scales than individual neurons--functional areas and pathways-has been investigated by Sporns 378 and Sporns, Tononi, and Edelman 379 Blood vessels and the equivalent vascular networks in plants form the foundation for one of the most successful theoretical models of the effects of network structure on the behavior of a networked system, the theory of biological allometry 29, 416, 417 although we are not aware of any quantitative studies of their statistical structure Finally we mention two examples of networks from the physical sciences, the network of free energy minima and saddle points in glasses [130 and the network of conformations of polymers and the transitions between them 360, both of which appear to have some interesting structural properties. 3. Properties of Networks. Perhaps the simplest useful model of a net- work is the random graph, first studied by Rapoport 345, 346, Solomonoff and Rapoport 377, and Erdos and Renyi [141, 142, 143, which we describe in section 4.1 In this model, undirected edges are placed at random between a fixed number n of ertices to create a network in which each of the in(n-1)possible edges is indepen dently present with some probability p, and the number of edges connected to each vertex--the degree of the vertex-is distributed according to a binomial distribution or a Poisson distribution in the limit of large n. The random graph has been well studied by mathematicians [63, 210, 222, and many results, both approximate and exact, have been proved rigorously. Most of the interesting features of real-world networks that have attracted the attention of researchers in the last few years, how- ever, concern the ways in which networks are not like random graphs. Real networks e nonrandom in some revealing ways that suggest both possible mechanisms that could be guiding network formation, and possible ways in which we could exploit network structure to achieve certain aims. In this section we describe some features that appear to be common to networks of many different types 3.1. The Small-World Effect. In section 2.1 we described the famous experi- ments carried out by Stanley Milgram in the 1960s, in which letters passed from
180 M. E. J. NEWMAN tems for which large-scale modeling attempts were made. The early work on random Boolean nets by Kauffman [223, 224, 225] is a classic in this field and anticipated recent developments by several decades. Another much-studied example of a biological network is the food web, in which the vertices represent species in an ecosystem and a directed edge from species A to species B indicates that A preys on B [91, 338]—see Figure 1.2c. (Sometimes the relationship is drawn the other way around, because ecologists tend to think in terms of energy or carbon flows through food webs; a predator-prey interaction is thus drawn as an arrow pointing from prey to predator, indicating energy flow from prey to predator when the prey is eaten.) Construction of complete food webs is a laborious business, but a number of quite extensive data sets have become available in recent years [27, 176, 203, 271]. Statistical studies of the topologies of food webs have been carried out by Sol´e and Montoya [289, 374], Camacho, Guimer`a, and Amaral [82], and Dunne et al. [132, 133, 422], among others. A particularly thorough study of webs of plants and herbivores has been conducted by Jordano, Bascompte, and Olesen [218], which includes statistics for no less than 53 different networks. Neural networks are another class of biological networks of considerable importance. Measuring the topology of real neural networks is extremely difficult, but has been done successfully in a few cases. The best known example is the reconstruction of the 282-neuron neural network of the nematode C. elegans by White et al. [420]. The network structure of the brain at larger scales than individual neurons—functional areas and pathways—has been investigated by Sporns [378] and Sporns, Tononi, and Edelman [379]. Blood vessels and the equivalent vascular networks in plants form the foundation for one of the most successful theoretical models of the effects of network structure on the behavior of a networked system, the theory of biological allometry [29, 416, 417], although we are not aware of any quantitative studies of their statistical structure. Finally we mention two examples of networks from the physical sciences, the network of free energy minima and saddle points in glasses [130] and the network of conformations of polymers and the transitions between them [360], both of which appear to have some interesting structural properties. 3. Properties of Networks. Perhaps the simplest useful model of a network is the random graph, first studied by Rapoport [345, 346], Solomonoff and Rapoport [377], and Erd˝os and R´enyi [141, 142, 143], which we describe in section 4.1. In this model, undirected edges are placed at random between a fixed number n of vertices to create a network in which each of the 1 2n(n − 1) possible edges is independently present with some probability p, and the number of edges connected to each vertex—the degree of the vertex—is distributed according to a binomial distribution, or a Poisson distribution in the limit of large n. The random graph has been well studied by mathematicians [63, 210, 222], and many results, both approximate and exact, have been proved rigorously. Most of the interesting features of real-world networks that have attracted the attention of researchers in the last few years, however, concern the ways in which networks are not like random graphs. Real networks are nonrandom in some revealing ways that suggest both possible mechanisms that could be guiding network formation, and possible ways in which we could exploit network structure to achieve certain aims. In this section we describe some features that appear to be common to networks of many different types. 3.1. The Small-World Effect. In section 2.1 we described the famous experiments carried out by Stanley Milgram in the 1960s, in which letters passed from
THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS person to person were able to reach a designated target individual in only a small number of steps-around six in the published cases. This result is one of the first direct demonstrations of the small-world effect, the fact that most pairs of vertices in most networks seem to be connected by a short path through the network. The existence of the small-world effect had been speculated upon before Mil- gram's work, notably in a remarkable 1929 short story by the Hungarian writer Frigyes Karinthy 221 and more rigorously in the mathematical work of Pool and Kochen 1340, which, although published after Milgram's studies, was in circulation preprint form for a decade before Milgram took up the problem. Nowadays, the small-world effect has been studied and verified directly in a large number of different etwork Consider an undirected network, and let us define e to be the mean geodesic i. e, shortest) distance between vertex pairs in a network (31) nn+∑可 where dii is the geodesic distance from vertex i to vertex j. Notice that we have included the distance from each vertex to itself(which is zero)in this average. This is mathematically convenient for a number of reasons, but not all authors do it. In any case, its inclusion simply multiplies e by(n-1)/(n+1) and hence gives a correction of order n-l, which is often negligible for practical purposes The quantity l can be measured for a network of n vertices and m edges in time O(mn)using simple breadth-first search [ 7, also called a"burning algorithm"in the physics literature. In Table 3.1, we show values of e taken from the literature for a variety of different networks. As the table shows, the values are in all cases quite mall-much smaller than the number n of vertices. for instance The definition (3. 1)of e is problematic in networks that have more than one component. In such cases, there exist vertex pairs that have no connecting path. Conventionally one assigns infinite geodesic distance to such pairs, but then the value of e also becomes infinite. To avoid this problem one usually defines l on such networks to be the mean geodesic distance between all pairs that have a connecting path. Pairs that fall in two different components are excluded from the average. The figures in Table 3. 1 were all calculated in this way. An alternative and perhaps more satisfactor approach is to define e to be the "harmonic mean"geodesic distance between all pairs, i. e, the reciprocal of the average of the reciprocals 号n(n+1) Infinite values of dii then contribute nothing to the sum. This approach has dopted only ionally in network calculations 259, but perhaps should be more o The small-world effect has obvious implications for the dynamics of processes taking place on networks. For example, if one considers the spread of information, or indeed anything else, across a network, the small-world effect implies that that spread will be fast on most real-world networks. If it takes only six steps for a rumor t spread from any person to any other, for instance, then the rumor will spread much faster than if it takes a hundred steps, or a million. This affects the number of"hops a packet must make to get from one computer to another on the Internet, the number
THE STRUCTURE AND FUNCTION OF COMPLEX NETWORKS 181 person to person were able to reach a designated target individual in only a small number of steps—around six in the published cases. This result is one of the first direct demonstrations of the small-world effect, the fact that most pairs of vertices in most networks seem to be connected by a short path through the network. The existence of the small-world effect had been speculated upon before Milgram’s work, notably in a remarkable 1929 short story by the Hungarian writer Frigyes Karinthy [221] and more rigorously in the mathematical work of Pool and Kochen [340], which, although published after Milgram’s studies, was in circulation in preprint form for a decade before Milgram took up the problem. Nowadays, the small-world effect has been studied and verified directly in a large number of different networks. Consider an undirected network, and let us define to be the mean geodesic (i.e., shortest) distance between vertex pairs in a network: (3.1) = 1 1 2n(n + 1) i≥j dij , where dij is the geodesic distance from vertex i to vertex j. Notice that we have included the distance from each vertex to itself (which is zero) in this average. This is mathematically convenient for a number of reasons, but not all authors do it. In any case, its inclusion simply multiplies by (n − 1)/(n + 1) and hence gives a correction of order n−1, which is often negligible for practical purposes. The quantity can be measured for a network of n vertices and m edges in time O(mn) using simple breadth-first search [7], also called a “burning algorithm” in the physics literature. In Table 3.1, we show values of taken from the literature for a variety of different networks. As the table shows, the values are in all cases quite small—much smaller than the number n of vertices, for instance. The definition (3.1) of is problematic in networks that have more than one component. In such cases, there exist vertex pairs that have no connecting path. Conventionally one assigns infinite geodesic distance to such pairs, but then the value of also becomes infinite. To avoid this problem one usually defines on such networks to be the mean geodesic distance between all pairs that have a connecting path. Pairs that fall in two different components are excluded from the average. The figures in Table 3.1 were all calculated in this way. An alternative and perhaps more satisfactory approach is to define to be the “harmonic mean” geodesic distance between all pairs, i.e., the reciprocal of the average of the reciprocals: (3.2) −1 = 1 1 2n(n + 1) i≥j d−1 ij . Infinite values of dij then contribute nothing to the sum. This approach has been adopted only occasionally in network calculations [259], but perhaps should be used more often. The small-world effect has obvious implications for the dynamics of processes taking place on networks. For example, if one considers the spread of information, or indeed anything else, across a network, the small-world effect implies that that spread will be fast on most real-world networks. If it takes only six steps for a rumor to spread from any person to any other, for instance, then the rumor will spread much faster than if it takes a hundred steps, or a million. This affects the number of “hops” a packet must make to get from one computer to another on the Internet, the number