{'fraction_non_alphanumeric': 0.043869632695292295, 'fraction_numerical': 0.013071219175719951, 'mean_word_length': 4.087376085621545, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Organization of Growing Random Networks

The organizational development of growing random networks is investigated. These growing networks are built by adding nodes successively and linking each to an earlier node of degree k with attachment probability A_k. When A_k grows slower than linearly with k, the number of nodes with k links, N_k(t), decays faster than a power-law in k, while for A_k growing faster than linearly in k, a single node emerges which connects to nearly all other nodes. When A_k is asymptotically linear, N_k(t) tk^{-nu}, with nu dependent on details of the attachment probability, but in the range 2<nu<infty. The combined age and degree distribution of nodes shows that old nodes typically have a large degree. There is also a significant correlation in the degrees of neighboring nodes, so that nodes of similar degree are more likely to be connected. The size distributions of the in-components and out-components of the network with respect to a given node -- namely, its"descendants"and"ancestors"-- are also determined. The in-component exhibits a robust s^{-2} power-law tail, where s is the component size. The out component has a typical size of order ln t and it provides basic insights about the genealogy of the network.

The organizational development of growing random networks is investigated. These growing networks are built by adding nodes successively and linking each to an earlier node of degree k with attachment probability A k . When A k grows slower than linearly with k, the number of nodes with k links, N k (t), decays faster than a power law in k, while for A k growing faster than linearly in k, a single node emerges which connects to nearly all other nodes. When A k is asymptotically linear, N k (t) ∼ tk −ν , with ν dependent on details of the attachment probability, but in the range 2 < ν < ∞. The combined age and degree distribution of nodes shows that old nodes typically have a large degree. There is also a significant correlation in the degrees of neighboring nodes, so that nodes of similar degree are more likely to be connected. The size distributions of the in-components and out-components of the network with respect to a given node -namely, its "descendants" and "ancestors" -are also determined.

I. INTRODUCTION
Networks of many interacting units play an important role in epidemiology, ecology, gene regulation, neural networks, and many other fields [1][2][3]. In many studies of these networks, the number of nodes is considered to be fixed and the presence of a link between two nodes is treated as a random event independent of the other links. These assumptions lead naturally to random graph models [4,5]. While these models have rich behavior and considerable utility, they are not necessarily appropriate for describing growing networks, where the addition of nodes and links may depend on the local features of the network where the growth event is taking place.
Typical examples of such growing networks include transportation or electrical distribution systems, where growth occurs in response to population-driven demands. Two currently appealing examples are the distribution of scientific citations and the structure of the world-wide web. For both these examples there is now considerable data available, in spite of the very rapid growth of these systems. In the former case, one may consider papers to be the nodes of a graph and citations as the links. The structure of the resulting "citation graph" was originally studied by Lotka in 1926 [6], and then by many others [7][8][9][10][11][12][13]. The basic feature of this citation distribution is that it appears to have a relatively steep power-law tail; thus most papers are minimally cited while highly-cited papers are rare.
Similarly, in the web graph, much structural data has recently been obtained [14][15][16][17][18][19][20][21] which suggest that the number of nodes with k links has a power-law tail, with an exponent that is somewhat larger than 2. This powerlaw tail again corresponds to the basic fact that most nodes of the web graph are unimportant, while a relatively small number of nodes garner a large fraction of "hits". Due to the qualitative similarities between the citation and web graphs, insights developed in the field of bibliometrics [9] have been applied to help understand the structure of the web [22].
Because of the dynamic nature of the citation and web graphs, it is not surprising that their topologies at any fixed time are very different from classical random graphs. In distinction to the power-law degree distributions of the citation and web graphs, random graphs have a Poisson node degree distribution. Here node degree is defined as the number of links at a node. To overcome the shortcomings of random graphs in describing the dynamic natures of these systems, both "small-world" networks [23,24] and growing random network models [20,[25][26][27][28] have been recently introduced. The former are aimed at understanding the relatively small diameter of large graphs of socially interacting units, while the latter seek to understand the growth dynamics.
In this paper, we provide a comprehensive quantitative description of a simple growing network (GN) model. Our results are based on the analysis of the rate equations for the densities of nodes of a given degree. This approach bears many similarities to the rate equations for the kinetics of aggregation. The rate equations for the evolution of growing networks are relatively simple and the results that emerge are comprehensive. Thus it appears that the rate equation method is better suited for probing the structure of growing random networks compared to the classical approaches for analyzing random graphs, such as probabilistic [4] or generating function [5] techniques. The rate equation approach also has the advantage that it can be adapted to other evolving graph systems, including networks with addition and deletion of nodes and links, as well as networks with link re-wiring.
We will specifically investigate two types of models: (a) the GN in which nodes are added one at a time and a link is established with a pre-existing node according to an attachment probability A k which depends only on the degree of the target node (Fig. 1), and (b) the GN with re-direction (GNR), in which the newly-created link can be re-directed to the "ancestor" node of the original target node. An important feature of these models is that the links are directed and the resulting graphs have a simple tree-like topology. The motivation for the GNR model is that this re-direction process roughly mimics how we might (lazily) construct the references to this paper. In addition to papers that we peruse and cite directly, we are also likely to incorporate some of the references within these papers as part of our reference list. A related "copying" process also affects the organization of the web [15]. Schematic illustration of the evolution of the growing random network. Nodes are added sequentially and a single link joins the new node to an earlier node. In this example, node 1 has degree 5, node 2 has degree 3, nodes 4 and 6 have degree 2, and all the remaining nodes have degree 1. Also note that node 1 is the "ancestor" of 6, while 10 is the descendant of 6.
One of our primary results is that for asymptotically linear attachment kernels, A k ∼ k as k → ∞, the degree distribution of the GN has a power-law form N k (t) ∼ tk −ν , with ν tunable in the range 2 < ν < ∞. By choosing the control parameters of our model in a plausible manner it is then easy to reproduce the quantitative observations about the node degree distribution of the web graph.
In Sec. II, we define the GN and GNR models precisely and then determine their node degree distributions in Sec. III by the rate equation approach. Different distributions arise in the GN model which depend on the asymptotic behavior of the attachment probability as a function of node degree. In Sec. IV, we investigate the joint age-degree distribution and find (not surprisingly) that "old" nodes are typically more highly connected. In Sec. V, we study the correlations which develop between the degrees of connected nodes as the network grows. In Sec. VI, we study a more global measure of the network, namely, the size distributions of the "in-component" and "out-component". With respect to a given node x, the incomponent is the set of nodes which can reach node x via a directed path of links. Conversely, the out-component is the set nodes which can be reached from node x via a directed path. The former exhibits a robust power-law size distribution which appears to be independent of the attachment probability. The latter distribution predicts a network "diameter" which grows as ln t and also provides basic insights about the genealogy of the network. We conclude in Section VII.

A. Growing Network (GN)
In the GN, we introduce a new node at each time step and link it to one of the earlier nodes in the network (Fig. 1). This leads to a network which has a topology of a (directed) tree graph. In terms of citations, we may interpret the nodes as publications, and the directed link from one paper to another as a citation to the earlier publication. In terms of the web graph, nodes are web pages and the directed links are hyperlinks. We will refer to the node to which the link is directed as the ancestor of the current node.
As the network grows, a degree distribution N k (t), defined as the average number of nodes with k links (k − 1 incoming and 1 outgoing) builds up. The initial node is unique as it does not have an outgoing link. The basic ingredient which determines the structure of the network is the attachment kernel A k , defined as the probability that the newly-introduced node links to an existing node which already has k links. On general grounds, this attachment kernel should be a non-decreasing function of k, and natural scenarios are attachment kernels with a power law dependence on k. For the linear kernel, the GN reduces to the "scale free" model introduced by Barabási and Albert [20] and further investigated in [25][26][27].
The general homogeneous model, A k = k γ with γ ≥ 0, was investigated in [28] where it was found that the degree distribution N k (t) crucially depends on the value of γ. For γ < 1, the linking probability grows weakly with node "popularity" and N k (t) decreases as a stretched exponential in k for any t. The complementary case of γ > 1 leads to phenomenon akin to gelation [29] in which a single "gel" node links to nearly every other node. For γ > 2, this phenomenon is so extreme that the number of links between other nodes is finite in an infinite graph. We shall show that these results also apply for the more general situation where A k ∼ k γ as k → ∞ in addition to the strictly homogeneous situation where A k = k γ .
The borderline case of an asymptotically linear attachment kernel, A k ∼ k, is particularly intriguing as it leads to N k ∼ k −ν , with the exponent ν tunable to any value larger than 2 depending on finer details of the attachment kernel. In particular, the strictly linear kernel, A k = k, leads to ν = 3. However, by changing the value of a single attachment probability, for example A 1 = α and A k = k for k > 2, any value of ν > 2 is possible. This sensitivity of asymptotic behavior on microscopic details indicates that the case of attachment index γ = 1 is marginal. A related phenomenon occurs in constant-kernel aggregation, where the asymptotic kinetics is sensitively dependent on the actual values of the reaction rate [30,31].

B. Growing Network with Re-direction (GNR)
The GN is built by simultaneous node and link addition and disregards other elemental processes which can occur in the development of large networks. In the context of the web, these include node and link deletion (for out-of-date websites), link re-wiring, the tendency of a new node to connect to nearby nodes, and the copying of links from existing nodes to new nodes. The GNR model incorporates a simple form of link re-wiring into the GN model. At each time step, a new node n is added and an earlier node x is selected uniformly as a possible "target" for attachment. With probability 1 − r, the link from n to x is created; in this case, the evolution is the same as in the GN. However, with probability r, the link is re-directed to the ancestor node y of node x (  A model of this spirit was recently mentioned in the context of the web development [15]. A related model was also proposed long ago by Simon [32,33] to describe the word frequencies of English text. The Simon model gives a power-law frequency distribution whose exponent is tunable in manner which closely mirrors the behavior in the GNR model. The Simon model was also recently applied to explain power-law distributions in the frequency of family names [34].
While at first sight the GNR model appears complicated, we shall see that its characteristics can be obtained in a simple fashion. Another very helpful and surprising property of the GNR with a uniform initial attachment probability is that it is equivalent to the GN with a shifted linear attachment kernel and no re-direction. We shall exploit this equivalence extensively in the following. Nevertheless, we consider the GNR separately, as in many cases the rate equations for the GNR with a uniform attachment kernel is simpler to appreciate than the rate equations for the GN with a shifted linear attachment kernel.

A. GN Model
We now study the evolution of the degree distribution of the GN model. The rate equations for N k (t) are The first term on the right-hand side of Eq. (1) accounts for the process in which a node with k − 1 links is connected to the new node, leading to a gain in the number of nodes with k links. This happens with probability  [35], additive polymerization [36], hydrolysis [37], catalysis and submonolayer epitaxial growth [38], fit into this scheme. However, there is one important difference in that we consider strictly a single connected cluster (the growing network), while in the context of aggregationlike processes, one generally deals with a collection of clusters. The effect of having more than one cluster in the framework of growing networks is currently under investigation [39].
We start by solving the equations for the low-order moments of the degree distribution, which are defined by M n (t) = j≥1 j n N j (t). Summing Eqs. (1) over all k gives the rate equation for the total number of nodes, M 0 = 1, whose solution is M 0 (t) = M 0 (0) + t. The first moment (the total number of link endpoints) obeyṡ M 1 = 2, which gives M 1 (t) = M 1 (0) + 2t. The first two moments are therefore independent of the attachment kernel A k , while higher moments and the degree distribution itself do depend on the kernel A k .
To develop an appreciation for the types of behavior that can occur, consider the linear kernel A k = k for which A(t) coincides with M 1 (t). In this case, we can solve Eqs. (1) for an arbitrary initial condition. However, since the long-time behavior is most interesting we limit ourselves to the asymptotic regime (t → ∞) where the initial condition is irrelevant. Using therefore M 1 = 2t, we solve the first few of Eqs. (1) and obtain N 1 = 2t/3, N 2 = t/6, etc., which implies that the N k grow linearly with time. Accordingly, we substitute N k (t) = t n k in Eqs. (1) to yield the simple recursion relation n k = n k−1 (k − 1)/(k + 2). Solving for n k gives n k = 4 k(k + 1)(k + 2) . (2) In the context of discrete functions defined on the positive integers, this distribution is algebraic over the entire range of k. Indeed, as explained in Ref. [40], the proper analog of the continuous power-law function f (x) = x −λ is the discrete function f k = Γ(k)/Γ(k + λ), where Γ is the Euler gamma function. Rewriting Eq. (2) as n k = 4Γ(k)/Γ(k + 3), we see that n k is indeed algebraic over the entire range k ≥ 1.
Returning to more general attachment kernels, let us assume that the degree distribution and A(t) both grow linearly with time. We anticipate that this hypothesis will hold for attachment kernels which do not grow faster than linearly with k. By substituting N k (t) = t n k and A(t) = µt into Eqs. (1) we obtain the recursion relation n k = n k−1 A k−1 /(µ + A k ) and n 1 = µ/(µ + A 1 ). Solving for n k , we obtain To complete the solution, we need to find the amplitude µ. Combining the definition µ = j≥1 A j n j and Eq. (3), we obtain the implicit relation Thus the amplitude µ always depends on the entire attachment kernel. On the other hand, we shall show that the degree distribution exhibits a robust behavior which depends only on gross features of the attachment kernel, as long as A k grows slower than linearly. The case where A k is asymptotically linear is perhaps the most intriguing as the degree distribution has a power-law behavior whose exponent depends on microscopic details of the dependence of A k on k. When A k grows faster than linearly, drastically different gelation-like behavior arises. It is again worth noting that these three regimes of kinetic behavior also arise in the solutions to the rate equations for additive polymerization processes, with the different regimes arising when the attachment exponent γ is smaller than, larger than, or equal to one [41]. We now separately describe these three cases.

Sub-linear kernels
Consider sub-linear kernels which are asymptotically homogeneous, that is, A k ∼ k γ , with 0 < γ < 1. Substituting this asymptotics into Eq. (3), writing the product as the exponential of a sum, converting the sum to an integral, and performing this integral, we obtain etc.. The pattern given in Eq. (5) continues ad infinitum: Whenever γ decreases below 1/m, with m a positive integer, an additional term in the exponential arises from the now relevant contribution of the next higher-order term in the expansion of the product in Eq. (3). To complete the solution, we require the amplitude µ. We have been unable to find an explicit expression for µ, even if the attachment kernel is strictly homogeneous, A k = k γ , as it requires solving Eq. (4). However, this relation can be easily evaluated numerically and it shows that µ(γ) varies smoothly between 1 and 2 as γ increases from 0 to 1 (Fig. 3). These two limits correspond to the known limiting behaviors for M 0 and M 1 .
More detailed results can be obtained for the limiting solvable cases of A k = const. and A k = k. In these limits, µ = 1 and µ = 2, respectively, and the corresponding degree distributions are given by n k = 2 −k and by Eq. (2). The former can be easily obtained by following exactly the same steps as those used to solve the network with the linear kernel. We can then apply perturbation theory to find the respective limiting behaviors of µ(γ) for γ close to 0 or 1,

Linear kernels
Consider now asymptotically linear attachment kernels, A k ∼ k as k → ∞. As already mentioned, we can always choose the amplitude in the asymptotic relation equal to one, as attachment kernels which differ by a multiplicative factor give identical behavior. For the asymptotically linear kernel, expanding the product in Eq. (3) and following step-by-step the approach that led to Eq. (5) now gives the power-law asymptotic behavior An important feature of this result is that the exponent ν can be tuned to any value larger than 2. This lower bound immediately follows from the fact that the sum µ = j A j n j ∼ j jn j must converge and this, in turn, requires that ν must be larger than 2.
As an explicit example, consider the attachment kernel A k = k for k ≥ 2, while A 1 ≡ α is an arbitrary positive number. Now it is convenient to separately treat A 1 and A k for k ≥ 2 in Eq. (4) to recast it as The right-hand side of Eq. (7) can be simply expressed as the ratio of Euler gamma functions to yield This sum can be evaluated by employing the identity [40] ∞ k=2 Γ(a + k) so that Eq. (8) reduces to µ(µ − 1) = 2α, with solution µ = (1 + √ 1 + 8α)/2. Thus the exponent ν = 1 + µ is Furthermore, following the steps that lead to Eq. (3), the degree distribution for the GN with the attachment kernel A 1 = α and A k = k for k ≥ 2 is Notice that for 0 < α < 1, the exponent lies in the range 2 < ν < 3; in particular, ν = 2 + 2α − 4α 2 + . . . as α → 0. When α = 1, we recover the connectively distribution of Eq. (2). For α > 1, we have ν > 3; in particular, ν → √ 2α as α → ∞. The GN is also solvable when A k = k + w. This shifted linear kernel can be motivated naturally by explicitly keeping track of the directionality of the links.
In particular, the node degree for an undirected graph generalizes to the in-degree and out-degree for a directed graph. These are just the number of incoming and outgoing links at a node, respectively. Thus, the node degree k in a directed graph is the sum of the in-degree i and outdegree j. The most general linear attachment kernel for a directed graph is therefore of the form A ij = ai + bj. The GN corresponds to the case where the out-degree of any node equals one; thus j = 1 and k = i+1. Hence the general linear attachment kernel reduces to A k = a(k−1)+b. Since, as mentioned above, the overall scale factor in the kernel is irrelevant, we can re-write A k as the shifted linear kernel A k = k + w, with w = −1 + b/a, so that it can vary over the range −1 < w < ∞.
We can now easily determine the degree distribution for the shifted linear attachment kernel. First we note that A(t) = j A j N j = M 1 (t) + wM 0 (t). Then using the basic results A = µt, M 0 = t and M 1 = 2t, we have µ = 2 + w and thence ν = 3 + w, according to Eq. (6). Furthermore, from Eq. (3) we easily determine the entire degree distribution to be In a similar vein, we can solve the GN with an arbitrary piecewise linear attachment kernel. In all these cases, the exponent ν can be tuned to any value larger than 2, and for sufficiently large degree n k can be expressed as the ratio of gamma functions, i. e., the degree distribution is a purely (discrete) algebraic function.

Super-linear kernels
For the super-linear homogeneous attachment kernels, A k = k γ with γ > 1, we now show that a "winner take all" phenomenon arises, namely, there emerges a single dominant "gel" node which is linked to almost every other node. A particularly singular behavior occurs for γ > 2, where there is a non-zero probability that the initial node is connected to every other node of the network.
Let us first determine the probability that the initial node connects to all other nodes. It is convenient to consider a discrete time version of the GN in which one node is introduced at each elemental step which always links to the initial node. After N steps, the probability that the new node will link to the initial node is N γ /(N + N γ ). This probability that this connectivity pattern continues indefinitely is Clearly, P = 0 when γ ≤ 2 but P > 0 when γ > 2. Thus for γ > 2 there is a non-zero probability that the initial node connects to all other nodes.
To determine the behavior for general γ > 1, we first need the asymptotic time dependence of M γ . To this end, it is useful to consider the discretized version of the master equations Eq. (1), where the time t is limited to integer values. Then N k (t) = 0 whenever k > t and the rate equation for N k (k) immediately leads to From this, and the obvious fact that N k (k) must be less than unity, it follows that M γ (t) cannot grow more slowly than t γ . On the other hand, M γ (t) cannot grow faster than t γ , as follows from the estimate Thus M γ ∝ t γ . In fact, the amplitude of t γ is unity as we will derive self-consistently after solving for the N k 's. We now use M γ ∼ t γ , with γ > 1, in the rate equations to solve recursively for each N k . Starting with the equationṄ 1 = 1 − N 1 /M γ , we see that the second term on the right-hand side is sub-dominant. Thus by neglecting this term we obtain N 1 = t. Similarly, Continuing this same line of reasoning for each successive rate equation gives the leading behavior of N k , . This pattern of behavior for N k continues as long as its exponent k − (k − 1)γ remains positive, or k < γ/(γ − 1). The full temporal behavior of the N k (t) may be determined straightforwardly by keeping the next correction terms in the rate equations. For example, For k > γ/(γ − 1), each N k has a finite limiting value in the long-time limit. Since the total number of connections equals 2t, and t of them are associated with N 1 , the remaining t links must all connect to a single node which has t connections (up to corrections which grow no faster than sub-linearly with time). Consequently the amplitude of M γ equals unity, as argued above.
Therefore for super-linear kernels, the GN undergoes an infinite sequence of connectivity transitions as a function of γ. For γ > 2 all but a finite number of nodes are linked to the "gel" node which has the rest of the links of the network. This is the "winner take all" situation. For 3/2 < γ < 2, the number of nodes with two links grows as t 2−γ , while the number of nodes with more than two links is again finite. For 4/3 < γ < 3/2, the number of nodes with three links grows as t 3−2γ and the number with more than three is finite. Generally for m+1 m < γ < m m−1 , the number of nodes with more than m links is finite, while N k ∼ t k−(k−1)γ for k ≤ m. Logarithmic corrections also arise at the transition points.

B. Relation to citation data
Let us now attempt to relate some of our predictions from the GN model to the distribution of citations in recent scientific publications [11,12]. The GN model represents an extreme idealization of the citation process in which each publication cites only a single paper and the probability of citing a paper depends only on its current number of citations, and not on its intrinsic quality or any other realistic features. Thus we anticipate that the connection between the model and the data will be, at best, tenuous.
The data that we discuss is based on: (a) 783,339 papers with 6,716,198 citations (provided by the Institute of Scientific Information (ISI)), and (b) 24,296 papers with 351,872 citations from all issues of Physical Review D (PRD) from 1975-1994 (provided by the SPIRES database) [42]. A cursory visual inspection of this data suggests that the number of publications with k citations decays as a stretched exponential function of k (see e. g., Fig. 1 of Ref. [12]). However, an analysis based on presenting the data in a Zipf plot, in conjunction with scaling, is suggestive of a power-law form for the citation distribution, k −ν , with ν ≈ 3 (Fig. 2 of Ref. [12]). This ambiguity between a stretched exponential and powerlaw form for the citation distribution corresponds to the situation where the predictions of the GN itself are difficult to discern numerically.
If we consider the GN with attachment kernel A k ∼ k γ for γ < ∼ 1, then a plot of n k in Eq. (5) versus k, for 1 ≤ k ≤ 1000, changes relatively slowly as γ varies in the range (0.9, 1). If one attempts to fit this data to a power law, then an exponent value somewhat larger than 3 gives a reasonable fit to the data. It is only as γ → 1 from below, however, that the factors in the exponential of Eq. (5) conspire to give a pure power-law form for n k . Because of the relatively small change in n k as γ varies, the relatively incomplete data on the distribution of citations is insufficient to provide a clear test for the existence of a power law. Further, for the GN model with linear attachment kernel, the degree distribution depends on additional details of this kernel and can achieve any value greater than 2. In short, it is difficult to relate the GN model to citation data based on the form of the distribution alone.
Another interesting aspect of the citation distribution which can be compared with the GN model is the nature of highly-cited publications. Within the GN model, the degree of the most popular node, k max , may be determined by the extreme statistics criterion k>kmax N k = 1, which states that there is one node in the network whose degree lies in the range (k max , ∞). This criterion gives asymptotically linear; t γ > 1.
We now compare this prediction with the data about the most-cited paper. To make a correspondence between citations and Eq. (17), we identify the total number of publications in each dataset with t. The most cited paper had 8,904 citations in the ISI data set and 2,026 citations in the PRD data set. These results are consistent with the first line of Eq. (17) when γ ≈ 0.86 and γ ≈ 0.7 respectively, and also with the second line for ν ≈ 2.5 and ν ≈ 2.3 respectively. Thus an analysis of the most-cited paper does not cleanly indicate whether the citation distribution is a power law or a stretched exponential.
These ambiguities indicate some of the issues that should be be clarified to provide a clear description of citations in terms of a growing network model.

C. GNR Model
We now solve the GNR model within the rate equation framework. According to the basic processes in the model (Fig. 2), the degree distribution N k (t) evolves by the rate equations For re-direction probability r = 0, the first three terms on the right-hand side of Eqs. (18) are the same as in the GN. The last two terms account for the change in N k due to the re-direction process. To understand their origin, consider the gain term due to re-direction. Since the initial node is chosen uniformly, if re-direction does occur, the probability that a node with k − 1 pre-existing links receives the new "re-directed" link is proportional to k − 2, the number of pre-existing incoming links. A similar argument applies for the re-direction-driven loss term. Since N 0 ≡ 0 is tacitly assumed, Eq. (18) applies for all k ≥ 1. By combining the terms in Eq. (18), the rate equation reduces to that of the original GN with A k = (k − 1)r + 1 − r = r[k − 1 + (1 − r)/r]. By scaling out the factor r, we then reduce A k to the shifted linear kernel k + w, with w = (1 − r)/r − 1 = 1 r − 2. Thus we can merely transcribe our results about the GN with the shifted linear kernel to determine the degree distribution for the GNR model. Amusingly, for r = 1/2, the GN R model is identical to the GN with the purely linear kernel. In general, the degree distribution in the R model is a power law with exponent ν = 1 + 1/r, which can be tuned to any value larger than 2. This exponent value was first obtained in Simon's original paper [32], but in a rather different context, by employing an approach which is similar to ours.

IV. THE AGE DISTRIBUTION
In addition to the distribution of degree, we study when connections occur in the GN. This provides a deeper understanding of the overall development of growing networks. Naively, we expect that older nodes will be better connected and this can be quantified by categorizing nodes both by their degree and their age. It should be emphasized, that the GN does not have explicit aging, in which the connection probability depends on the age of the target node; this feature is treated in Ref. [26]. Instead, we are merely extending the categorization of node to include their age as well as their degree.

A. Linear connection kernel
Let c k (t, a) be the average number of nodes of age a which have k − 1 incoming links at time t. Here age a means that the node was introduced at time t − a. That is, we are now resolving each node both by its degree and its age. The resulting joint age-degree distribution is simply related to the degree distribution through N k (t) = t 0 da c k (t, a). The joint distribution evolves according to The second term on the left accounts for the aging of nodes and the probability of connecting to a given node again depends only on its degree and not on its age. We start by considering the linear attachment kernel, A k = k, and focus on the long time asymptotic behavior. Then we can disregard the initial condition and write A(t) ≡ M 1 (t) = 2t. This transforms Eqs. (19) into The homogeneous form of this equation implies that solution should be self-similar. Thus we seek a solution as a function of the single variable a/t rather than two separate variables. Thus, we write This turns the partial differential equation (20) into the ordinary differential equation We have omitted the delta function term, since it merely provides the boundary condition c k (t, a = 0) = δ k1 , or The solution to this boundary-value problem may be simplified by assuming the exponential solution f k = Φϕ k−1 ; this is consistent with the boundary condition, provided that Φ(1) = 1 and ϕ(1) = 0. The above ansatz reduces the infinite set of rate equations (22) into two elementary differential equations for ϕ(x) and Φ(x) whose solutions are ϕ(x) = 1 − √ x and Φ(x) = √ x. In terms of the original variables of a and t, the joint age-degree distribution is then Thus the degree distribution for nodes of fixed age decays exponentially with degree, with a characteristic degree which diverges as k ∼ (1 − a/t) −1/2 for a → t. As expected, young nodes (those with a/t → 0) typically have a small degree while old nodes have large degree (Fig. 4). It is the slow decay of the degree distribution for old nodes which ultimately leads to a power-law degree distribution when this joint age-degree distribution is integrated over all ages to give N k (t).

B. General connection kernels
Let us now consider the GN with a connection kernel which grows either linearly or more slowly with k. The ansatz (21) still is valid, so that the distribution f k evolves according to We now solve Eqs. (25), subject to the boundary condition (23), and with µ determined from Eq. (4). Let us first replace x by X = −µ −1 ln x, which reduces the left-hand side of (25) to df k dX . Applying a Laplace transform,f k (s) = ∞ 0 dX e −sX f k (X),f k (s) obeys a simple algebraic recursion formula whose solution iŝ Apart from notation, this is identical to Eq. (3) and can be analyzed accordingly. In particular, we can determinef k (s) for various asymptotically linear attachment kernels. For example, for the shifted linear attachment kernel, A k = k + w, we find To invert this Laplace transform, it is useful to rewrite this expression as a sum of rational functionsf k (s) = When then re-express this in terms of the original variable x = e −(2+w)X . Hence f k (x) can be re-written as the sum of k power-laws f k (x) = 1≤j≤k F k j x (j+w)/(2+w) . Substituting the explicit expressions (28) into this sum reduces the joint age-degree distribution to This expression shows that old nodes have a broad distribution of degrees up to a characteristic degree k = (1 − a/t) −1/(2+w) . One can also verify that the average age a k of nodes of degree k, defined as Thus nodes with very large degree necessarily have an age which approaches that of the entire network. Finally, the joint age-degree distribution simplifies in the limit k → ∞ and x → 0, with the scaling variable ξ = kx 1/(2+w) kept finite. In this case, we can rewrite (29) in the scaling form The scaling variable can also be written as ξ = k/ k , and thus Eq. (31) clearly shows that old nodes have a broad distribution of degrees: 1 ≤ k < ∼ k . We can derive explicit age-degree distributions for other attachment kernels. For example, for the constant attachment kernel, A k = 1, the joint age-degree distribution is the Poisson distribution, or in terms of the original variables a and t, The characteristic degree now diverges relatively slowly, viz. k ∼ − ln(1 − a/t) as a → t, than for asymptotically linear attachment kernels. On the other hand, the average age approaches the maximal age t at a much faster rate, as a k = t 1 − (2/3) k , as k approaches its maximal value. For cases where we have been unable to obtain an explicit solution, the Laplace transform method still allows us to extract the asymptotics. For example, for asymptotically homogeneous attachment kernels, A k → k γ as k → ∞, Eq. (26) gives the large-k asymptoticsf k (s) ∼ k −γ exp −sk 1−γ /(1 − γ) (see Eq. (5). (For concreteness, we consider here the range 1/2 < γ < 1.) Inverting this Laplace transform yields In particular, the age of nodes with k links is peaked about the value a k which satisfies This again shows that old nodes are much better connected.

V. NODE DEGREE CORRELATIONS
We now demonstrate that correlations between the degrees of connected nodes spontaneously develop as the network grows. One motivation for focusing on these correlations is that recently random graph models with arbitrary degree distributions have been investigated [43][44][45]. While the degree distribution can be chosen arbitrarily in these models, the degrees of connected nodes are uncorrelated. This lack of correlation suggests that such random graphs may have limited applicability to growing network systems.
For the GN, a useful characterization of node degree correlations is N kl (t), the number of nodes of total degree k which attach to an ancestor node of total degree l.
For example, in the network of Fig. 1, there are N 1 = 6 nodes of degree 1, with N 12 = N 13 = N 15 = 2. There are also N 2 = 2 nodes of degree 2, with N 25 = 2, and N 3 = 1 node of degree 3, with N 35 = 1. The correlation function is not defined for the initial node. Generally, N kl is defined for k ≥ 1 and l ≥ 2, and obeys the sum rule N k = l N kl . A gratifying feature of the rate equation approach is that the correlation function N kl can be understood in a natural and simple fashion.

A. Linear connection kernel
For the GN with the linear attachment kernel A k = k, the joint distribution N kl (t) evolves according to The first two terms on the right-hand side account for the change in N kl due to the addition of a link onto a node of degree k − 1 (gain) or k (loss), while the second set of terms gives the change in N kl due to the addition of a link onto the ancestor node. Finally, the last term accounts for the gain in N 1l due to the addition on the new node. Asymptotically, M 1 → 2t and N kl → tn kl , and we use these hypotheses to reduce Eqs. (36) to the timeindependent recursion relations (k + l + 2)n kl = (k − 1)n k−1,l + (l − 1)n k,l−1 + (l − 1)n l−1 δ k1 .
This can be reduced to a constant-coefficient inhomogeneous recursion relation by the substitution m kl (38) to yield m kl = m k−1,l + m k,l−1 + 4(l + 2)δ k1 .
The important feature of this result is that the joint distribution does not factorize, that is, n kl = n k n l . This confirms our earlier assertion that correlations between the degrees of connected nodes form spontaneously. This is arguably the most important distinction between classical random graphs -where node degrees are uncorrelated -and the GN.
While the solution of Eq. (41) is unwieldy, it greatly simplifies in the scaling regime, k → ∞ and l → ∞ with y = l/k kept finite. The scaled form of the solution is For fixed large k, the distribution n kl has a single maximum at y * = ( √ 33 − 5)/2 ∼ = 0.372. Thus a node whose degree k is large is typically linked to another node whose degree is also large; the typical degree of the ancestor is 37% of the degree of the daughter node. In the complementary case of a fixed degree l for the ancestor node, the distribution n kl reaches maximum when k = 1, i. e., the daughter node is usually dangling. From Eq. (41), we find that this configuration occurs with probability n 1l = 2(l − 1)(l + 6) l(l + 1)(l + 2)(l + 3) .
Finally, when both k and l are large and also their ratio is very different from one, the limiting behaviors of n kl are n kl → 16 (l/k 5 ) when l ≪ k, 4/(k 2 l 2 ) when l ≫ k.
This last result demonstrates the correlations in the network most cleanly. If there were no correlations, then n k n l would be proportional to (k l) −3 .

B. General connection kernels
In general, correlations between the degrees of neighboring connected nodes exist for any attachment kernel. The analysis of these correlations for an arbitrary kernel is tedious and we merely outline some of the primary results in the relatively simple cases of the shifted linear and constant attachment kernels.
In the former case, we follow the same approach as the linear kernel to reduce the rate equation for the correlation function to recursion relations of a similar form to Eq. (37), viz.
Here n l is determined from Eq. (12). In analogy with Eq. (38), the substitution reduces Eqs. (45) to where W = (2 + w) Γ(3 + 2w)/(Γ(1 + w)) 2 . We solve the recursion (47) by the generating function method [40]. Multiplying Eq. (47) by x k y l and summing over all k ≥ 1, l ≥ 2, we find that the generating function is given by Expanding M(x, y) we obtain Eqs. (46) and (50) constitute the exact solution for the correlation function of the GN with the shifted linear attachment kernel. When the parameter w is an integer, we can reduce n kl to a rational function. In the general case, the exact solution also simplifies in several extreme limits. When k ≫ l, the dominant contribution to n kl is provided by the first term in the sum in Eq. (50). Assuming additionally l ≫ 1 and repeatedly using the asymptotic relation Γ(N + n)/Γ(N ) → N n as N → ∞, we ultimately find In the complementary case of l ≫ k ≫ 1, all the terms in the sum of Eq. (50) are important. However, we can simplify this sum by employing the above asymptotics for the ratio of gamma functions and then replacing the sum by an easily-computable integral. We find When the attachment kernel is uniform, correlations between the degrees of a node and its ancestor still develop. To see how this comes about quantitatively, we again follow the same steps as those which led to Eq. (37) and find that the joint distribution n kl now satisfies the recursion relation 3n kl = n k−1,l + n k,l−1 + 2 −(l−1) δ k1 .
This recursion relation can again be solved by the generating function technique to give To appreciate the qualitative behavior of the joint distribution n kl it is again useful to fix one variable and vary the other. For fixed l, Eq. (54) shows that n kl has a maximum at k = 1. The magnitude of this maximum is n 1l = 2 −(l−1) − 3 −(l−1) . To analyze the behavior when k is fixed, it is convenient to transform Eq. (54) into Now a straightforward analysis shows that for large k, the maximum is attained at l = k/2. The form of the joint distribution n kl remains relatively complex even in the scaling regime, k, l → ∞, with the scaling variable y = l/k kept finite. We determine the scaled form of the solution (55) by applying Stirling's formula and the identity Γ(x + λ)/Γ(x) → x λ as x → ∞. For y < 2, we find where Y = y ln y − (y + 1) ln[(y + 1)/3]. For y > 2, it is preferable to use the solution in the form of Eq. (54). After some algebra, we can verify that the dominant contribution equals 2 −(l−1) , that is, independent of k [46]. Finally, the limiting behavior of the correlation function is Thus, correlations are strong even for the random attachment kernel and the qualitative behavior is similar to that of the linear attachment kernel.

VI. LARGE-SCALE PROPERTIES
The degree of a node is an important but local network characteristic and we now seek to quantify more global features of the network. One such characteristic is the partitioning of the network into an in-component and an out-component with respect to any node (Fig. 5).
in-component The in-component to node x is the set of all nodes from which node x can be reached by following a path of directed links. Similarly the out-component of node x is the set of nodes which can be reached by following the path directed links which emanate from node x. For the GN model, the out-component is just a single path, while in more realistic networks both the in-and out-components will be branched. In the context of citations, the in-component is the set of all publications which refer to x, either directly or through intermediate reference lists until x is reached. The out-component is the set of cited publications generated by iteratively following the reference list(s) of x and its ancestors.

A. In-component size distribution
The size distribution of the in-component can be easily obtained by the rate equation formalism for the GN with a uniform attachment kernel and also for the GNR. Given the equivalence between the latter and the GN with a shifted linear kernel, the latter case is also soluble. We start by considering the GN with the uniform attachment kernel. In this case, the number I s (t) of incomponents with s nodes satisfies the rate equation To understand this equation, consider first the loss term.
For an in-component of size s there are s nodes in which the attachment of a new node causes this component to increase in size by one. This gives a loss rate for I s which is proportional to s. If there is more than one in-component of size s they must be disjoint, so that the total loss rate for I s is simply sI s . A similar argument applies for the gain term. Finally, the overall factor of t −1 converts these rates to normalized probabilities. Curiously, Eqs. (58) are almost identical to the rate equations for the degree distribution of the GN with linear attachment kernel, except that the prefactor equals t −1 rather than (2t) −1 . From Eqs. (58) we can determine all moments of the in-component size distribution, I n (t) = s≥1 s n I s (t). The zeroth moment obeysİ 0 = 1, whose solution is I 0 (t) = I 0 (0) + t. This is obvious since the total number of in-components equals the total number of nodes. The first moment obeysİ 1 = 1 + I 1 /I 0 , whose asymptotic solution is I 1 (t) ∼ t ln t. We shall see that this logarithmic factor is an outcome of the asymptotic power law for I s with the tail decaying as s −2 .
To solve for I s (t), we note that it again grows linearly in time. Thus we substitute the ansatz I s (t) = ti s into Eqs. (58) to obtain i 1 = 1/2 and i s = i s−1 (s − 1)/(s + 1), which immediately leads to i s = 1 s(s + 1) .
For this s −2 decay, the moments I n diverge when n ≥ 1. However, the size of the largest in-component, s max = t, provides an upper threshold in the computation of the moments. For example, I 1 ∼ s≤t sI s (t) = t ln t. It is intriguing that the algebraic in-component distribution co-exists with an exponential in-degree distribution, Similarly, we can determine I s (t) for the GNR model. In this case, the number I s (t) of in-components with s nodes satisfies Remarkably, the asymptotic power law I s ∝ s −2 holds for any r. It is striking that this apparently universal behavior has also recently been observed in measurements of the Internet [47] Since the GNR model is identical to the GN with the shifted linear attachment kernel A k = k + ( 1 r − 2), Eq. (61) also applies to the in-component distribution for the GN with shifted linear attachment kernels. For example, the in-component distribution for the linear kernel is i s = 2/(4s 2 − 1). Since the same I s ∝ s −2 decay holds for the GN with both constant and linear attachment kernels, we conjecture that the in-component distribution exhibits a universal s −2 decay for an arbitrary attachment kernel, as long as it does not grow faster than linearly with node degree.

B. Out-component size distribution
The out-component from each node reveals basic insights about the "genealogy" of the growing network in an extremely simple fashion. For example, it allows us to estimate the diameter of the network, an important characteristic which has been measured for the web graph [48,49] and for social networks [23].
For this characterization, we begin by reorganizing the GN into a genealogical tree according to a procedure which is suggested by the growth process itself. Generation g = 0 contains the single "seed" node. The nodes which attach to the seed node form generation g = 1, and generally the nodes which attach to nodes in generation g form generation g + 1, independent of when the attachment actually occurs. Thus the position of a node in the genealogical tree depends only on the position of the ancestor node and not on when the node is introduced. In this respect, the GN genealogical tree differs from usual genealogies, where each new generation is born into a progressively later position in the genealogical tree. For example, the network of Fig. 1 has 5 nodes in the first generation and 4 nodes in the second generation leading to the genealogical tree of Fig. 6. The sizes of all generations grow continuously, except for generation g = 0 which always consists of the single node. Once we understand the genealogical structure of the GN, we simultaneously establish the out-component distribution. Indeed, the number O s of out-components with s nodes equals L s−1 , the number of nodes in generation s − 1 in the genealogical tree. We therefore compute L g (t), the size of generation g at time t. We start with the simplest situation when the attachment rate is uniform. In this case, L g (t) increases when a new node attaches to a node in the previous generation. This occurs with rate L g−1 /M 0 , where M 0 (t) = 1 + t is the total number of nodes. Because of the simplicity of the corresponding rate equations, we use the exact expression for M 0 rather than the asymptotic expression M 0 ∼ t, as was done in solving for the in-component. Thus we write Solving these equations gives We therefore conclude that for a fixed (large) time, the generation size grows with g when g < τ , reaches a maximum size which is equal to when g = τ , and then decreases and eventually becomes of order one when g = eτ . The distribution L g quickly decays when g exceeds the cutoff value eτ . At time t, the genealogical tree therefore contains approximately eτ generations. Hence the diameter D of the network is approximately 2eτ , or where N = 1 + t is the total number of nodes. Thus, the diameter of an evolving GN exhibits the same N dependence as a static random graph [4]. We can also find the generation size distribution for shifted linear attachment kernels. It is again simpler to derive the rate equations in the framework of the GNR model and then transcribe the results to the shifted linear kernel. For the GNR model, the rate equation for the generation size distribution is for g > 1, andL 1 = (1 + t) −1 [1 + rL 1 ]. The first term in (66) has the same origin as in the GN without redirection and the second term accounts for the change in L g due to the re-direction. In the latter case, the new node provisionally attaches to a node in generation g; this occurs with relative probability L g . However, by the re-direction process, this new node actually attaches to a node in generation g − 1 and thereby joins generation g.
To solve Eq. (66), we again use τ = ln(1 + t) and apply the Laplace transform technique. After some elementary steps, we obtain From this solution, we find that for a fixed (large) time, the generation size grows with g when g < (1 − r)τ , reaches a maximum value L max ≃ t/ 2π(1 − r) ln t at g = (1 − r)τ , and then decreases when g > (1 − r)τ . Eventually the generation size becomes of order one when g = Gτ , where G is the root of equation G ln(G/(1−r)) = G + r. The diameter of the network is then D ≈ 2Gτ . These two solvable cases again suggest that the genealogy of the GN is robust, as long as the attachment kernel does not grow faster than linearly with node degree. For the super-linear kernels, however, the genealogy changes drastically. When the attachment exponent exceeds 2, there will be only a few generations overall, and one generation g * will contain all but the finite number of nodes. For such a network, the gel node will reside in generation g * − 1. When the attachment exponent lies in the range 1 < γ < 2, a single generation will also contain almost all t nodes. However, the number of nodes which reside in other generations is of order t 2−γ and thus grows as well. Additionally, the number of non-empty generations grows indefinitely with the total number of nodes.
The above results can be reformulated in terms of the out-component distribution. In particular, for the GN with uniform attachment kernel, the number O s of outcomponents with s nodes equals Similar results apply for the linear attachment kernel, suggesting that the out-component distribution is robust as long as the attachment kernel does not grow faster than linearly with node degree.

VII. DISCUSSION AND CONCLUSIONS
In this paper, we have analyzed the structure of the growing network (GN) model and shown that many of its properties can be easily determined within a rate equation approach. We have found that the GN has a powerlaw node degree distribution, N k (t) ∼ tk −ν , for asymptotically linear attachment kernels, with an exponent ν which is always larger than 2. By tuning parameters of the model in a reasonable way, it is easy to obtain a node degree distribution which is in quantitative agreement with available data for the web graph [14][15][16][19][20][21]49].
A remarkable feature of this network is the spontaneous development of correlations between connected nodes. These correlations provide a much more sensitive characterization of the structure of growing networks than the extensively studied degree distribution. These correlations are a crucial feature which distinguishes the GN from classical random graphs. Thus testing for the presence of correlations between node degrees in large evolving networks may provide crucial insights to help determine the underlying mechanism of their growth.
We have also studied two specific large-scale properties of the network, namely, the size distributions of the inand out-components with respect to a given site. The in-component distribution exhibits a robust s −2 powerlaw behavior, where s is the component size, as long as the attachment probability does not grow faster than linearly with node degree. The out-component distribution reveals the basic genealogical feature that the number of "generations" in the network grows logarithmically with the total number of nodes, again for attachment kernels which do not grow faster than linearly in node degree.
The qualitative agreement between the degree distributions of real evolving networks, such as the web graph, and the GN is reassuring given that the model ignores many important features of real networks. Nevertheless, a number of characteristics of real growing networks are difficult to treat in the framework of the GN model. One important such characteristic is the out-degree distribution. Within the GN model the out-degree of each node is one by construction. In contrast, for real growing networks the out-degree distribution has a power law form [49]. Additionally, the average in-and out-degrees at each node are generally larger than one. For the web graph, for example, i = j ≈ 7.5 [49].
There are several natural ways to extend the GN model to generate an average out-degree which is greater than one. A simple construction is to link every new node to more than one earlier node, as already discussed in Ref. [20]. Let us consider a network which is built by attaching every new node to exactly p earlier nodes. For the linear attachment kernel, the degree distribution N k (t), which is now defined only for k ≥ p, evolves according to Clearly, the average in-degree i and out-degree j of each node in this network is equal to p. By applying the basic approach of Sec. III to this rate equation, we find that the degree distribution again asymptotically approaches a stable distribution N k → tn k , with n k = 2p(p + 1) k(k + 1)(k + 2) for k ≥ p.
Thus for the linear attachment kernel, the average node degree does not affect the exponent ν of the degree distribution. However, for other solvable examples, the new feature of attaching the new node to more than one preexisting node leads to different degree distributions. For example, for the shifted linear kernel we find n k = const. × Γ(k + w) Γ(k + 3 + w + w/p) for k ≥ p, This gives the asymptotic behavior n k ∼ k −(3+w/p) . Thus the exponent of the degree distribution depends on the average node degree, with ν = 3 + w/p. The multiple linking construction also reduces the number of nodes with in-degree zero. For example, for the GN with the shifted linear attachment kernel, the fraction of such nodes is n 1 = (2 + w)/(3 + 2w), which is always larger than 1/2. However, for the multiple linking construction, the fraction of nodes with in-degree zero is reduced to the value n p given in Eq. (72). If we use p = 7 to reproduce the correct average node degree of the web graph, the fraction of nodes with in-degree zero always exceeds 1/8, which, however, apparently disagrees with web data [49]. Thus while multiple attachment does reduce the number of poorly-connected nodes, this reduction is still insufficient to account for web-graph data. However, it is clear that the multiple linking construction has the potential to provide a better description of citation data.
Another shortcoming of the multiple attachment construction is that it cannot dynamically generate a nontrivial out-degree distribution. However, we can extend the GN model by allowing for creation of links between existing nodes [50]. This simple construction allows us to generate non-trivial out-degree distributions which closely match web graph data. An even more challenging direction is to describe the global topological structure of growing networks. The GN model leads to a singlecomponent tree graph, while the web graph has numerous disconnected components. A deeper understanding of the web graph may provide valuable insights to help develop algorithms for web crawling, searching, and community discovery.
We are grateful to NSF grant DMR9978902 and ARO grant DAAD19-99-1-0173 for partial financial support of this research.