Large-scale topological and dynamical properties of the Internet

Large-scale topological and dynamical properties of the Internet Alexei Va ´zquez,1Romualdo Pastor-Satorras,2and Alessandro Vespignani3 1International School for Advanced Studies SISSA/ISAS, via Beirut 4, 34014 Trieste, Italy 2Departament de Fı ´sica i Enginyeria Nuclear, Universitat Polite `cnica de Catalunya, Campus Nord, Mo `dul B4, 08034 Barcelona, Spain 3The Abdus Salam International Centre for Theoretical Physics (ICTP), P.O. Box 586, 34100 Trieste, Italy 共Received 21 December 2001; published 28 June 2002兲 We study the large-scale topological and dynamical properties of real Internet maps at the autonomous system level, collected in a 3-yr time interval. We find that the connectivity structure of the Internet presents statistical distributions settled in a well-defined stationary state. The large-scale properties are characterized by a scale-free topology consistent with previous observations. Correlation functions and clustering coefficients exhibit a remarkable structure due to the underlying hierarchical organization of the Internet. The study of the Internet time evolution shows a growth dynamics with aging features typical of recently proposed growing network models. We compare the properties of growing network models with the present real Internet data analysis. DOI: 10.1103/PhysRevE.65.066130 PACS number共s兲: 89.75.⫺k, 87.23.Ge, 05.70.Ln I. INTRODUCTION The Internet is a capital example of growing complex network 关1,2兴interconnecting large numbers of computers around the world. Growing networks exhibit a high degree of wiring entanglement that takes place during their dynamical evolution. This feature, at the heart of the proposed and interesting topological properties recently observed in growing network systems 关3,4兴, has triggered the attention of the research community to the study of the large-scale properties of router-level maps of the Internet 关5–7兴. The statistical analysis performed so far has focused on several quantities exhibiting nontrivial properties: wiring redundancy and clustering, 关8–11兴, the distribution of shortest path lengths 关5,10兴, and the eigenvalue spectra of the connectivity matrix 关10兴. Noteworthy, the presence of a power-law connectivity distribution 关8,10–13兴makes the Internet an example of the recently identified class of scale-free networks 关14,15兴. This evidence implies the absence of any characteristic connectivity—large connectivity fluctuations—and a high heterogeneity of the network structure. As widely pointed out in the literature 关13,16,17兴,a deeper empirical understanding of the topological properties of the Internet is fundamental in the developing of realistic Internet map generators, that on their turn are used to test and optimize Internet protocols. In fact, the Internet topology has a great influence on the dynamics that data traffic carries out on top of it. Hence, a better understanding of the Internet structure is of primary importance in the design of routing 关16,17兴and searching algorithms 关18,19兴, and to protect from virus spreading 关20兴and node failures 关21–23兴. In this perspective, the direct measurement and statistical characterization of real Internet maps are of crucial importance in the identification of the basic mechanisms that rule the Internet structure and dynamics. In this work, we shall consider the evolution of real Internet maps from 1997 to 2000, collected by the National Laboratory for Applied Network Research 共NLANR兲关5兴, in order to study the underlying dynamical processes leading to the Internet structure and topology. We provide a statistical analysis of several average properties. In particular, we consider the average connectivity, clustering coefficient, path length, and betweenness. These quantities will provide a preliminary test of the stationarity of the network. The scale-free nature of the Internet has been pointed out by inspecting the connectivity probability distribution, and it implies that the fluctuations around the average connectivity are not bounded. In order to provide a full characterization of the scale-free properties of the Internet, we analyze the connectivity and betweenness probability distributions for different time snapshot of the Internet maps. We observe that these distributions exhibit an algebraic behavior and are characterized by scaling exponents that are stationary in time. The shortest path length between pairs of nodes, on the other hand, appears to be sharply peaked around its average value, providing a striking evidence for the presence of welldefined small-world properties 关24兴. A more detailed picture of the Internet can be achieved by studying higher order correlation functions of the network. In this sense, we show that the Internet hierarchical structure is reflected in nontrivial scale-free betweenness and connectivity correlation functions. Finally, we study several quantities related to the growth dynamics of the network. The analysis points out the presence of two distinct wiring processes: the first concerns newly added nodes, while the second is related to already existing nodes increasing their interconnections. We confirm that newly added nodes establish new links with the linear preferential attachment rule often used in modeling growing networks 关14兴. In addition, a study of the connectivity evolution of a single node shows a rich dynamical behavior with aging properties. The present study could provide some hints for a more realistic modeling of the Internet evolution, and with this purpose in mind we provide a discussion of some of the existing growing network models in the light of our findings. A short account of these results appeared in Ref. 关25兴. The paper is organized as follows. In Sec. II we describe the Internet maps used in our study. Section III is devoted to the study of average quantities as a function of time. In Sec. PHYSICAL REVIEW E, VOLUME 65, 066130 1063-651X/2002/65共6兲/066130共12兲/$20.00 ©2002 The American Physical Society65 066130-1 IV we provide the analysis of the statistical distributions characterizing the Internet topology. We obtain evidence for the scale-free nature of this network as well as for the stationarity in time of this property. In Sec. V we characterize the hierarchical structure of the Internet by the statistical analysis of the betweenness and connectivity correlation functions. Section VI reports the study of dynamical properties such as the preferential attachment and the evolution of the average connectivity of newly added nodes. These properties, which show aging features, are the basis for the developing of Internet dynamical models. Section VII is devoted to a detailed discussion of some Internet models as compared with the presented real data analysis. Finally, in Sec. VIII we draw our conclusions and perspectives. II. MAPPING THE INTERNET Several Internet mapping projects are currently devoted to obtain high-quality router-level maps of the Internet. In most cases, the map is constructed by using a hop-limited probe 共such as the UNIX traceroute tool兲from a single location in the network. In this case the result is a ‘‘directed,’’ map as seen from a specific location on the Internet 关7兴. This approach does not correspond to a complete map of the Internet because cross-links and other technical problems 共such as multiple Internet provider aliases兲are not fully considered. Heuristic methods to take into account these problems have been proposed 共see, for instance, Ref. 关26兴兲. A different representation of the Internet is obtained by mapping the autonomous systems 共AS兲topology. The Internet can be considered as a collection of subnetworks that are connected together. Within each subnetwork the information is routed using an internal algorithm that may differ from one subnetwork to another. Thus, each subnet is an independent unit of the Internet and it is often referred as an AS. These AS communicate between them using a specific routing algorithm, the border gateway protocol. Each AS number approximately maps to an Internet service provider 共ISP兲and their links are inter-ISP connections. In this case it is possible to collect data from several probing stations to obtain interconnectivity maps 共see Refs. 关5,6兴for a technical description of these projects兲. In particular, the NLANR project is collecting data since November 1997, and it provides topological as well as dynamical information on a consistent subset of the Internet. The first November 1997 map contains 3180 AS, and it has grown in time until the December 1999 measurement, consisting of 6374 AS. In the following we will consider the graph whose nodes represent the AS and whose links represent the adjacencies 共interconnections兲between AS. In particular we will focus on three different snapshots corresponding to 8 November 1997, 1998, and 1999, that will be referenced as AS97, AS98, and AS99, respectively. The NLANR connectivity maps are collected with a resolution of one day and are changing from day to day. These changes are due to the addition 共birth兲and deletion 共death兲of nodes and links, but also to the flickering of connections, so that a node may appear to be isolated 共not mapped兲from time to time. A simple test, however, shows that flickering is appreciable just in nodes with low connectivity. We compute the ratio rbetween the number of days in which a node is observed in the NLANR maps and the total number of days after the first appearance of the node, averaged over all nodes in the maps. The analysis reveals that r⯝1 and r⬎0.65 for nodes with connectivity k⭓10, and k⬍10, respectively. Hence, nodes with k⬍10 have fluctuations that must be taken into account. In order to shed light on this point, we inspect the incidence of deletion events with respect to the creation of new nodes. We consider a deletion event only if a node is not observed in the map during a 1-yr time interval. In Table I we show the total number of deletion events in a year, for 1997, 1998, and 1999, in comparison with the total number of new nodes created. It can be seen that the AS’s birth rate appears to be larger by a factor of 2 than the deletion rate. More interestingly, if we restrict the analysis to nodes with connectivity k⬎10, the deletion rate is reduced to a few percent of the birth rate. This clearly indicates that only poorly connected nodes have an appreciable probability to disappear. This fact is easily understandable in terms of the market competition among ISP’s, where small newcomers are the ones which more likely go out of business. III. AVERAGE PROPERTIES AND STATIONARITY The growth rate of AS maps reveals that the Internet is a rapidly evolving network. Thus, it is extremely important to know whether or not it has reached a stationary state whose average properties are time independent. This will imply that, despite the continuous increase of nodes and connections in the system, the network’s topological properties are not appreciably changing in time. As a first step, we have analyzed the behavior in time of several average magnitudes: the average connectivity 具 k 典 , the clustering coefficient 具 c 典 , the average path length 具 l 典 , and the average betweenness 具 b 典 . The connectivity kiof a node iis defined as the number of connections of this node with other nodes in the network, and 具 k 典 is the average of kiover all nodes in the network. Since each connection contributes to the connectivity of two nodes, we have that 具 k 典 ⫽2E/N, where Eis the total number of connections and Nis the number of nodes. Both Eand N are increasing with time but their ratio remains almost constant. The average connectivity for the years 1997, 1998, and 1999 共averaged over all the AS maps available for that year兲 is shown in Table II. In average each node has three to four connections, which is a small number compared with that of a fully connected network of the same size ( 具 k 典 ⫽N⫺1 ⬃103). The average connectivity gives information about the number of connections of any node but not about the overall TABLE I. Total number of new (Nnew) and deleted (Ndel) nodes in the years 1997, 1998, and 1999. We also report the number of deleted nodes with connectivity k⬎10. Year 1997 1998 1999 Nnew 309 1990 3410 Ndel 129 887 1713 Ndel(k⬎10) 0 14 68 VA ´ZQUEZ, PASTOR-SATORRAS, AND VESPIGNANI PHYSICAL REVIEW E 65 066130 066130-2 structure of these connections. More information can be obtained using the clustering coefficient introduced in Ref. 关24兴. The number of neighbors of a node iis given by its connectivity ki. On their turn, these neighbors can be connected among them forming a triangle with node i. The clustering coefficient ciis then defined as the ratio between the number of connections among the kineighbors of a given node iand its maximum possible value, ki(ki⫺1)/2. The average clustering coefficient 具 c 典 is the average of ciover all nodes in the network. The clustering coefficient thus provides a measure of how well locally interconnected are the neighbors of any node. The maximum value of 具 c 典 is 1, corresponding to a fully connected network. For random graphs 关27兴, which are constructed by connecting nodes at random with a fixed probability p, the clustering coefficient decreases with the network size Nas 具 c 典 rand⫽ 具 k 典 /N.Onthe contrary, it remains constant for regular lattices. The average clustering coefficient obtained for the years 1997, 1998, and 1999 is shown in Table II. As it can be seen, the clustering coefficient of the AS maps increases slowly with increasing Nand takes values 具 c 典 ⯝0.2, two orders of magnitudes larger than 具 c 典 rand⯝10⫺3, corresponding to a random graph with the same number of nodes and average connectivity. Therefore, the AS maps are far from being a random graph, a feature that can be naively understood using the following argument: In AS maps the connections among nodes are equivalent, but they are actually characterized by a real space length corresponding to the actual length of the physical connection between AS’s. The larger this length is, the higher the costs of installation and maintenance of the line, favoring therefore the connections between nearby nodes. It is thus likely that nodes within the same geographical region will have a large number of connection among them, increasing in this way the local clustering coefficient. With this reasoning one might be led to the conclusion that the Internet topology is close to a regular twodimensional lattice. The analysis of the shortest path length between nodes, however, reveals that this is not the case. Two nodes iand jare said to be connected if one can go from node ito jfollowing the connections in the network. The path from ito jmay not be unique and its length is given by the number of nodes visited. The average path length 具 l 典 is defined as the shortest path length between two nodes iand j, lij, averaged over every pair of nodes in the network. For regular lattices, 具 l 典 D⬃N1/D, where Dis the spatial dimension. As it can be seen from Table II, for the AS maps 具 l 典 ⯝3.7, which is smaller than the expected value for a regular two-dimensional lattice of the same size. The Internet strikingly exhibits what is known as the ‘‘small-world’’ effect 关24,28兴: in average one can go from one node to any other in the system passing through a very small number of intermediate nodes. This necessarily implies that besides the short local connections that contribute to the large clustering coefficient, there are some hubs and backbones that connect different regional networks, strongly decreasing the average path length. Another measure of this feature is given by the number of minimal paths that pass by each node. To go from one node in the network to another following the shortest path, a sequence of nodes is visited. If we do this for every pair of nodes in the network, there will be a certain number of key nodes that will be visited more often than others. Such nodes will be of great importance for the transmission of information along the network. This fact can be quantitatively measured by means of the betweenness bi, defined by the total number of shortest paths between any two nodes in the network that pass thorough the node i. The average betweenness 具 b 典 is the average value of biover all nodes in the network. The betweenness has been introduced in the analysis of social networks in Ref. 关29兴and more recently it has been studied in scale-free networks, with the name of load 关30兴. Moreover, an algorithm to compute the betweenness has been given in Ref. 关29兴. For a star network the betweenness takes its maximum value N(N⫺1)/2 at the central node and its minimum value N⫺1 at the vertices of the star. The average betweenness of the three AS maps analyzed here is shown in Table II. Its value is between 2Nand 3N, which is quite small in comparison with its maximum possible value N(N⫺1)/2⬃107. The present analysis makes clear that the Internet is not dominated by a very few highly connected nodes similarly to star-shaped architectures. As well, simple average measurements rule out the possibility of a random graph structure or a regular grid architecture. This evidence hints towards a peculiar topology that will be fully identified by looking at the detailed probability distributions of several quantities. Finally, it is important to stress that despite the network size is more than doubled in the 3-yr period considered, the average quantities suffer variations of a few percent 共see Table II兲. This points out that the system seems to have reached a fairly well-defined stationary state, as we shall confirm in the following section by analyzing the detailed statistical properties of the Internet. IV. FLUCTUATIONS AND SCALE-FREE PROPERTIES In order to get a deeper understanding of the network topology we look at the probability distributions pk(k) and pb(b) that any given node in the network has a connectivity kand a betweenness b, respectively. The study of these probability distributions will allow us to probe the extent of fluctuations and heterogeneity present in the network. We shall see that the strong scale-free nature of the Internet, previTABLE II. Average properties of the Internet for three different years. N, number of nodes; E, number of connections; 具 k 典 , average connectivity; 具 c 典 , average clustering coefficient; 具 l 典 , average path length; 具 b 典 , average betweenness. Figures in parentheses indicate the statistical uncertainty from averaging the values of the corresponding months in each year. Year 1997 1998 1999 N3112 3834 5287 E5450 6990 10100 具 k 典 3.5共1兲3.6共1兲3.8共1兲 具 c 典 0.18共3兲0.21共3兲0.24共3兲 具 l 典 3.8共1兲3.8共1兲3.7共1兲 具 b 典 /N2.4共1兲2.3共1兲2.2共1兲 LARGE-SCALE TOPOLOGICAL AND DYNAMICAL... PHYSICAL REVIEW E 65 066130 066130-3 ously noted in Refs. 关10,12兴, results in power-law distributions with diverging fluctuations for these quantities. The analysis of the maps reveals, in fact, an algebraic decay for the connectivity distribution, pk共k兲⬃k⫺ ␥ ,共1兲 extending over three orders of magnitude. In Fig. 1 we report the integrated connectivity distribution Pk共k兲⫽ 冕 k ⬁pk共k⬘兲dk⬘共2兲 corresponding to the AS97, AS98, and AS99 maps. The integrated distribution, which expresses the probability that a node has connectivity larger than or equal to k, scales as Pk共k兲⬃k1⫺ ␥ ,共3兲 and it has the advantage of being considerably less noisy that the original distribution. In all maps we find a clear powerlaw behavior with slope close to ⫺1.2 共see Fig. 1兲, yielding a connectivity exponent ␥ ⫽2.2⫾0.1. The distribution cutoff is fixed by the maximum connectivity of the system and is related to the overall size of the Internet map. We see that for more recent maps the cutoff is slightly increasing, as expected due to the Internet growth. On the other hand, the connectivity exponent ␥ seems to be independent of time and in good agreement with previous measurements 关10兴. The betweenness distribution pb(b)共i.e., the probability that any given node is passed over by bshortest paths兲shows also scale-free properties, with a power-law distribution pb共b兲⬃b⫺ ␦ 共4兲 extending over three decades. As shown in Fig. 2共a兲, the integrated betweenness distribution measured in the AS maps is evidently stable in the 3-yr period analyzed and follows a power-law decay Pb共b兲⫽ 冕 b ⬁pb共b⬘兲db⬘⬃b1⫺ ␦ ,共5兲 where the betweenness exponent is ␦ ⫽2.1⫾0.2. The connectivity and betweenness exponents can be simply related if one assumes that the number of shortest paths bkpassing over a node of connectivity kfollows the scaling form bk⬃k ␤ .共6兲 By inserting the latter relation in the integrated betweenness distribution Eq. 共5兲we obtain Pk共k兲⬃k ␤ (1⫺ ␦ ).共7兲 Since we have that Pk(k)⬃k1⫺ ␥ , we obtain the scaling relation ␤ ⫽ ␥ ⫺1 ␦ ⫺1.共8兲 The measured ␥ and ␦ have approximately the same value for the AS maps data and we expect to recover ␤ ⬇1.0. This is corroborated in Fig. 2共b兲, where we report the direct measurement of the average betweenness of a node as a function of its connectivity k. It is also worth remarking the study of the betweenness distribution in scale-free networks made in Ref. 关30兴. From a numerical study of both static and dynamic scale-free network models with different values of ␥ ,itwas found in Ref. 关30兴that the betweenness distribution follows a power-law decay with an estimated exponent ␦ ⫽2.2⫾0.1. The authors argued that this fact represents a universal property, independent of the connectivity exponent, for all scaleFIG. 1. Integrated connectivity distribution for the AS97, AS98, and AS99 maps. The power-law behavior is characterized by a slope ⫺1.2, which yields a connectivity exponent ␥ ⫽2.2⫾0.1. FIG. 2. 共a兲Integrated betweenness distribution for the AS97, AS98, and AS99 maps. The power-law behavior is characterized by a slope ⫺1.1, which yields a betweenness exponent ␦ ⫽2.1⫾0.2. 共b兲Betweenness bkas a function of the node’s connectivity k. The full line corresponds to the expected behavior bk⬃k. Errors bars take into account statistical fluctuations over different nodes with the same connectivity. VA ´ZQUEZ, PASTOR-SATORRAS, AND VESPIGNANI PHYSICAL REVIEW E 65 066130 066130-4 free networks with 2⬍ ␥ ⭐3. Our results on the AS maps present further support to the universality claim made in Ref. 关30兴. Another quantity of interest is the probability distribution of the clustering coefficient of the nodes. In our analysis we do not find definitive evidence for a power-law behavior of this distribution. However, still useful information can be gathered from studying the clustering coefficient ckas a function of the node connectivity. In this case the local clustering coefficient of each node ciis averaged over all nodes with the same connectivity k. The plots for the AS97, AS98, and AS99 maps are shown in Fig. 3. Also in this case, measurements yield a power-law behavior ck⬃k⫺ ␻ with ␻ ⫽0.75⫾0.03, extending over three orders of magnitude. The exponent 0.75 has been computed as an average over the regressions of the individual data sets. This fact implies that nodes with a small number of connections have larger local clustering coefficients than those with a large connectivity. This behavior is consistent with the picture previously described in Sec. III of highly clustered regional networks sparsely interconnected by national backbones and international connections. The regional clusters of AS are probably formed by a large number of nodes with small connectivity but large clustering coefficients. Moreover, they also should contain nodes with large connectivities that are connected with the other regional clusters. These large connectivity nodes will be on their turn connected to nodes in different clusters that are not interconnected and, therefore, will have a small local clustering coefficient. This picture also shows the existence of some hierarchy in the network that will become more evident in the following section. A different behavior is followed by the shortest path length lbetween two nodes, which does not show singular fluctuations from one pair of nodes to another. This can be shown by means of the probability distribution pl(l)of shortest path lengths lbetween pairs of nodes, reported in Fig. 4共a兲. This distribution is characterized by a sharp peak around its average value and its shape remains essentially unchanged from the AS97 to the AS99 maps. Associated to the shortest path length distribution we have the hop plot introduced in Ref. 关10兴. The hop plot is defined as the average fraction of nodes M(l)/Nwithin a distance less than or equal to lfrom a given node. At l⫽0 we find the starting node and, therefore, M(0)⫽1. At l⫽1 we find the starting node plus its neighbors and thus M(1)⫽ 具 k 典 ⫹1. If the network is made up by a single cluster, for l⫽lM, where lM is the maximum shortest path length, we have M(lM)⫽N. For regular D-dimensional lattices, M(l)⬃lD, and in this case Mcan be interpreted as the mass. The hop plot is related to the distribution of shortest path lengths through the following relation: M共l兲 N⫽兺 l⬘⫽0 l pl共l⬘兲.共9兲 The hop plots for the AS97, AS98 and AS99 maps are shown in Fig. 4共b兲. In this case the shortest path length barely spans a decade (lM⫽11). Most importantly, M(l) practically reaches its maximum value Nat l⫽5. Hence, the shortest path length does not show strong fluctuations, as already noticed from the shortest path length distribution. In Ref. 关10兴it was argued that the increase of M(l) for small l follows a power-law behavior. This observation is not consistent with the present data, that yield a very abrupt increase taking place in a very narrow range, as shown in Fig. 4共b兲. Finally, it is important to stress again that all the measured distributions are characterized by scaling exponents or behaviors that are not changing in time. This implies that the statistical properties characterizing the Internet are time inFIG. 3. Clustering coefficient ckas a function of the connectivity kfor the AS97, AS98, and AS99 maps. The best fitting powerlaw behavior is characterized by a slope ⫺0.75. Errors bars take into account statistical fluctuations over different nodes with the same connectivity. FIG. 4. 共a兲Distribution of shortest path lengths pl(l) for the AS97, AS98, and AS99 maps. 共b兲Hop plots M(l) for the same maps. See text for definitions. LARGE-SCALE TOPOLOGICAL AND DYNAMICAL... PHYSICAL REVIEW E 65 066130 066130-5 dependent, providing a further test to the network stationarity; i.e., the Internet is self-organized in a stationary state characterized by scale-free fluctuations. V. HIERARCHY AND CORRELATIONS Due to installation costs, the Internet has been designed with a hierarchical structure. The primary known structural difference between Internet nodes is the distinction between stub and transit domains. Nodes in stub domains have links that go only through the domain itself. Stub domains, on the other hand, are connected via a gateway node to transit domains that, on the contrary, are fairly well interconnected via many paths. This hierarchy can be schematically divided into international connections, national backbones, regional networks, and local area networks. Nodes providing access to international connections or national backbones are of course on top level of this hierarchy, since they make possible the communication between regional and local area networks. Moreover, in this way, a small average path length can be achieved with a small average connectivity. Very likely the hierarchical structure will introduce some correlations in the network topology. We can explore the hierarchical structure of the Internet by means of the conditional probability pc(k⬘ 兩 k) that a link belonging to a node with connectivity kpoints to a node with connectivity k⬘.If this conditional probability is independent of k, we are in presence of a topology without any correlation among the nodes’ connectivity. In this case, pc(k⬘ 兩 k)⫽pc(k⬘) ⬃k⬘pk(k⬘), in view of the fact that any link points to nodes with a probability proportional to their connectivity. On the contrary, the explicit dependence on kis a signature of nontrivial correlations among the nodes’ connectivity, and the presence of a hierarchical structure in the network topology. A direct measurement of the pc(k⬘ 兩 k) function is a rather complex task due to large statistical fluctuations. More clear indications can be extracted by studying the quantity 具 knn 典 ⫽兺 k⬘ k⬘pc共k⬘ 兩 k兲,共10兲 i.e., the nearest-neighbors average connectivity of nodes with connectivity k. In Fig. 5共a兲we show the results obtained for the AS97, AS98, and AS99 maps, that again exhibit a clear power-law dependence on the connectivity degree, 具 knn 典 ⬃k⫺ ␯ k,共11兲 with an exponent ␯ k⫽0.5⫾0.1. This observation clearly implies that the connectivity correlation function has a marked dependence upon k, suggesting nontrivial correlation properties for the Internet. In practice, this result indicates that highly connected nodes are more likely pointing to less connected nodes, emphasizing the presence of a hierarchy in which smaller providers connect to larger ones and so on, climbing different levels of connectivity. Similarly, it is expected that nodes with high betweenness 共that is, carrying a heavy load of traffic兲, and consequently a large connectivity, will be connected to nodes with smaller betweenness, less load and, therefore, small connectivity. A simple way to measure this effect is to compute the average betweenness 具 bnn 典 of the neighbors of the nodes with a given betweenness b. The plot of 具 bnn 典 for the AS97, AS98, and AS99 maps, represented in Fig. 5共b兲, shows that the average neighbor betweenness exhibits a clear power-law dependence on the node betweenness b, 具 bnn 典 ⬃b⫺ ␯ b,共12兲 with an exponent ␯ b⫽0.4⫾0.1, evidencing that the more loaded nodes 共backbones兲are more frequently connected with less loaded nodes 共local networks兲. These hierarchical properties of the Internet are likely driven by several additional factors such as the space locality, economical resources, and the market demand. An attempt to relate and study some of these aspects can be found in Ref. 关13兴, where the geographical distribution of population and Internet access are studied. In Sec. VII we shall compare a few of the existing models for the generation of scale-free networks with our data analysis, in an attempt to identify some relevant features in the Internet modeling. VI. DYNAMICS AND GROWTH In order to inspect the Internet dynamics, we focus our attention on the addition of new nodes and links into the maps. In the 3-yr range considered, we keep track of the number of links Lnew appearing between a newly introduced node and an already existing node. We also monitor the rate of appearance of links Lold between already existing nodes. In Table III we can observe that the creation of new links is FIG. 5. 共a兲Average connectivity 具 knn 典 of the nearest neighbors of a node as a function of the connectivity kfor the AS97, AS98, and AS99 maps. The full line has a slope ⫺0.5. 共b兲Average betweenness 具 bnn 典 of the nearest neighbors of a node as a function of its betweenness bfor the same maps. The full line has a slope ⫺0.4. VA ´ZQUEZ, PASTOR-SATORRAS, AND VESPIGNANI PHYSICAL REVIEW E 65 066130 066130-6 governed by these two processes at the same time. Specifically, the largest contribution to the growth is given by the appearance of links between already existing nodes. This clearly points out that the Internet growth is strongly driven by the need of redundancy in the wiring and an increased need of available bandwidth for data transmission. A customarily measured quantity in the case of growing networks is the average connectivity 具 ki(t) 典 of new nodes as a function of their age t. In Refs. 关15,31,32兴it is shown that 具 ki(t) 典 is a scaling function of both tand the absolute time of birth of the node t0. We thus consider the total number of nodes born within a small observation window ⌬t0, such that t0⯝const with respect to the absolute time scale that is the Internet lifetime. For these nodes, we measure the average connectivity as a function of the time telapsed since their birth. The data for two different time windows are reported in Fig. 6, where it is possible to distinguish two different dynamical regimes: At early times, the connectivity is nearly constant with a very slow increase. Later on, connectivity grows rapidly approaching what appears to be a power-law or faster growth regime. While reliable fits or exponent estimates are affected by noise and limited time window effects, the crossover between two distinct dynamical regimes is compatible with the general aging form obtained in the context of growing networks in Refs. 关31,32兴. A very important issue in the modeling of growing networks concerns the understanding of the growth mechanisms at the origin of the developing of new links. As we shall see more in detail in the following section, the basic ingredients in the modeling of scale-free growing networks is the preferential attachment hypothesis 关14兴. In general, all growing network algorithms define models in which the rate ⌸(k) with which a node with kconnections receives new links is proportional to k ␣ 共see Ref. 关14兴and Sec. VII兲. The inspection of the exact value of ␣ in real networks is an important issue since the connectivity properties strongly depend on this exponent 关31–33兴. Here we use a simple recipe that allows to extract the value of ␣ by studying the appearance of new links. We focus on links emanating from newly appeared nodes in different time windows ranging from one to three years. We consider the frequency ␮ (k) of links that connect to nodes with connectivity k. By using the preferential attachment hypothesis, this effective probability is ␮ (k) ⬃k ␣ pk(k). Since we know that pk(k)⬃k⫺ ␥ , we expect to find a power-law behavior ␮ (k)⬃k ␣ ⫺ ␥ for the frequency. In Fig. 7 we report the obtained results which show for the integrated frequency ␮ cum(k)⫽ 兰 k ⬁ ␮ (k⬘)dk⬘a behavior compatible with an algebraic dependence ␮ (k)⬃k⫺1.2. By using the independently obtained value ␥ ⫽2.2 we find a preferential attachment exponent ␣ ⯝1.0, in good agreement with the result obtained with a different analysis in Ref. 关33兴.We performed a similar analysis also for links emanated by existing nodes, recovering the same form of preferential attachment 共see Fig. 7兲. The present analysis confirms the validity of the preferential attachment hypothesis, but leaves open the question of the interplay with several other factors, such as the nodes’ hierarchy, space locality, and resource constraints. VII. MODELING THE INTERNET In the preceding section we have presented a thorough analysis of the AS maps topology. Apart from providing useful empirical data to understand the behavior of the Internet, our analysis is of great relevance in order to test the validity of models of the Internet topology. The Internet topology has a great influence on the information traffic carried on top of it, including routing algorithms 关16,17兴, searching algorithms 关18,19兴, virus spreading 关20兴, and resilience to node failure 关21–23兴. Thus, designing network models that accurately reproduce the Internet topology is of capital importance to carry out simulations on top of these networks. TABLE III. Monthly rate of new links connecting existing nodes to new (Lnew) and old (Lold) nodes. Year 1997 1998 1999 Lnew 183共9兲170共8兲231共11兲 Lold 546共35兲350共9兲450共29兲 Lnew /Lold 0.34共2兲0.48共2兲0.53共3兲 FIG. 6. Average connectivity of nodes borne within a small time window ⌬t0, after a time telapsed since their appearance. Time tis measured in days. FIG. 7. Frequency of links emanating from new and existing nodes that attach to nodes with connectivity k. The full line corresponds to a slope ⫺1.2, which yields an exponent ␣ ⯝1.0. The flat tails are originated from the poor statistics at very high kvalues. LARGE-SCALE TOPOLOGICAL AND DYNAMICAL... PHYSICAL REVIEW E 65 066130 066130-7 Early works considered the Erdo ¨s-Re ´nyi 关34兴model or hierarchical networks as models of the Internet 关35兴. However, they yield connectivity distributions with a fast 共exponential兲decay for large connectivities, in disagreement with the power-law decay observed in real data. Only recently the Internet modeling benefited of the major advance provided in the field of growing networks by the introduction of the Baraba ´si-Albert 共BA兲model 关14,15,36兴, which is related to 1955 Simon’s model 关37–39兴. The main ingredients of this model are the growing nature of the network and a preferential attachment rule, in which the probability of establishing new links toward a given node grows linearly with its connectivity. The BA model is constructed using the following algorithm 关14兴: We start from a small number m0of disconnected nodes; every time step a new node is added, with m links that are connected to an old node iwith probability ⌸BA共ki兲⫽ki 兺 jkj ,共13兲 where kiis the connectivity of the ith node. After iterating this procedure Ntimes, we obtain a network with a connectivity distribution pk(k)⬃k⫺3and average connectivity 具 k 典 ⫽2m. In this model, heavily connected nodes will increase their connectivity at a larger rate than less connected nodes, a phenomenon that is known as the ‘‘rich-get-richer’’ effect 关14兴. It is worth remarking, however, that more general studies 关4,31,32兴have revealed that nonlinear attachment rates of the form ⌸(k)⬃k ␣ with ␣ ⫽1 have as an outcome connectivity distributions that depart form the power-law behavior. The BA model has been successively modified with the introduction of several ingredients in order to account for connectivity distribution with 2⬍ ␥ ⬍3关31,32,40兴, local geographical factors 关41兴, wiring among existing nodes 关42兴, and age effects 关43兴. In the preceding section we have analyzed different measures that characterize the structure of AS maps. Since several models are able to reproduce the right power law behavior for the connectivity distribution, the analysis obtained in the previous sections can provide the effective tools to scrutinize the different models at a deeper level. In particular, we perform a data comparison for three different models that generate networks with power-law connectivity distributions. First we have considered a random graph with a power-law connectivity distribution, constructed using the Molloy and Reed 共MR兲algorithm 关44,45兴. Secondly, we have studied two variations of the BA model, that yield connectivity exponents compatible with the one measured in the Internet: the generalized Baraba ´si-Albert 共GBA兲model 关40兴, which includes the possibility of connection rewiring, and the fitness model 关46兴, that implements a weighting of the nodes in the preferential attachment probability. The models are defined as follows: MR model. In the construction of this model 关4,44,45,47兴 we start assigning to each node iin a set of Nnodes a random connectivity kidrawn from the probability distribution pk(k)⬃k⫺ ␥ , with m⭐ki⬍N, imposing the constraint that the sum 兺ikimust be even. The graph is completed by randomly connecting the nodes with 兺iki/2 links, respecting the assigned connectivities. The results presented here are obtained using m⫽1 and a connectivity exponent ␥ ⫽2.2, equal to that found in the AS maps. Clearly this construction algorithm does not take into account any correlations or dynamical features of the Internet and it can be considered as a first order approximation that focuses only on the connectivity properties. GBA model. It is defined by starting with m0nodes connected in a ring 关40兴: At each time step one of the following operations is performed: 共i兲With probability qwe rewire mlinks. For each of them, we randomly select a node iand a link lij connected to it. This link is removed and replaced by a new link li⬘jconnecting the node jto a new node i⬘selected with probability ⌸(ki⬘) where ⌸GBA共ki兲⫽ki⫹1 兺 j共kj⫹1兲 .共14兲 共ii兲With probability pwe add mnew links. For each of them, one end of the link is selected at random, while the other is selected with probability as in Eq. 共14兲. 共iii兲With probability 1⫺q⫺pwe add a new node with m links that are connected to nodes already present with probability as in Eq. 共14兲. The preferential attachment probability Eq. 共14兲leads to a power-law distributed connectivity, whose exponent depends on the parameters qand p. In the particular case p⫽0, the connectivity exponent is given by 关40兴 ␥ ⫽1⫹共1⫺q兲共2m⫹1兲 m.共15兲 Hence, changing the value of mand qwe can obtain the desired connectivity exponent ␥ . In the present simulations we use the values m⫽2 and q⫽13/25, that yield the exponent ␥ ⫽2.2. The GBA model embeds both the rich-getricher paradigm and the growing nature of the Internet; however, it does not take into account any possible difference or hierarchies in newly appearing nodes. Fitness model. This network model introduces an external competence among nodes to gain links, that is controlled by a random 共fixed兲fitness parameter ␩ ithat is assigned to each node ifrom a probability distribution ␳ ( ␩ ). In this case, we also start with m0nodes connected in a ring and at each time step we add a new node i⬘with mlinks that are connected to nodes already present on the network with probability ⌸fitness共ki兲⫽ ␩ iki 兺 j ␩ jkj .共16兲 The newly added node is assigned a fitness ␩ i⬘. The results presented here are obtained using m⫽2 and a probability ␳ ( ␩ ) uniformly distributed in the interval 关0,1兴, which yields a connectivity distribution pk(k)⬃k⫺ ␥ /lnkwith ␥ ⬇2.26 关46兴. The fitness model adds to the growing dynamics with VA ´ZQUEZ, PASTOR-SATORRAS, AND VESPIGNANI PHYSICAL REVIEW E 65 066130 066130-8 preferential attachment a stochastic parameter, the fitness, that embeds all the properties, other than the connectivity, that may influence the probability of gaining new links. We have performed simulations of these three models with the parameters mentioned above and using sizes of N ⯝4000 nodes, in analogy with the size of the AS maps analyzed. In each case we perform averages over 1000 different realizations of the networks. It is worth remarking that while the fitness model generates a connected network, both the GBA and the MR model yield disconnected networks. This is due to the rewiring process in the GBA model, while the disconnect nature of the graph in the MR model is an inherent consequence of the connectivity exponent being larger that 2 关47兴. In these two cases we therefore work with graphs whose giant component 共that is, the largest cluster of connected nodes in the network 关27兴兲 has a size of the order N. It is important to remind the reader that we are working with networks of a relatively small size, chosen so as to fit the size of the Internet maps analyzed in the previous sections. In this perspective, all the numerical analysis that we shall perform in the following serve only to check the validity of the models as representations of the Internet as we know it, and do not refer to the intrinsic properties of the models in the thermodynamic limit N→⬁. As a first check of the connectivity properties of the models, in Fig. 8 we have plotted the respective integrated connectivity distributions. For the MR model we recover the expected exponent ␥ MR⯝2.20, since it was imposed in the very definition of the model. For the GBA model we obtain numerically ␥ GBA⯝2.19 for the giant component, in excellent agreement with the value predicted by Eq. 共15兲for the asymptotic network. For the fitness model, on the other hand, a numerical regression of the integrated connectivity distribution yields an effective exponent ␥ fitness⯝2.4. This value is larger than the theoretical prediction 2.26 obtained for the model 关46兴. The discrepancy is mainly due to the logarithmic corrections present in the connectivity distribution of this model. These corrections are more evident in the relatively small-sized networks used in this work and become progressively smaller for larger network sizes. In Table IV we report the average values of the connectivity, clustering coefficient, path length, and betweenness for the three models, compared with the respective values computed for the Internet during 1998. From the examination of this table, one could surprisingly conclude that the MR model, which neglects by construction any correlation among nodes, yields the average values in better agreement with the Internet data. As we can observe, the fitness model provides too small a value for the average clustering coefficient, while the GBA model clearly fails for the average path length and the betweenness. A more crucial test about the models is however provided by the analysis of the full distribution of the various quantities, that should reproduce the scale-free features of the real Internet. The betweenness distribution pb(b) of the three models give qualitatively similar results. The integrated betweenness distribution Pb(b) obtained is plotted in Fig. 9共a兲. Both the MR and the fitness models follow a power-law decay pb(b)⬃b⫺ ␦ with an exponent ␦ ⯝2, in agreement with the value obtained from the AS maps. The GBA model shows an appreciable bending that, nevertheless, is compatible with the experimental Internet behavior. These results are in agreement with the numerical prediction in Ref. 关30兴and support the conjecture that the exponent ␦ ⯝2.2 is a universal quantity in all scale-free networks with 2⬍ ␥ ⬍3. In order to further inspect the betweenness properties, we plot in Fig. 9共b兲the average betweenness bkas a function of the connectivity. In this case, the MR and GBA models yield an exponent ␤ ⯝1, compatible with the AS maps, while the fitness model exhibits a somewhat larger exponent, close to 1.4. Also in this case, we have that the finite size logarithmic corrections present in the fitness model could play a determinant role in this discrepancy. While properties related to the betweenness do not appear to pinpoint a major difference among the models, the most striking test is provided by analyzing the correlation properties of the models. In Figs. 10 and 11, we report the average clustering coefficient as a function of the connectivity, ck, and the average connectivity of the neighbors, 具 knn 典 , respectively. The data from the Internet maps show a nontrivial k structure that, as discussed in previous sections, is due to scale-free correlation properties among nodes. These properties depend on their turn upon the underlying hierarchy of the Internet structure. The only model that renders results in qualitative agreement with the Internet maps is the fitness model. On the contrary, the MR and GBA models completely FIG. 8. Integrated connectivity distribution for the MR, GBA, and fitness models, compared with the result from the AS98 map. The full line has slope ⫺1.2. TABLE IV. Average properties of the MR, GBA, and fitness models, compared with the values from the Internet in 1998. 具 k 典 , average connectivity; 具 c 典 , average clustering coefficient; 具 l 典 , average path length; 具 b 典 , average betweenness. Figures in parentheses indicate the statistical uncertainty from the average of 1000 realizations of the models. MR GBA Fitness 1998 具 k 典 4.8共1兲5.4共1兲4.00共1兲3.6共1兲 具 c 典 0.16共1兲0.12共1兲0.02共1兲0.21共3兲 具 l 典 3.1共1兲1.8共1兲4.0共1兲3.8共1兲 具 b 典 /N2.2共1兲1.9共1兲2.1共1兲2.3共1兲 LARGE-SCALE TOPOLOGICAL AND DYNAMICAL... PHYSICAL REVIEW E 65 066130 066130-9