A key ingredient of current models proposed to capture the topological evolution of complex networks is the hypothesis that highly connected nodes increase their connectivity faster than their less connected peers, a phenomenon called preferential attachment. Measurements on four networks, namely the science citation network, Internet, actor collaboration and science coauthorship network indicate that the rate at which nodes acquire links depends on the node's degree, offering direct quantitative support for the presence of preferential attachment. We find that for the first two systems the attachment rate depends linearly on the node degree, while for the latter two the dependence follows a sublinear power law. PACS numbers: 89.65.-s, 89.75.-k, 05.10.-a Modeling the highly interconnected nature of various social, biological and communication systems as complex networks or graphs has attracted much attention in the last few years. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] . As for a long time these networks were modeled as completely random [15, 16] , the recent interest is motivated by the increasing evidence that real network display short length-scale clustering [1, 2] and obey unexpected scaling laws [3, 4] , interpreted as signatures of deviation from randomness. Current approaches, using the tools of statistical physics [6, 8, 9 ] search for universalities both in the topology of these webs and in the dynamics governing their evolution. These efforts resulted in a class of models that view networks as evolving dynamical systems, rather than static graphs. Most evolving network models [4, 6, 9] are based on two ingredients [4]: growth and preferential attachment. The growth hypothesis suggests that networks continuously expand through the addition of new nodes and links between the nodes, while the preferential attachment hypothesis states that the rate Π(k) with which a node with k links acquires new links is a monotonically increasing function of k. While most versions of such evolving network models assume that Π(k) is linear in k [4,6,9], recently several authors proposed that Π(k) could follow a power-law [8, 10] . Consequently, the time evolution of the degree k i of node i can be obtained from the first order differential equation where m is a constant and Π(k) has the form with α > 0 an unknown scaling exponent. For α = 1 these models reduce to the scale-free model [4] , for which the degree distribution P (k), giving the probability that a node has k links, follows P (k) ∝ k −γ with γ = 3. As Krapvisky, Redner and Leyvraz have shown [8], for α < 1 the degree distribution follows a stretched exponential, while for α > 1 a gelation-like phenomenon is expected, where a single site links to nearly all other nodes. On the other hand the hypothesis (2) Here we offer the first direct attempt to answer these questions in quantitative terms by proposing a numerical method that allows us to extract the functional form of Π(k) directly from dynamical data on real evolving networks. Our measurements indicate that Π(k) follows a power law for all investigated networks. For the Internet and the citation network we find α = 1, while for the science collaboration network and the Hollywood actor network the results indicate sublinear attachment, i.e. α < 1. These results offer the crucial missing link for modeling the dynamics of complex evolving networks. Methods: To measure Π(k) we use computerized data on the dynamics of large networks. Consider a network for which we know the order in which each node and link joins the system. According to (1) and (2) the function Π(k) gives the rate at which an existing node with k links acquires new links as the network grows. To measure Π(k) we need to monitor to which old node new nodes link to, in function of the degree of the old node. However, there is an important problem with this simple approach: the normalization constant, C(t), depends on the time at which a given node joins the system, creating unwanted biases in the measurements. To avoid such bias we study the attachment of new nodes within a relatively short time-frame. Consider all nodes existing in the system at time T 0 , called "T 0 nodes". Next select a group of "T 1 nodes", added between [T 1 , T 1 + ∆T ], where 1
Jeong et al. REF found that the attachment probability of a node solely depends on its degree, once again confirming preferential attachment.
Measuring preferential attachment in evolving networks
Europhysics Letters (EPL)
Europhysics Letters (EPL)
Physics Computer Science