Preferential attachment mechanism of complex network growth: "rich-gets-richer" or "fit-gets-richer"?
Michael Golosovsky







michael.golosovsky@mail.huji.ac.il


The Racah Institute of Physics, The Hebrew University of Jerusalem, 91904 Jerusalem, Israel



             


We analyze  the growth models for complex networks including  preferential attachment (A.-L. Barabasi and R. Albert, Science 286, 509 (1999)) and fitness model (Caldarelli et al., Phys. Rev. Lett. 89, 258702 (2002)) and demonstrate that, under very general conditions,  these two models  yield  the same dynamic equation of  network growth, dK/dt=A(t)(K+K_0), where A(t) is the aging constant, K is the node's degree, and K_0 is the initial attractivity. Basing on this result, we show that the fitness model provides an underlying microscopic basis for the preferential attachment mechanism. This approach yields long-sought  explanation for the initial attractivity,  an elusive parameter which was left unexplained  within the framework of the preferential attachment model. We show that  K_0 is mainly determined by the width of the fitness distribution. The measurements of K_0 in many complex networks usually yield the same K_0∼ 1. This  empirical universality  can be traced to frequently occurring lognormal fitness distribution with the width σ≈ 1.




01.75.+m, 02.50.Ey, 89.75.Fb, 89.75.Hc
                             

                              
Preferential attachment mechanism of complex network growth: "rich-gets-richer" or "fit-gets-richer"?

    Michael Golosovsky
    December 30, 2023
======================================================================================================




§ INTRODUCTION



Power-law distributions   were  brought to attention of scientific community about a century ago <cit.> and they made sharp contrast with previously known Gaussians. The intriguing question arouse- what is the  generative mechanism   of these weird distributions? The explanation  came in 1970s when de Solla Price suggested his cumulative advantage model which he developed by studying network of citations to scientific papers.<cit.>  This model can be captured as follows.<cit.> Consider a network consisting of nodes and edges. New nodes appear with constant rate dN/dt and extend ∼ c edges to other nodes.  The probability of a new node i to attach to a node j is

    Π_j=K_j+K_0/∑_l(K_l+K_0),

where K_j is the target node's in-degree, i.e., the number of its incoming edges, and the sum is over all nodes.   The initial attractivity K_0  ensures that newly born nodes start to acquire edges immediately. Equation <ref> is motivated by  the Gibrat's proportional law which explained the power-law distribution of wealth. The accumulated edges in Eq. <ref> play the role of node's "capital" and new edges are "dividends".

Equation <ref> yields a power-law degree distribution, p(K)∼ K^-γ   with the exponent

    γ=2+K_0/c.

Price didn't look for detailed comparison of Eq. <ref> with the data, it was sufficient for him that Eq. <ref> yields the power-law distribution with γ≥ 2 which is very similar to well-documented Pareto distributions of bibliometric indicators captured by Lotka's, Bradford's, and Zipf's laws. In the absence of any clue, Price postulated K_0=1.

The Price's cumulative advantage model (Eqs. <ref>,<ref>) didn't spread beyond the information science community since citation network was the only complex network then known. However,  as a result of proliferation of digitized information in 1990s, a number of information, biological, and social complex networks came to the forefront of scientific research, many of them being characterized by the power-law degree distributions  with γ∼3.<cit.> These distributions are somewhat different from the power-law distributions with γ∼2 occurring in those social phenomena which are not considered as complex networks (word occurrence in  texts, city sizes, wealth distribution, etc.). To account for the power-law degree distributions  with γ∼3  in information and biological networks Barabasi and Albert  suggested the preferential attachment model <cit.> which is very similar to but not identical with the Price's cumulative advantage model.  The core assumption of the Barabasi-Albert model  is that a newly born node i attaches to an older node j with  probability

    Π_j∼ K_j,

where K_j is the target node's degree for undirected networks and the  sum of the in- and out-degrees,  K_j=K_j^in+K_j^out, for directed networks. Newman <cit.> showed that for the latter case Eq. <ref> can be mapped onto the Price's model. Indeed,  since statistical distribution of  out-degrees in most complex networks is  narrow,  for directed networks,  Eq. <ref>  can be written as  Π_j∼ (K_j^in+c)  where c=K_j^out.  On another hand, Eq. <ref> can be written as Π_j∼ (K_j^in+K_0). The above  equations are equivalent and c plays the role of initial attractivity K_0.  It should be noted, however, that while Price's model postulates   K_0=1,  the Barabasi-Albert  model assumes K_0=c. Both  models generate  networks with the power-law degree distributions, but the exponents are different: γ≥2 for the former and γ=3  for the latter model. The Barabasi-Albert preferential attachment model  better agrees with  measured power-law distributions in complex networks and that is why it became the paradigm for complex network research, much in the same way as the Ising model established itself  as a  paradigm for  studies of magnetism.  In particular, the preferential attachment model became the basis for developing  specific network growth models. On another hand, it has been serving as a platform for organisation of measurements to characterize complex networks. 

Numerous measurements of the  growth dynamics of  complex networks validated Eq. <ref>, namely they established  a linear or close-to-linear dependence between the growth rate of node's degree, dK/dt, and its current degree, K.  In addition, these measurements yielded a very small initial attractivity, K_0∼ 1. The last finding poses a problem for the theory. On the one hand, most complex networks are characterized by the power-law distribution with γ∼ 3 and c>>1 and, according to Eq. <ref>, this implies  K_0∼ c>>1. On another hand,  the measured K_0∼ 1 is much smaller and inconsistent with that inferred from Eq. <ref>. Solution of this inconsistency  requires (i) thorough analysis of the measurement protocols aimed at verification of Eq. <ref>, (ii) reevaluation of the theoretical derivation of Eqs. <ref>,<ref>,<ref>, and (iii) a deeper understanding of the initial attractivity K_0 which is not defined within the preferential attachment model.


The aim of our study is the reevaluation of the preferential attachment mechanism and its derivatives in order to understand this elusive parameter- initial attractivity. This is done in Sections <ref> - <ref> while in Section <ref> we analyze another kind of the network growth model- the  fitness model of Caldarelli et al. <cit.>. Section <ref> reports our original results. Our main finding is that the fitness model  provides a microscopic basis of the preferential attachment mechanism and explains the initial attractivity which is determined by the shape of the fitness distribution. We also demonstrate that small initial attractivity K_0 is consistent with the power-law degree distribution with γ∼ 3. Section <ref> discusses the common basis of the preferential attachment, fitness model, and recursive search.


§ EVALUATION OF THE PREFERENTIAL ATTACHMENT MODEL



In what follows we do not make distinction between the Price's and Barabasi-Albert approaches and relate to Eq. <ref> with unspecified  K_0  as the preferential attachment model. The success of this model in explaining the seemingly universal power-law degree distribution in complex networks prompted several theoretical generalizations.



  * Initial attractivity.  Refs. <cit.> analyzed Eq. <ref> in which the attachment rule was modified to Π_j∼ (K_j+K_0), where  K_j is the total degree and K_0 is an arbitrary  number. It was found that the power-law degree distribution is retained but its exponent is modified in accordance with Eq. <ref>.


  * Accelerated network growth. While the original Barabasi-Albert model assumed that new nodes and edges appear at the same rate, Leskovec et al. <cit.> found that in many networks the number of edges grows faster than the number of nodes, in such a way that these  networks shrink with time. Assuming that the  average number of outgoing edges per node increases exponentially with time, c=c_0t^Θ, Ref. <cit.>  found that the power-law degree distribution in these shrinking networks is retained but its exponent increases by Δγ=2Θ/1-Θ.



  * Link editing. In the original Barabasi-Albert model the existing links can't be deleted, the links between old nodes can't be added, and the old nodes can't be removed. Although this is true for citation networks, other networks such as Wikipedia edits, allow link or node editing. Ghoshal et al. <cit.> analyzed   networks for which  link editing and node removal are allowed and showed that these processes act disruptively on network topology, although there is a wide range of parameters for which the power-law degree distribution is conserved.


  * Aging. Equation <ref> assumes that the attachment probability Π_j does not depend on node's age. However, the common sense tells us that  Π_j should decrease with increasing age of the target node, in such a way that recent nodes become more popular. Refs. <cit.> considered a general case of the  preferential attachment with aging

    Π_j= A(t_j)(K_j+K_0)/∑_lA(t_l)[K_l+K_0],

where t_j is the age of node j and A(t) is the aging function which is usually assumed to follow exponential or power-law dependence, A(t)∝ 1/t^ν. In the latter case Dorogovtsev and Mendes <cit.> showed that the power-law degree distribution is retained only for ν<1 while for ν>1 the aging effect overcomes the preferential attachment and the degree distribution does not follow the power-law dependence.


  * Memory. Although Eq. <ref> accounts for aging, it attributes  equal weight to all edges, as if the attachment were a Markov process. However, the recent edges are usually more important than the older ones, namely, attachment process can have memory. Refs. <cit.> considered  preferential attachment with memory and replaced Eq. <ref>  by
 
    Π_j(t_j)∝∫_0^t_jA(t_j-τ) k_j(τ)dτ,

where Δ K_j(τ)=k_jΔτ  is the number of edges garnered by the node j in the time window (τ,τ+δτ), t_j is the node's age, A(t_j-τ) is the memory kernel, and the integral is over all past edges that appeared during target node's life.


  * Nonlinear preferential attachment. While  Eq. <ref> assumes a linear relation between attachment probability Π_j and node's degree K_j, Krapivsky and Redner <cit.> considered a general case of nonlinear preferential attachment

    Π_j=(K_j+K_0)^1+δ/∑_l(K_l+K_0)^1+δ

where δ≠ 0. It was shown that  the power-law degree distribution is closely associated with the linear case, δ=0. For the superlinear attachment, δ>0,  the network becomes the hub-and-spoke or  "winner-takes-all", while  for the sublinear attachment, δ<0, the network becomes a gel-like where every node is connected to all other nodes and degree distribution is the stretched exponential rather than power-law.   Subsequently, Krapivsky and Krioukov  <cit.> showed that for weak superlinear attachment, 0<δ<<1, there is a vast asymptotic regime for which the network retains its power-law degree distribution.


In summary, theoretical studies indicate that the preferential attachment mechanism is  plausibly robust. Namely, it generates complex networks with the power-law degree distribution and the exponent 2<γ≤ 3  under the following conditions: the attachment probability is  linear or weakly nonlinear, aging is weak, and initial attractivity is positive and  small. These conditions are quite reasonable and that is why the preferential attachment model has been accepted as a most plausible generative mechanism of  growing complex networks with the power-law degree distribution.




§ MEASUREMENTS AND MODEL VALIDATION



Refs. <cit.>  discuss the microscopic mechanisms of the evolution of growing networks  and the ways of their validation. In what follows we present a more specific overview with the focus on preferential attachment.



Straightforward verification of the preferential attachment model requires analysis of decisions made by incoming nodes. The measurements aimed at quantitative analysis of such decisions are widespread in psychology but they are rare in physics, biology, and computer science - the fields, where majority of complex networks appear. The most conventional way to uncover the growth mechanism of complex networks is to trace evolution of individual nodes.  To this end, the  perspective shall be shifted from the incoming node to  the target node. To perform such shift we go back to Eqs. <ref>-<ref> and assume that new nodes appear at a constant rate. Consider N new nodes that joined the network during time window (t,t+Δ t). Each new node extends in average  c edges to existing nodes. Consider one such target node j. From the  batch of new nodes,  it garners approximately Δ K_j=Π_jcN  edges  where Π_j  is its attachment probability. We substitute there the general expression for Π_j, which includes nonlinearity, aging, and initial attractivity,  but not  memory,  and find

    Δ K_j=Ã(t_j)(K_j+K_0)^1+δ

where  t_j is the target node's age at time t, K_j is its current degree, and the aging function is  Ã(t)=A(t)/∑_lA(t_l)[K_l+K_0]^1+δcN. [Note difference between A(t) and Ã(t): for the Barabasi-Albert model A(t)=1 while Ã(t)=2/tN/Δ t.] Equation <ref> is the basis for comparison of the preferential attachment model to measurements.

To validate Eq. <ref>  one usually considers a set of  all nodes of the same age and measures each one's degree  at  t and at t+Δ t. Then one calculates Δ K_j=K_j(t+Δ t)-K_j(t), the number of additional edges that  each  node  garnered during the time window (t,t+Δ t), plots Δ K_j versus K_j, and makes one's best to fit this scatter plot using Eq. <ref>.<cit.>  This fit is by no means trivial. The catch here is that Δ K_j is a discrete  stochastic variable and Eq. <ref> predicts its  mean value but says nothing about the variance. Our measurements for citation networks <cit.> indicate that Δ K_j distribution (for fixed K_j) follows negative binomial distribution with high variance-to-mean ratio >2, in such a way that the variance of Δ K_j  is considerably greater than that for the Poisson distribution. In other words, Δ K_j(K_j) dependence is so noisy that direct fitting of Δ K_j vs K_j using Eq. <ref> is not very informative.


To circumvent the problem of noise one can use logarithmic binning of K_j, plot a histogram of Δ K_j, and find the trend. This method was originated by Newman <cit.> and adopted by many others.<cit.>

Another way to counter the noise problem is to plot  cumulative function ∫_0^KΔ K(K)dK vs  K. In the context of complex networks  this procedure was first applied by Jeong et al. <cit.> and subsequently by Refs. <cit.>. However, there is a pitfall here.  If Δ K_j were continuous variable with symmetric distribution, this cumulative procedure should certainly work. However, since Δ K_j is a non-negative discrete variable with highly skewed distribution, the cumulative procedure can distort  the results, in particular, when applied to validation of Eq. <ref>, it overestimates the initial attractivity.<cit.>


Yet another strategy is to use the raw Δ K_j versus K_j plots and to apply sophisticated numerical fitting procedure to find parameters of Eq. <ref>.<cit.> This procedure could probably become a valuable tool in complex network characterization.<cit.>


In what follows we present the summary of measurements aimed at validation of Eq. <ref>.


  * Preferential attachment. The growth of many complex networks does follow the preferential attachment model.<cit.> However, some of these networks exhibit preferential attachment only  for nodes with low and moderate degrees while the nodes with high degree exhibit anti-preferential attachment.<cit.>


  * Linear or nonlinear PA? Early measurements claimed  linear or close to linear preferential attachment.<cit.> Later measurements using large datasets (citations to scientific papers <cit.> and patent citations  <cit.>) revealed superlinear attachment with the exponent  1+δ∼ 1.25. Social networks (scientific collaboration,<cit.> movie actors <cit.>) exhibit sublinear preferential attachment with the exponent 1+δ=0.8-0.9.

 
  * Aging function.  Our measurements of citations to scientific papers <cit.> yielded Ã(t)∼(t-Δ)^-ν, namely, a power-law decay with small delay Δ∼1-2 yr and the exponent ν=2. Patent citations  yield a similar power-law aging function with ν=1.3-1.6. <cit.> Zeng et al. <cit.> provide an overview of aging effects in citation networks.
     


 
  * Initial attractivity. Early measurements of citations to scientific papers  were not statistically representative to make reliable estimate of K_0.<cit.> Subsequent studies of  patent citations   yielded small  K_0∼ 1.<cit.>  Our high statistics measurements of citations to scientific papers  <cit.> also yielded small K_0∼ 1. Eom and Fortunato <cit.> analyzed network of citations between the APS (American Physical Society) journals  and found a bigger number,  K_0∼ 7 for younger papers and K_0∼ 1-2 for the papers that are at least 5 years old. (Note, however, that Ref. <cit.> used cumulative procedure which is known to  overestimate K_0.<cit.>). Recent  studies of Higham et al. <cit.> yielded K_0=1-1.8 for patent citations and K_0=1 for Physical Review citations. Thus, all  measured initial attractivities are small, K_0<<c, and better conform to Price's conjecture, K_0=1, rather than to the Barabasi-Albert conjecture, K_0=c.
 

Thus, preferential attachment mechanism of network growth, as captured by Eq. <ref>, has been qualitatively validated for  many complex networks. The attachment in most of them is  linear or close-to-linear, although deviations from the linearity are well documented. However,  Eq. <ref> is not supported by measurements. Indeed, the measurements indicate that initial attractivity K_0 is small.  In this case  Eq. <ref> yields the  power-law degree distribution with γ≥  2 and this is in contrast to the power-law degree distribution with  γ∼ 3 observed in  majority of complex networks.<cit.>  This inconsistency  notwithstanding,  the preferential attachment model became a paradigm of complex network growth and a platform for network characterization.



§ SPECIFIC PREDICTIONS OF THE PREFERENTIAL ATTACHMENT  MODEL AND THEIR STATUS VERSUS MEASUREMENTS


After scientific community became persuaded that the growth of  complex networks is accounted for by the preferential attachment model, the research  shifted  from the model validation to analysis of its predictions. Indeed, besides the power-law degree distribution, the complex networks generated using Eq. <ref> should acquire  a very special structure.<cit.>



  * First mover advantage. The preferential attachment model  predicts strong positive  correlation between the node's age and degree, namely,  the degree of the old nodes should be substantially higher than that of the recent nodes.  The measurements reveal such correlation but it is not strong and most new edges do not necessarily go to old nodes.<cit.>
    


  * Trajectory of the nodes of the same age. The basic preferential attachment model predicts that the node's degree grows  with time according to the rule: K_j(t_j)=K_0[(1+t_j/t)^c/c+K_0-1]  where t is the age of the network at the moment when the node was born and t_j is the node's age.<cit.> Thus, the node's degree grows with time with deceleration and the trajectories of the nodes of the same age  should be very similar. However, the measurements show  that these trajectories   strongly diverge <cit.> and do not necessarily decelerate with time. In particular, citation networks demonstrate  many  "sleeping beauties" <cit.> whose trajectories accelerate with time.


  * Degree distribution for the nodes of the same age. According to the preferential attachment model, this distribution is narrow and close to exponential, p(K)∼ K^K_0-1(1-t_j^c/c+K_0)^K.<cit.> Measurements on Wikipedia  and citation networks showed that degree distribution for the nodes of the same age is much wider than exponential and is better described by the power-law or lognormal function.<cit.>


  * Degree-degree correlation. Within the framework of the preferential attachment model the assortativity of the resulting network is determined by the initial attractivity K_0.<cit.> In particular, for K_0=c (the Barabasi-Albert model), the network shall be neutral, for K_0>c  it shall be assortative, and for K_0<c (Price's model) it shall be disassortative.<cit.> Direct measurements of the initial attractivity yield small  K_0∼ 1 implying that most networks should be disassortative.   While social networks are indeed disassortative, citation networks are not.<cit.> Thus, contrary to model prediction, there is no straightforward relation between the initial attractivity K_0 and the network assortativity.
    

  * Clustering coefficient. The preferential attachment mechanism predicts that in large networks the clustering coefficient shall be vanishingly  small.<cit.> However, many real networks have high clustering coefficient.<cit.>



Thus, several specific predictions of the preferential attachment model are inconsistent with measurements. This is unsurprising since these predictions were made assuming a basic version of the model, namely, linear preferential attachment and absence of aging (Eq. <ref>). Since most studied networks exhibit weakly nonlinear attachment and strong aging, the proper  account of these two factors could modify some of the above predictions and make them  consistent with observations. However,  the problem of the wide degree distribution of the nodes of the same age and the paradox of the first-mover advantage can be hardly solved in such a way. To address these problems one needs to go beyond the framework of the preferential attachment model as captured by Eqs. <ref>-<ref>.




§ FITNESS-BASED PREFERENTIAL ATTACHMENT



The difficulties associated with the application of the preferential attachment model and its derivatives for the quantitative account of  complex network growth call for alternative approaches. One such alternative is the attachment probability which  is proportional not to node's degree but to some other node's attribute such as  local  clustering coefficient,<cit.>  node's rank,<cit.> or PageRank coefficient.<cit.> However, the most popular alternative is the  Bianconi and Barabasi model <cit.> that introduced fitness- an empirical parameter that characterizes the propensity of nodes to attract edges. The core assumption of the model is that the node's fitness is a constant number  and does not change with time.



 §.§ Multiplicative fitness- Bianconi-Barabasi model

How fitness can be incorporated into dynamic equation of network growth? The Bianconi-Barabasi model <cit.>  introduces  fitness  on top of the preferential attachment, namely, it postulates  that the attachment probability is the product of node's fitness η and degree,

    Π_j=η_j(K_j+K_0).

(To be consistent with  Eq. <ref> we introduced here  initial attractivity K_0.)   Solution of Eq. <ref> yields the node's trajectory K_j(t). It turns out that this trajectory strongly depends on fitness: a  high fitness latecomer can outperform a low-fitness old node. Thus, fitness solves  the problem of the first-mover advantage. It also solves the problem of degree distribution for the nodes of the same age which is now determined by  fitness distribution  rather than by the acquired degree.

What is fitness? On the one hand, it  includes the notion of similarity  known as homophily in social networks.<cit.>  Indeed, complex networks are rarely uniform, they consist of communities and subcommunities. New nodes tend to attach to  similar nodes, namely, to those belonging to the same community.  To measure similarity one can use overlap of contents or  bibliographies for citation networks and WWW pages,<cit.>  or overlap of common neighbors in the general case.<cit.> Another ingredient of fitness is  associated with quality or talent. This component   is not easy to estimate  when the  node first appears, it can be measured  only after it has garnered some edges. The obvious way to measure the Bianconi-Barabasi's fitness is through  Eq. <ref>.  Thus, Kong et al.  <cit.> studied the network of WWW internet pages, analyzed  trajectories of the pages of the same age, and successfully fitted them using Eq. <ref>. The fitness turned out to be constant, as expected,  and the fitness distribution  turned out to be wide.


The most striking prediction of the Bianconi-Barabasi model is that for wide fitness distributions there are supercritical nodes that eventually take a lion share of edges.  Such supercritical nodes were  observed in citation networks <cit.>  and this successful prediction became a reason of the wide popularity of the  Bianconi-Barabasi  model.<cit.>
 

While Eq. <ref> explains several  features of  complex networks, such as degree distribution of the nodes of the same age,  it  does not account for aging. To convert the Bianconi-Barabasi model into a quantitative tool that can be  be compared to measured node's trajectories, Wang, Song, and Barabasi  <cit.>   replaced Eq. <ref> by the following expression

    Π_j=η_jA_j(t_j)(K_j+K_0),

where A_j(t_j) is the aging function, specific for each node, and t_j is the node's age.  (Ref. <cit.> denoted the aging function by P_j (t)  while we denote it by A_j(t) to be consistent with Eq. <ref>). The Wang-Song-Barabasi model (Eq. <ref>)  builds upon the earlier approach of Ref. <cit.> who introduced  node's relevance, X_j(t)∼η_jA_j(t).


Equation <ref> was validated using citation network of Physics papers covered by the APS database,<cit.> whereas  the  aging function was approximated by the lognormal dependence A_j(t_j)=1/√(2π)σ_j t_je^-((lnt_j-μ_j)^2/2σ_j^2 )
where μ_j and σ_j are specific parameters for each node.   Pham, Sheridan, and Shimodaira <cit.> developed a software package  based on Eq. <ref>  and demonstrated that it is a valid platform for quantitative description of the complex network growth.


This success notwithstanding, Eq. <ref> has several problems. First of all, it contains too many fitting parameters. In addition to dynamic node attributes (degree K_j and  age t_j), the Wang-Song-Barabasi model adds another three   static attributes: η_j,μ_j, and σ_j. Secondly, the Wang-Song-Barabasi  and its parent  Bianconi-Barabasi model assume linear preferential attachment.  This is an unlucky coincidence  that both these models were validated using citation networks which exhibit nonlinear preferential attachment.<cit.>  While  the Wang-Song-Barabasi model can be  extended to account for nonlinearity, this extension requires an additional fitting parameter- attachment exponent- in such a way that the resulting model  becomes too sophisticated.



 §.§ Additive fitness

The multiplicative fitness of the Bianconi-Barabasi model is not the only way it can be  introduced into dynamic equation of network growth.  Ref. <cit.> introduced fitness through optimization procedure, while  Refs. <cit.> introduced it additively, as follows:

    Π_j∝ (K_j+η_j).

Equation <ref> is nothing else but Eq. <ref> where fitness η_j replaces the initial attractivity K_0.


The growth dynamics described by Eqs. <ref>, <ref> are not that different as it could seem.  In fact, the combination of nonlinear preferential attachment (Eq. <ref>) with  additive fitness (Eq. <ref>)  mimics Eq. <ref>, in particular, it   predicts supercritical nodes. To demonstrate this we adopt continuous approximation of Ref. <cit.> and replace Δ K_j in Eq. <ref> by dK_j/dtΔ t. In view of Eq. <ref>  Eq. <ref> can be recast  as follows:

    dK/dt=Ã(t)(K+η)^1+δ

where  index j was dropped for brevity. We solve Eq. <ref> for δ>0 and find

    K(t)η/[1-δη^δ∫_0^tÃ(τ)dτ]^1/δ-η.

To analyze Eq. <ref> we assume for simplicity that the integral  ∫_0^tÃ(τ)dτ converges  as t→∞. We introduce η_crit=[δ∫_0^∞Ã(τ)dτ]^-1/δ, in such a way that  Eq. <ref> reduces to

    K(t)=η/[1-(η/η_crit)^δ∫_0^tÃ(τ)dτ/∫_0^∞Ã(τ)dτ]^1/δ-η,

where t is the node's age. For η<η_crit Eq. <ref> yields  K(t) that increases with time and eventually achieves saturation, K(∞)=η/[1-(η/η_crit)^δ]^1/δ-η. However, for  η≥η_crit, K(t) does not achieve saturation, namely, the node's trajectory becomes supercritical. (In fact, it undergoes a finite-time singularity at certain t_0, in such a way that Eqs. <ref>, <ref>  hold only for t<t_0.)  Thus, for the superlinear preferential attachment, δ>0, Eq. <ref>  predicts the supercritical nodes - exactly as Eq. <ref> does.





§ EXPLANATORY MODELS OF NETWORK GROWTH



The basic preferential attachment model and the fitness-based preferential attachment are not explanatory models, they lack realistic scenario explaining how the new node chooses the target nodes. Indeed,  Eqs. <ref>,<ref> imply that an incoming node shall know degrees of all  other nodes in the network in order to attach to some of them. This can be true for  collaboration and some other social networks,<cit.> for which a new node is  familiar  with some limited set of nodes, but not for general networks for which global information on network connectivity is usually unavailable.<cit.>

The most popular explanatory model of  network growth is the recursive search <cit.> also known as link copying or redirection,<cit.> random walk or local search,<cit.>  triple(triangle) formation,<cit.>   triadic closure,<cit.> or forest fire model.<cit.> The motivation for this class of models was the explanation of the high clustering coefficient commonly observed in complex networks. The recursive search mechanism assumes that a new node attaches to a randomly found node, explorers the network neighborhood of the latter, and with some probability attaches to one <cit.> or all <cit.> of its ancestors. This scenario can include one-level <cit.> or multilevel search,<cit.> in the latter case a new node explores network vicinity of all previously chosen nodes. Vazquez <cit.> showed that, in the absence of ageing and memory, the one-level recursive search mechanism results in the attachment probability

    Π_ij= λ+ qK_j,

where λ is the probability of random search, qK_j is the probability of recursive search, and K_j is the target node's degree. If we recast this equation as Π_ij= q(K_j+λ/q) we immediately realize that this is nothing else but  Eq. <ref> with K_0= λ/q.

The above studies suggested only a generic scenario of the recursive search while to convert it into a quantitative model one needs to calibrate this scenario against the measurements. Recently, we performed such calibration using  citation networks <cit.>  and found that Eq. <ref> shall be supplemented with  aging, memory, and- most important- fitness. Namely, it turned out that the random search is not random but fitness-based.  Our findings imply the multilevel recursive search that develops according to the following scenario:  a new node i performs a fitness-based search in the network, finds some target node k, and explorers its network neighborhood. It can choose a  nearest neighbor of k as a new target node j. The  probability of such choice depends on the age of the parent node k with respect to node i (obsolescence or memory). Then the node i explores a network neighborhood of a newly chosen node j and so on. When we shift the perspective to the target node j,  this  scenario results in the following dynamic equation

    dK_j/dt= η_jm(t)+ ∫_0^tqe^γ(τ-t)k_j(τ)dτ

where K_j is the target's node degree, η_j is its fitness, m(t) is the aging function, q is the probability of recursive search,  k_j(τ)δτ is the number of edges garnered by a node j in the time window (τ, τ+δτ), and γ is the obsolescence coefficient.

In the limit  γ-1<<t  (short memory), Eq. <ref> reduces to 

    dK_j(t)/dt≈η_j m(t)+q/γdK_j(t-1/γ)/dt

Equation <ref> is the first-order autoregressive model  where  time delay is 1/γ and q/γ is the first-order autoregressive parameter.<cit.>   Similar models  were suggested by Refs. <cit.> under the name of preferential attachment with gradually-vanishing memory.

In the limit  γ-1>>t (long memory),  Eq. <ref>  reduces to

    dK_j/dt≈η_j m(t)+qK_j(t)

This is nothing else but Eq. <ref> where the random-based search has been replaced by the fitness-based search. Equation <ref> is also similar to Eq. <ref> which describes preferential attachment with additive fitness. A similar model was suggested by Menczer.<cit.>  Thus, fitness pops out as an important ingredient of the recursive search model as well.



§ FITNESS-ONLY MODEL



Our analysis shows that all extensions and explanations of the preferential attachment mechanism eventually invoke fitness. While at the birth of the research field of complex networks  the node degree seemed to be the most important parameter  determining  growth dynamics,  subsequent studies focused more on node fitness.<cit.> This prompts us to consider generative mechanisms where fitness rather than node's degree  plays the key role.

One such mechanism was suggested by Caladarelli et al.<cit.>  who  assumed that the  probability of attachment between  a new node i and the target node j  is just Π_ij=f(η_i,η_j)  where  η_i and η_j  are node fitnesses,  and f(η_i,η_j) is the symmetric function of  its arguments (linking function). Ref. <cit.> considered additive linking function but the later publication of the same group <cit.> postulated multiplicative linking function, f(η_i,η_j)∼η_iη_j. The latter assumption became more popular and it allows the following generalization. Consider a target node j.  If fitness is determined by similarity  and  all nodes belong to the same community, then the node j will garner edges with the rate Δ K_j∝η_iη_j where η_i is the average fitness of incoming nodes. This average fitness can be absorbed into the aging function, in such a way that the probability of a new node i to attach to existing node j is

    Π_j∼η_jA(t_j).

The fitness-only approach  captured by Eq. <ref>  was  developed further by Refs. <cit.>. Although it seems to represent a radical deviation from  the preferential attachment model, in what follows  we demonstrate that this is not so. Under very general conditions,  these two approaches yield the same dynamics of  network growth.  In particular,  we demonstrate that if the fitness distribution is  broad, then the fitness-based attachment (Eq.
<ref>) yields the same growth dynamics as the preferential attachment model (Eq. <ref>) with δ=0. However, the  initial attractivity K_0 is not an arbitrary parameter anymore but is determined by the shape and width of the fitness distribution.




§ FITNESS MODEL WITH BROAD FITNESS DISTRIBUTION MIMICS PREFERENTIAL ATTACHMENT


Consider a directed acyclic network that grows according to  Eq. <ref>. We assign to each node a certain fitness η drawn from some distribution ρ(η) where  ∫_0^∞ρ(η)dη=1.  We further assume that the degree of each node grows according to an inhomogeneous Poisson process, in such a way that Δ K, the  number of edges garnered by a node  during time window (t,t+Δ t), is represented by the Poisson distribution Poiss(λ,Δ K)=λ^Δ K/Δ K!e^-λ  with the rate

    λ=η A(t)Δ t,


where  A(t) is the aging function, the same for all nodes, and the time t is counted from the moment when the node joined the network.  Equation <ref> leaves some ambiguity in the definition of the fitness η and aging constant A(t) since it includes only their product.  To raise this ambiguity, we define the aging constant in such a way that ∫_0^∞A(τ)dτ=1. Under this constraint, the physical meaning of fitness η is the long-time limit of node's degree, namely, η∼ K(t→∞).


Since Eq. <ref> is memoryless, the number of edges that each node garners through the period from t=0 to t also follows  Poisson distribution with the rate

    Λ =η∫_0^tA(τ)dτ.



We focus on the ensemble of N nodes that joined the network at the same time which we set as t=0. Among these nodes, the number of those that garnered K edges by time t is

    N(K,t)=N∫_0^∞Λ^K/K!e^-Λρ(η)dη,

where ρ(η) is the fitness distribution and Λ (η) dependence is given by Eq. <ref>. During time window (t, t+Δ t) each of these N(K,t) nodes garners ∼λ edges, in such a way that the  average number  of new edges garnered by each node from this subset is

    Δ K= N∫_0^∞λΛ^K/K!e^-Λρ(η)dη/N(K,t)

We substitute Eq. <ref> into Eq. <ref>, note that λ=ΛÃ(t), where Ã(t)=A(t)Δ t/∫_0^tA(τ) dτ, use the equality

    Λ Poiss(Λ,K)=(K+1)Poiss(Λ,K+1),

and come to

    Δ K|_K=Ã(t)(K+1)N(K+1,t)/N(K,t).

where N(K+1,t) is the number of nodes that after time t garnered  K+1 edges. If the fitness distribution is sufficiently broad, then N(K+1)≈ N(K)  for K>>1 (see Appendix) and  Eq. <ref> approaches asymptotically to

    Δ K=Ã(t)(K+1).

This expression is nothing else but the preferential attachment rule (Eq. <ref>) with  δ=1 and K_0=1. A similar result was obtained earlier by Burrell <cit.> using a different approach. In the continuous approximation, Eq. <ref> reduces to dK/dt=Ã(t)(K+1). This equation has uncanny resemblance to the famous expression for the photon emission rate for two-level atomic systems, dN_ph/dt=Bn_2(N_ph+1), where n_2 is the number of atoms in the upper state, N_ph is the number of photons, and  B is the Einstein coefficient  for stimulated  emission. Thus, K is the analog of N_ph and K_0 is the analog of spontaneous emission.



To validate  Eq. <ref>  through numerical simulation   we considered a set of 400,000 nodes  and simulated their growth using Eq. <ref>. We assumed a lognormal fitness distribution ρ(η)=1/√(2π)σηe^-(lnη-μ)^2/2σ^2 with μ=1.6 and σ=1.1, and the aging function A(t)=0.035t/|t-2.4|^1.3. The time was run from t=0 to t=25 with steps Δ t=1, in such a way that ∑_0^t=25A(t)=1.  For each node j in this set  we determined K_j(t),  the total number of  edges accumulated  after  time t, and Δ K_j(t), the number of additional edges gained at step t+1. For every  t we grouped all nodes into 40 logarithmically-spaced bins, each bin containing the nodes with close values of  K. For each bin, we determined Δ K-distribution  and found its  mean, Δ K. Figure <ref> plots  Δ K versus K+1, as suggested by Eq. <ref>. It is clearly seen that  this equation fits the data fairly well for K>>1. The fit at small K is less satisfactory but it can be improved by using Eq. <ref> with K_0 as a fitting parameter. We obtain
K_0=0.7, 0.8, 0.85 and 1 for t=2,3,7 and 24, correspondingly. Thus, anyway K_0∼ 1.








Figure <ref> shows Δ K(K+1) dependences for lognormal fitness distributions with different σ. These dependences  deviate
from Eq. <ref> for small K and we approximate them  as

    Δ K=Ã(t)(K+K_0),

where K_0 is the fitting parameter.   Equation <ref> indicates that at small K, Δ K→Ã(t)K_0.  On another hand, Eq. <ref> yields

    Δ K|_K=0=Ã(t)N(1,t)/N(0,t).

Thus,

    K_0≈N(1,t)/N(0,t)
    =∫_0^∞Λ e^-Λρ(Λ)dΛ/∫_0^∞ e^-Λρ(Λ)dΛ,

where ρ(Λ) follows the lognormal distribution with shifted  μ'=μ+log (∫_0^tA(τ) dτ). Since ∫_0^tA(τ) dτ)→ 1 in the long time limit, the difference between μ and μ' becomes increasingly small at long t. Figure <ref> shows K_0 calculated according to Eq. <ref>  as a function of μ and  σ. We observe that K_0 increases with μ and decreases with σ. These dependences can be captured by the approximate empirical expression

    K_0≈e^μ/1+σ/(1+σ^2)^0.6.

For reasonable values of μ=0-2 and σ=1-2, K_0 lies between 0.5 and 1.5. It is determined by σ, and, to a lesser extent, by μ. This means the following: if  K_0  is measured using Eq. <ref>  using extrapolation from large K, then  one always gets K_0=1. On another hand, since most fitness distributions are broad, the K_0 measured using Eq. <ref> for small K (as it is usually done in most studies) is not not exactly 1 but close to 1, somewhere between 0.5 and 1.5. Figure <ref> shows that for narrow fitness distribution,  K_0 can be higher.

We plot on Fig. <ref> the  measured values of K_0 which were inferred from our studies of citation dynamics of scientific papers published in 1984. We considered  three research fields: Physics, Economics, and Mathematics and found that the fitness distribution for all three fields is lognormal with different μ but the same, σ=1.1. The measured and calculated initial attractivities K_0 are in good agreement and are all close to 1.

Thus, our numerical simulation supports the preferential attachment (cumulative advantage) model with  initial attractivity K_0∼ 1, as it was postulated by de Solla Price.<cit.> The natural question arises- why  K_0∼ 1 is so widespread?  Figure <ref> shows that the corresponding fitness distribution shall have any μ between 0 and 2 but the width shall be  σ≈ 1.  Nguyen and Tran <cit.> showed by numerical simulation that if the complex network with a lognormal fitness distribution grows according to Eq. <ref>, then the power-law degree distribution with the exponent γ∼ 3 appears only for σ≈ 1. This observation implies that the initial attractivity is coupled to the exponent of the degree distribution, in such a way that the universality of initial attractivity K_0∼ 1 in growing networks is a by-product of the ubiquity of power-law degree distributions with γ∼ 3.




§ DISCUSSION



Our analysis shows that if  network growth is considered from the perspective of a target node and  is studied using the mean-field approximation, namely, by averaging over many similar nodes, one cannot distinguish between the preferential attachment and the fitness-only models - both of them yield  Eq. <ref>. Thus, in all that concerns the mean-field network dynamics, preferential attachment is equivalent to fitness-only  model, in other words, the rich-gets-richer mechanism reduces to the fit-gets-richer mechanism.<cit.>  This is surprising since these two models are based on different premises. The preferential attachment model assumes that all nodes are born equal, the inequality in their degree coming by chance. After this  inequality has been established, it is  amplified by the autocatalytic process  represented by Eq. <ref>. In contrast, the fitness model and the fitness-based recursive search model  assume that the nodes are born unequal, each newly born node is endowed with a certain fitness. The latent inequality in fitnesses becomes evident only after the nodes have been developing for some time. Surprisingly, the two opposing assumptions underlying network growth- all nodes are born equal or  different-  result in the same  growth equation,  Eq. <ref>.


This does not mean that the two models are equivalent. While the preferential attachment model does not specify the initial attractivity, the fitness-only model with aging explains it perfectly well- it is determined by the shape of the fitness distribution. With respect to the power-law degree distribution in complex networks: the preferential attachment relates its to the strategy by which the new node attaches to old nodes, while  the fitness model implies that this distribution is inherited from the fitness distribution.  The fitness model successfully explains the first-mover advantage, degree distribution for the nodes of the same age, different trajectories of the nodes of the same age, etc. However, this model does not account for the nonlinear dynamic growth rule that is observed in some networks. Most important, this model does not account for the network structure: it addresses neither clustering coefficient nor assortativity.





Although it could seem that the fitness-only model is more advantageous than the preferential attachment,  Eqs. <ref>,<ref> can still be valid since the preferential attachment is a structural rather than explanatory model.  Indeed, the relation Π_ij∼ K_j does not imply that a new node i crawls through the whole network in order to gain information about degrees of all other nodes j. What occurs in reality is that the network grows following some local  rule  and this rule becomes imprinted in the network  topology.  When the network growth is analyzed, the changes in topology are visible while the underlying microscopic growth rule is not. This feeds the illusion that  the growth dynamics is  determined by network topology while in reality the reverse is true. The challenge is to uncover the  microscopic rules of network growth that explain the resulting network  topology. This can't be done basing on Eq. <ref> since too many mechanisms yield the very same equation. Only truly microscopic measurements, such as  studying network growth from the incoming node's perspective, measuring autocorrelation and memory effects, can differentiate between the different  models. Our opinion is that the recursive search mechanism (which includes the fitness model as a particular case) is a best candidate to account for growth dynamics of many complex networks.


Does the recursive search mechanism exclude the genuine preferential attachment- namely, the algorithm whereby a new node finds well-connected older nodes and attaches to them?  It has been generally believed that the recursive search mechanism is one of realizations of this algorithm, since if a new node makes a  random choice among the neighbors of already chosen nodes, it has high probability of picking up a highly-connected node. We  demonstrate here (Eq. <ref>) that this strategy works in a straightforward way only if the recursive search does not have memory. In reality, recursive search has rather short memory,<cit.> and it is not clear whether highly-connected nodes can be found by this simple strategy: random choice among the neighbors of already chosen nodes.  We found <cit.>  that the recursive search follows a more clever strategy: the search in the network neighborhood of the previously chosen nodes is not random but has preference for those neighbors that are connected to several already chosen nodes.   The cartoon picture of such strategy is as follows. Simple recursive search: if Alice is linked to Bob, and Bob is linked to Frank, there is a chance that Alice will link to Frank. Clever recursive search:  if Alice is  linked to Bob and Charlie, and  both of them are  linked to Frank, then Alice will link to Frank almost for sure. Thus if a new node identifies a target node in the network vicinity of two or more previously chosen nodes, the probability of attachment to such node exceeds the sum of probabilities per each path, namely, multiple paths interfere constructively, reinforcing one another. The synergetic interaction between the paths to the next-nearest neighbors ensures that a new node finds highly-connected nodes. This strategy of exploring next-nearest neighbors  can still be considered as local strategy, but in fact, it is one step towards global search and this is the way how classical preferential attachment emerges in the recursive search.



§ ACKNOWLEDGMENTS

I am grateful to Lev Muchnik for valuable discussions.


§ APPENDIX

To explore the limits of  approximation K>>1 for which N(K+1)≈ N(K), we consider the ratio N(K+1,t)/N(K,t)=∫_0^∞Λ^K+1/(K+1)! e^-Λρ(Λ)dΛ/∫_0^∞Λ^K/K! e^-Λρ(Λ)dΛ and note  that for the uniform distribution, ρ(Λ)=const, the relation N(K)=N(K+1) is satisfied exactly for every K.  In order to study to what extent this relation holds for non-uniform  distributions, we assume  a lognormal distribution, ρ(Λ)=1/√(2π)σΛe^-(lnΛ-μ)^2/2σ^2.  Then N(K+1,t)/N(K,t)=∫_0^∞Λ^K+1/(K+1)! e^-Λe^-(lnΛ-μ)^2/2σ^2dΛ/∫_0^∞Λ^K/(K)! e^-Λ e^-(lnΛ-μ)^2/2σ^2dΛ. The expression  Λ^K e^-Λ, when considered as a function of Λ, is a bell-shaped function with a peak at Λ_max=K, the width of the peak being ΔΛ∼ K^1/2. The relative width of this peak is ΔΛ/Λ_max≈1/K^1/2  and for K>>1 it is much narrow than any lognormal distribution with σ>1. In this case, the lognormal function is almost constant across the peak of the function Λ^K e^-Λ and we can replace it by its value at the peak, Λ=Λ_max. Since ∫_0^∞Λ^K/(K)! e^-Λ=1 then, for K>>1, N(K+1,t)/N(K,t)≈ e^-(ln (K+1) -μ)^2-(ln K-μ)^2/2σ^2= e^-ln(1+1/K)ln K-μ/σ^2≈
e^-ln K-μ/Kσ^2. Since lnK/K<<1 for K>>1, then N(K+1,t)/N(K,t)≈ 1. Thus, the latter relation holds for K>>1 and σ>1.


