{'fraction_non_alphanumeric': 0.043457180769623356, 'fraction_numerical': 0.018321935286312135, 'mean_word_length': 4.205073714968788, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dynamical fitness models: evidence of universality classes for preferential attachment graphs

In this paper we define a family of preferential attachment models for random graphs with fitness in the following way: independently for each node, at each time step a random fitness is drawn according to the position of a moving average process with positive increments. We will define two regimes in which our graph reproduces some features of two well known preferential attachment models: the Bianconi-Barab\'asi and the Barab\'asi-Albert models. We will discuss a few conjectures on these models, including the convergence of the degree sequence and the appearance of Bose-Einstein condensation in the network when the drift of the fitness process has order comparable to the graph size.


Introduction
Preferential attachment models (PAMs) are a type of dynamic network that exhibits features observed in many real-life datasets, such as the power-law decay in the tails of the degree distribution (van der Hofstad 2016). Since the works Yule 1925, Simon 1955, one of the versions of preferential attachment graphs which became prominent is the Barabási-Albert model (Barabási and Albert 1999). In the simplest case, at each discrete time step a new node attaches itself to one of the already existing vertices with probability proportional to that vertex's degree. One of the main features of this model is the old-get-richer phenomenon, for which older vertices tend to accumulate higher degree. PAMs have been extended to allow for different attachment probabilities. In physics it is relevant to look at the following generalisation: each node comes into the network with an additional label called fitness, sampled at random. Now the attachment probability to a node is not only proportional to its degree, but to its degree times its fitness. This graph is called PAM with fitness, first introduced by Bianconi and Barabási 2001. We shall henceforth refer to this model as the Bianconi-Barabási model. One of the main interests in fitness models of preferential attachment is due to their link to a well-known phenomenon called "Bose-Einstein condensation" (Barabási 2016). Roughly speaking, condensation for a graph means that a small fraction of the nodes collects a sum of degrees which is linear in the network size. In physical terms this means that particles in a Bose-Einstein gas (corresponding to nodes in our graph) crowd at the lowest energy level (roughly corresponding to the fitness). It has been shown (Borgs et al. 2007, Dereich 2016, Dereich, Mailler, and Mörters 2017 Ortgiese 2014 are some of the many references) that under suitable conditions on the fitness distribution a condensate appears in the Bianconi-Barabási model. In recent years, applications for preferential attachment models with fitness went beyond physics. On the mathematical side, several variants of the Bianconi-Barabási model have been developed to study condensation and related phenomena (Garavaglia 2019, Haslegrave, Jordan, and Yarrow 2019, Haslegrave and Jordan 2016. On the modelling side they have been used to study the power-law exhibited by cryptocurrency transaction networks such as Bitcoins (Aspembitova et al. 2019), and citation networks (Garavaglia, van der Hofstad, and Woeginger 2017). The reason for this is that one can think that nodes represent agents and connections among them depend on their reputation (the degree) and their skills (the fitness). Studying properties of such networks can lead to better understanding of real-life phenomena. So far the fitness has been considered fixed in time. Clearly this may not be the case, for example when the skills of an agent increase in time via a learning-by-doing mechanism. Motivated by this, we want to define a family of PAMs with dynamical fitness. In our networks, the fitness F t (v) is allowed to vary over time, independently for each vertex i, according to a stochastic process that arises out of the sum of i.i.d. positive random variables . It turns out that by choosing the right summation scheme we are able to range between the Barabási-Albert and the Bianconi-Barabási model. More precisely, we start by showing that if the amount of increments is finite, we are able to compare our model to the Barabási-Albert and Bianconi-Barabási models by showing that some features resemble those of these benchmark cases (eg. expected asymptotic attachment probability). Furthermore, we investigate numerically the behavior of the degree sequence and show it is asymptotically close to that of the Barabási-Albert resp. Bianconi-Barabási model. Indeed the old-get-richer phenomenon is reinforced by the presence of larger fitness of older nodes. We continue by focusing on the Bianconi-Barabási model proving that condensation can be induced by summing sufficiently many increments. Provided the mean increment µ is less than 1/2 we can always find a fitness distribution ν( ) such that the Bianconi-Barabási model with that fitness condensates, in particular ν( ) is obtained via convolution of the increment distribution. However, for a larger mean increment condensation will not appear regardless of the growth of the fitness (as long as it is bounded in time), thus showing a phase transition at µ = 1/2. We then conjecture, and provide numerics in support, that this behavior carries over to our model as well. Finally, we conclude with several open problems and conjectures. In particular, we perform simulations suggesting the appearance of a condensate when the sum of the increments grows linearly in the network size. We inquire whether this phase transition is universal in the increment law. Drawing conclusions from our work, both mathematical and empirical evidence hints at the universal behavior of the Barabási-Albert and the Bianconi-Barabási model which appear to be stable under random, but bounded in time, perturbations of the attachment probability. The main challenge at present is that the study of random networks with fitness has been successfully carried through via a coupling with continuous-time branching processes (CTBP) and generalised Pólya's urns. However, our time-varying fitness corresponds to a change of the reproduction rate in each family of the associated CTBP, at every birth event, making the CTPB lose its Markovian properties and independence over families. Using the observation that the degree sequence corresponds to an element of a simplex, the theory of majorization turns out to be a good tool to control the quantities we are interested in. To the best of the authors's knowledge, majorization seems to be newly applied in the context of PAMs, although it has been widely used for other random graphs (Arnold 2007). Structure of the article. In Section 2 we describe the model we are considering and state our main Theorems, which are proved, together with auxiliary results, in Section 3. We describe some conjectures and numerical simulations in Section 4. We finally conclude with the remarks of Section 5.
Notation. For a random variable X we denote its expectation as µ X . We say that f (x) g(x) if there exist universal constants c r , c > 0 such that c g(x) ≤ f (x) ≤ c r g(x) for all x. We use the standard notation for graphs G t = (V t , E t ) where V t denotes the vertex set at time t and E t denotes the edge set. The degree of a node v at time t in a graph G = G t is indicated as deg t (v). We write w → v to indicate that node w is attached to node v in the graph G, and the bond between the two nodes is written as (w, v). We will use bold fonts for vectors. For denote the components of x in decreasing order, and let denote the decreasing rearrangement of x. We will use the Landau notation always with respect to a time parameter t → ∞. For a probability law ν we denote as ν (m) the m-convolution of ν. Finally, d TV denotes the total variation distance.

The model and main results
2.1. Definition of the model. We will now begin by setting up the definition of our preferential attachment graphs. In particular in this work we will construct random trees where at each time step a new node attaches itself to a previous one according to the preferential attachment rule given in Equation (2.1). The construction algorithm is the following: Algorithm 1 Construction of the preferential attachment graph 1: procedure GraphConstruction 2: initial step: 3: F 1 ← (F 1 (1), F 1 (2)) 5: recursive step:

6:
for i > 1 do 7: The choice of the initial graph G 1 is arbitrary and does not affect our results. The random variable is the partition function at time t. Note also that we label a vertex by its arrival time in the graph. This mapping is valid since our graph is a tree. Therefore we will interchangeably use u, v, w, . . . as names of vertices or as times in the graph evolution without risk of confusion.
The new feature of our model is that fitnesses randomly vary in time according to a specific discrete-time stochastic process whose definition is given in Definition 2.1.
The law of is denoted by ν. In the present work, we assume that supp(ν) ⊂ [0, 1], as common in the literature on condensation for preferential attachment models with fitness (Borgs et al. 2007, Dereich, Mailler, and Mörters 2017, Haslegrave, Jordan, and Yarrow 2019. According to the choice of α, (2.2) spans a rich variety of stochastic processes. Some notable ones are a) the i.i.d. sampling from the law ν if α = (0, . . . , 0, 1), namely for every v one has Observe that, for fixed v and i, c) The random walk with positive increments for α = (1, . . . , 1). d) When α = (1, . . . , 1 m , 0, . . . , 0) with m < ∞ the fitness is a finite sum of increments e) When α = (1, 0, . . . , 0) we obtain a time-independent fitness such that for every v one has F i (v) = v+1 (v) for all i ≥ v + 1. The classical Bianconi-Barabási model corresponds to e). On the other hand of the spectrum, we will provide evidence (see Section 4) to support the conjecture that the model in Case a) resembles a Barabási-Albert model. In our opinion this motivates the choice of the summation scheme in (2.2) since it allows for a possible interpolation between the Bianconi-Barabási and the Barabási-Albert models. In the next Subsection we will indeed identify two regimes in which the behavior of our model follows closely that of the Bianconi-Barabási resp. Barabási-Albert graphs.

Identification of two regimes.
The relevance of our model lies in the fact that, by a suitable tuning of the vector α, we can construct two families of graphs that will either behave roughly like the Bianconi-Barabási or the Barabási-Albert models. Therefore, our graph can be used as a tool to test the universality of these two models. The first step is to partition our family of graphs into suitable regimes where the associated graphs share some features. Subsequently we identify, wherever possible, a representative benchmark for the class which will be either the Bianconi-Barabási or the Barabási-Albert. In order to define properly the regimes, we introduce a parameter m ∈ N that roughly measures the total number of summed increments in (2.2). More precisely, m represents the length of a block of 1's in vector α. Note also that m may depend on the graph size. According to the position of the block three fitness categories are identified which in turn define the following graph regimes: Definition 2.2 (R1 graph). Let m fixed. The class R1 is the class of all graphs G t evolving according to Algorithm 1 with fitness for every node v.
Definition 2.3 (R2 graph). Let m fixed. The class R2 is the class of all graphs G t evolving according to Algorithm 1 with fitness for every node v.
Definition 2.4 (R3 graph). Let m(t) be a N-valued function of the graph size t which is increasing and unbounded. The class R3 is the class of all graphs G t evolving according to Algorithm 1 with fitness for every node v.
A few remarks are now due: Remark 2.5 (On R1). The fitness process of the class R1 covers Cases a)-b). We will show that in this regime a Barabási-Albert-like behavior emerges.
Remark 2.6 (On R2). The fitness process of the class R2 covers Cases d)-e). We will show that in this regime a BB-like behavior emerges. Indeed, we recover a model similar to the BB in the following sense: nodes after m steps stop adding increments and start behaving as if they were in a Bianconi-Barabási graph with fitness law ν (m) .
Remark 2.7 (On R3). The fitness process of the class R3 includes Case c) which can be obtained by setting m(t) = t in Definition 2.4. Clearly other functions can be used, for example m(t) = log t . As we shall see, according to the speed of the chosen function different behaviors will arise especially regarding the phenomenon of condensation. One may also wonder what happens when one chooses a fitness process as When m(t) = t (2.6) and (2.5) coincide. Any other other choice of m(t) in (2.6) is uninteresting for the purposes of our study (for example, we will see that the phenomenon of condensation is trivial in this case).
Before giving our main results, we conclude this Subsection with heuristics on the "rich-getricher" phenomenon, a characterising property of preferential attachment models. Note that for every regime the expected fitness of vertex v at time t is where m can also depend on t. It is clear from (2.7) that older nodes have a higher fitness on average, thus reinforcing the idea that the old-get-richer phenomenon is likely to be preserved in our family of models. We now turn to the main results of the paper. We will start by studying the phenomenon of condensation (defined precisely in Subsection 3.1.2). Then we will move to the attachment probability.
2.3. Condensation. The first result for condensation concerns the classical Bianconi-Barabási model and shows that condensation can be enforced by a convolution operation. More specifically, given a fitness distribution in a Bianconi-Barabási model with mean less than 1/2, we will prove that the graph in Definition 2.8 whose fitness is the m-convolution condensates for m large enough. On the other hand, if the mean is larger or equal to 1/2, condensation does not appear. This result provides new insight on the heuristic behind condensation. Since this phenomenon requires more "rarified" high fitness population (Borgs et al. 2007), the convolution, which increases the tail decay rate of the distribution, will favor condensation. On the other side, if the mean is too high, mass will not escape from the upper endpoint of the distribution, countering the appearance of the condensate. Therefore, there is a trade-off between these two mechanisms, which results in a phase transition at 1/2. We now make the above reasoning rigorous. We introduce a family of Bianconi-Barabási graphs parametrized by the convolution of the fitness law, that is, given a probability distribution ν in [0, 1], we call BB(m) a Bianconi-Barabási graph with fitness law ν (m) .
Definition 2.8 (BB(m) graphs). Let m ∈ N. We denote BB(m) a preferential graph evolving according to Algorithm 1 with We stress that the fitness distribution is independent of time and is distributed as the convolution ν (m) . Taking m = 1 one obtains a Bianconi-Barabási model with fitness . In the sequel, we will refer as "Bianconi-Barabási models" to any graph constructed via Algorithm 1, and we will use the notation BB(m) when it will be important to stress the dependence on the convolution.
Proposition 2.9. Assume that the probability distribution ν of the fitness increment satisfies Then there exists m * ∈ N such that BB(m * ) condensates.
The second result instead is relative to the R1 regime of our model. It states that in this case condensation does not occur.
Theorem 2.11. No condensation occurs for graphs in Regime R1.
When trying to prove a similar result for Regime R2 one faces additional difficulties. The main one is that one needs to control the empirical degree distribution, but the available techniques relying on continuous-time branching processes fail because of the interdependence among the branching rates of the particles represented by the vertices in our context. However, numerical simulations we performed in Section 4 show that when BB(m) condensates, the corresponding graph in R2, which sums the same m increments, will also condensate.
2.4. Evolution of the attachment probability. We now state three Propositions regarding the behavior of the attachment probability for our graphs. The main challenge lies in the fact that the attachment probability depends on the fitness, so it is a random object as well.
In particular the role of Proposition 2.12 is to justify why in Regime R1 we expect a behavior reminiscent of the Barabási-Albert model. Indeed, the refresh of the fitness after m steps will imply that on average we attach new nodes with a probability proportional only to the degree multiplied by a constant, the mean increment. This mirrors the behavior in the Barabási-Albert graph where no fitness is present. More formally, we show where the error is a.s. in t.
Note that in (2.11) there is no equality sign, but we are off by a multiplicative factor as the proof will show. Proposition 2.13 shows that the attachment probability in Regime R2 depends on the fitness distribution, resulting in the naming "Bianconi-Barabási-like" case.
Finally, when m depends on t (the R3 case) we cannot refer to any benchmark model so it is natural to investigate the attachment probability in this case too. In particular we observe a behavior more similar to the Barabási-Albert model. This is due to the fact that, essentially as a consequence of the law of large numbers, the fitness may be replaced by a constant, its mean, thus cancelling out in the numerator and denominator of the attachment probability.
Proposition 2.14. Let G t be a graph in Regime R3. Then s. and L 1 . (2.12) Remark 2.15. We notice in passing that when the fitness is distributed as in (2.6) the result of Proposition 2.14 carries over as well.
3. Proofs of the results 3.1. Preliminaries. The two main tools we use to study preferential attachment graphs are the majorization order and some results in the theory of branching processes. Although by no means complete, we wish to recall here the basics we are going to employ in our work. 3.1.1. Majorization. Majorization is a tool which was first introduced in Hardy, Littlewood, and Pólya 1929. We refer the interested reader to the monography Marshall, Olkin, and Arnold 1979 for a complete overview.
Definition 3.1 (Majorization order). For two vectors u, v ∈ R d + we will write u ≺ v ("v majorizes u"), if and only if the following is satisfied: We will call Majorization becomes a useful tool in random graphs because it provides a way to control functions whose domain is a simplex, and since the degree sequence satisfies ∑ t v=1 deg t (v) = 2(t − 1) for trees we can apply majorization to find maxima and minima of appropriate quantities. In particular, we will look at Schur-convex functions, which are are isotonic with respect to the majorization order (see Marshall, Olkin, and Arnold 1979, Definition A.1, Section 3). One such function is the partition function of the attachment probability at time t.
3.1.2. Condensation and continuous-time branching processes. Condensation can be defined rigorously in several ways. The first definition we use requires the introduction of the upper end-point of the fitness distribution ν: To restrict ourselves to interesting cases, we assume there is no atom at the upper end-point, that is, ν{h(F )}) = 0. The standard approach to study condensation is the embedding of preferential attachment graphs into continuous-time branching processes. This technique goes back to Athreya andKarlin 1968, Bhamidi 2007 In this case the weighted empirical fitness distribution converges as t goes to infinity to the sum of an absolutely continuous 1 part, called the bulk, and a Dirac mass in the essential supremum of the support of the fitness distribution, called the condensate. By viewing the CTBP as a reinforced Pólya's urn, it is also possible to study condensation by establishing the strict positivity in the limit of the cumulative degree for vertices with high fitness. This is in fact the first approach to the mathematical study of condensation, pioneered by Borgs et al. 2007, see also Freeman and Jordan 2018.
Condensation is based on the behavior of the functional as t → ∞ (firstly) andh → h (secondly). Models that do condensate are those for which We remark that these conditions to define condensation have been investigated only in the cases of static fitnesses. It is for example possible to see without difficulty that (3.3) is satisfied for F t such that lim t→∞ F t = +∞ a.s. and for which an m-Markov property holds, as one first takes the limit in t and then inh. This is the reason why we are not interested in studying models with fitness process given in (2.6).

Auxiliary lemmas.
3.2.1. Condensation. The next Lemma shows that for the BB(m) model defined in Definition 2.8 condensation is monotone under the convolution operation. Namely, once observed, the phenomenon of condensation is not disrupted by adding more increments in the fitness.
Proof. Without loss of generality we can assume m 1 = 1, m 2 = 2. The proof will proceed similarly for 1 < m 1 < m 2 by a repeated application of the arguments below. We assume also that the law ν of the fitness of BB(1) is normalised so that supp(ν) = [0, 1]. In order to prove the result we will verify the condition of condensation (3.1). We have, by assumption, and we have to show Mind that under ν (2) one has X = X 1 + X 2 with each X i ∼ ν and independent from each other. We introduce the notation x m := (x 1 , . . . , x m ). We rewrite (3.5) as 2 0 x 2 where a m := ( 1 /m, . . . , 1 /m m , 0, . . . , 0) ∈ R m+ , ∈ N. In the present case we choose m = 2, = 0. Consider the function This function is Schur-convex in D 2 as one can see by applying Marshall, Olkin, and Arnold 1979, Theorem A.3, Section 3: (3.7) The derivative in each (a 2 ) i can be taken inside the integral since the integrand is C 1 in the domain D 2 × [0, 1) 2 . Note also that ∂ϕ ∂(a 2 ) 1 (a 2 ) = ∂ϕ ∂(a 2 ) 2 (a 2 ). Therefore by definition of Schurconvexity and the fact that a m a m−1 it follows that which implies (3.5).
As a part of the proof (and we will name it Corollary) we have obtained the following: Corollary 3.3. For i, j ∈ N, the function ϕ of (3.6) satisfies ϕ(a i ) ≤ ϕ(a j ) if i ≥ j.
Proof of Proposition 2.9. Without loss of generality we assume that ν is such that BB(1) does not exhibit condensation (otherwise m * = 1). To show that the model condensates for some m * ∈ {2, 3, . . .}, we observe that for a random vector Now notice that (3.1) can be rewritten using (3.8) as (3.10) From X ↓ fix a realisation x ↓ . Consider the function As shown for ϕ of (3.6) in (3.7), one can prove that Φ is Schur-convex, so that, for fixed x ↓ , Φ(a m ) is decreasing in m. This enables us to say that using the monotone convergence theorem in the last step (applicable by (2.8) and the monotonicity of Φ). We can now show the right-hand side of (3.12) equals µ /(1 − µ ) using (3.10) and the strong law of large numbers. This yields that E X m 1−X m : m ∈ N is a bounded decreasing sequence converging to µ /(1 − µ ). This implies the result.

Attachment probability.
A classical result we need to quote is the following. Its proof can be found in Hardy, Littlewood, and Pólya 1952, Theorem 368, Section 10.2.
Lemma 3.4 (Rearrangement inequality). For every n ∈ N, every sequence of real numbers x 1 ≤ x 2 ≤ . . . ≤ x n , y 1 ≤ y 2 ≤ . . . ≤ y n and every permutation σ ∈ S n it holds that In order to treat the attachment probability, we need to have control on the partition functions. We will do so using majorization in Regimes R1-R3.
Lemma 3.5. Let Z t := ∑ v∈V t−1 F t (v) deg t−1 (v) be the partition function of (2.1) of models in Regimes R1-R3. Then the following holds: where the constants in the asymptotic upper and lower bounds are deterministic.
Proof. The proof is based on the following two steps: (1) first we find two matching a.s. upper and lower bounds for Z t that involve roughly the same sum of independent and identically distributed random variables.
(2) Secondly we show by the strong law of large numbers that the sum behaves asymptotically like mt. Let us begin with the two bounds. Using the fact that the degree is always at least one, we can bound Z t from below by (3.13) We then look for a similar bound from above. Let us rename the vertices v ∈ V t−1 in such a way that deg t (v) = deg t, ↓ (v). Namely we rearrange the degree sequence in decreasing order. Therefore for some permutation σ ∈ S t by the Rearrangement Inequality of Lemma 3.4. Now (deg t, ↓ (v)) ∈ D * := {x ∈ D t : is a.s. Schur-convex in D * by Marshall, Olkin, and Arnold 1979, Theorem A.3, Section 3. Therefore it attains its maximum at the maximal element for the majorization order in the simplex D * (Marshall, Olkin, and Arnold 1979, Prop. H.2.a, Section 3). It is straightforward to identify this element as Given (3.15), we invoke (3.14) to argue that with probability one We have thus obtained (3.13) and (3.16) which have the same order of magnitude as t grows.
We will then study only the asymptotics for (3.13), the other bound being very similar. We begin by observing that, for every v ∈ V t−1 , where we have relabeled the increments 2 and numbered them until Equation (3.17) holds for any regime because the total number of increments is the same. Equation (3.18) is going to infinity for m ≤ t. Then by the strong law of large numbers, for every η > 0 we can find an a.s.
Choose then t 0 = t 0 (η) in a set of probability one such that L ≥ L 0 for t ≥ t 0 (this is possible since L is an explicit function of t). Therefore we obtain an almost-sure bound of the form This concludes the proof.

Proofs of the main results.
Proof of Theorem 2.11. For a preferential attachment model with fitness, we have that where D v, m := {t ≥ t − m : t → v} is a random variable bounded almost surely by m. Thus recalling the definition Vh := {v ∈ V t : F t (v) ≥h}, we have that E[Mh] is bounded above by (3.21) Here we have used the fact that F t (1) is independent of the sigma algebra σ(G t−m−1 ) (the fitness has the m-Markov property) and that the sum of the degrees up to t − m − 1 is deterministic. Furthermore, we notice that, due to the independence of the fitnesses over vertices, one has as t → ∞ andh → h. We justify (3.22) since for every node v ≤ t − m the fitness is a sum of m i.i.d. increments. These two observations combined prove that, for m constant, (3.21) converges to 0. Proof of Proposition 2.12. We recall the bound for t large enough from Lemma 3.5. Thus using the left-hand side of (3.23) one can rewrite the expected attachment probability as where D v, m is as in (3.20). The a.s. bound on D v, m and the fact that E[F t (v)] = µ m yield that the second summand in (3.24) is O(1/t) with probability one. As for the first summand, note that deg t−m (v) and F t (v) are independent. Therefore we obtain that .
The other bound can be obtained in the same way from the right-hand side of (3.23).
Proof of Proposition 2.13. The result follows by applying Lemma 3.5 to the partition function of the attachment probability.
Proof of Proposition 2.14. Using again the right-hand side of (3.23) we get and that F t (v)/(µ m) converges to one by the strong law of large numbers with probability one. Hence by dominated convergence theorem one can argue that This shows that t is a random variable that is asymptotic in L 1 and a.s. to µ µ + 1 .

Conjectures
The condensation phenomenon and the attachment probability hint at the fact that the Barabási-Albert and the BB(m) models represent benchmarks. However, these two quantities are not sufficient to establish a full universality result. Therefore we believe that investigating other aspects of interest can strengthen our claim. We will devote this Section to the numerical study of some additional observables of our graph and the relation with the benchmark models. We focus on the degree distribution and the condensation phenomenon. As for the former, since the results on the attachment probability are local, in the sense that they hold for fixed vertices, looking at the degree distribution gives broader information on the network. As for the latter, we want to verify whether the threshold for the appearance of condensation derived in Proposition 2.9 for the BB(m) is mirrored in our model in Regime R2. Finally, since to the best of the authors' knowledge there is no reference in the literature to preferential attachment models with fitness as in Regime R3, we want to shed light on the behavior of condensation in this case.

Degree distribution.
We now present the numerical results for the degree distribution in Regimes R1 and R2. We will show that the total variation distance between the degree distribution of our model and the benchmarks vanishes asymptotically in the graph size. We chose the total variation distance, other than for its numerical tractability, also because it implies the convergence of the laws. (4.1) The limit is taken a.s. in the fitness realisation for G t .
In Figure 1 we plot the mean of the total variation distance (4.1) averaged over 100 Monte Carlo simulations with m = 1 and ∼ U(0, 1) for different graph sizes. Since our result is quenched in the fitness, we are keeping the same realization of the fitnesses and averaging the total variation distance over the Monte Carlo trials. Due to the convergence of (4.1) we are also conjecturing that the asymptotic survival function of the degree distribution is close to a power law with exponent τ = 2, as in the standard Barabási-Albert model (van der Hofstad 2016, Section 8.4). We then compare the tail exponent of the survival function of the degree distribution between our model in R1 and the Barabási-Albert model in Figure 2.   (4.2) The limit is taken a.s. in the fitness realisation of G t .
In Figure 3 we plot the mean total variation distance (4.2) over 100 Monte Carlo simulations with m = 5 resp. m = 10 and ∼ Beta(1, 3) for various graph sizes. As in the AB case, the fitness realisation is kept fixed over the various Monte Carlo trials. As a comparison, observe in Figure 4 the behavior of the mean total variation distance between our model in Regime R2 with m = 1 and a BB(1) averaged over 100 Monte Carlo simulations.
Again this hints at the fact that the way in which fitnesses increase is substantially uninfluential on the growth of the network, provided we sum finitely many increments. This also shows that the BB(m) model is robust under dynamical perturbations.  2) between our model with m = 5 and a BB(1), ∼ Beta(1, 3). Right: mean total variation distance (4.2) between our model with m = 2 and a BB(1), ∼ U(0, 1). In both cases the mean total variation does not approach zero.

Condensation.
We now present the numerical results on condensation in Regimes R1-R3. To do so, we will plot the cumulative degree of the nodes grouped by fitness. In this setting, based on the argument outlined in the Introduction, we expect to see condensation when the landscape of the above has more and higher spikes concentrated towards the upper end point of the fitness law.
To begin with, recall that by Theorem 2.11 no condensate appears in Regime R1. Indeed, when picturing condensation using the cumulative degree grouped by fitness (see Figure 5) one can notice that the position of the spikes varies on the whole support of the distribution. This is due to the the m-Markov property. We now turn our attention to Regimes R2 and R3.
4.3. Condensation for R2. Given Conjecture 4.2 on the asymptotic degree distribution, we formulate a conjecture on the condensation for R2 models.   ∼ Beta(1, 3). Observe that the location of the highest spike of the degree does not escape towards the supremum of the fitness but is randomly shuffled.
We will support the above conjecture with a few simulations. We recall (Borgs et al. 2007, Appendix C.3) that in a BB(1) model the fitness distribution Beta(α, β) condensates if and only if β > α + 1. In Figure 6 one can observe the absence of a condensate for U(0, 1)distributed increments and m = 1. In Figure 7 a condensate appears for the increment distribution Beta(1, 1.9) when m = 2. Note finally in Figure 8 that there is no condensation for Beta(3, 1)-distributed increments for m = 5. Since in this case µ = 3/4 > 1/2 the threshold in Proposition 2.9 seems to be binding in R2 as well. Figure 6. Cumulative degree in fitness intervals for Regime R2 with m = 1, ∼ U(0, 1). Note that the degree distribution per fitness becomes smoother at the right endpoint of the fitness distribution. This model is known not to exhibit condensation. Figure 7. Cumulative degree in fitness intervals for Regime R2 with m = 2 with ∼ Beta(1, 1.9). In this case, higher spikes appear as the graph size increases towards the upper endpoint of the fitness distribution. Recall that the classical Bianconi-Barabási model does not condensate for Beta(1, 1.9)distributed fitness. Figure 8. Cumulative degree in fitness intervals for Regime R2 with m = 5, ∼ Beta(3, 1). The degree distribution per fitness appears without peaks as the graph increases and no condensates forms.

Condensation in Regime R3. The case in which m(t)
1 presents an interesting open problem which is illustrated in the following simulations. In Figures 9-11 we are plotting the cumulative degree for nodes grouped by fitness with U(0, 1) increments in the regimes m = log t , √ t , t respectively. As one can see, the limiting fitness distribution resembles the cumulative fitness distribution for the first two cases, while in the m = t regime a spike appears at µ t. As stated at the beginning of Subsection 4.2, in this kind of plots condensation is indicated by the presence of spikes around the supremum of the fitness. Looking at Figures 9-10 there are no peaks and the landscape of the empirical fitness distribution resembles the cumulative degree grouped by fitness. On the other hand, in Figure 11 the two quantities are different: the cumulative degree by fitness exhibits a spike roughly around µ t, t = 100000, and the empirical fitness distribution seems to be uniform in [0, µ t]. Heuristically, a uniform law appears because by summing a linear number of increments the central limit theorem kicks in, so that each node has roughly a Gaussian fitness. More precisely, for most nodes i the fitness is close in law to N (µ (t − i), σ 2 (t − i)), where σ 2 is the variance of the increments. Therefore, by Gaussian concentration properties around the mean, we see a fitness landscape close to a uniform in [0, µ t]. Based on the above considerations, we expect that the speed at which m(t) grows in time influences the appearance of a condensate. Namely, if m(t) is too slow, condensation cannot be enforced, while a faster m(t) leads to Bose-Einstein condensation. Because of the scaling of the central limit theorem, we conjecture m(t) = Θ(t) to be the threshold for condensation in R3. This is summarised in the following conjecture: Conjecture 4.4. If m(t) = Θ(t) R3 exhibits condensation with the cumulative fitness distribution having an atom at µ t. Figure 9. Cumulative degree grouped by fitness in Regime R3 with m = log 2 t with ∼ U(0, 1) Bottom picture: empirical fitness distribution corresponding to the last cumulative degree plot. Notice that the empirical fitness distribution resembles the cumulative degree by fitness. The plots exhibit no spike. Figure 10. Cumulative degree grouped by fitness in Regime R3 with m = √ t with ∼ U(0, 1) Bottom picture: empirical fitness distribution corresponding to the last cumulative degree plot. Notice that the empirical fitness distribution resembles the cumulative degree by fitness. The plots exhibit no spike. Figure 11. Cumulative degree grouped by fitness in Regime R3 with m = t with ∼ U(0, 1). Bottom picture: empirical fitness distribution corresponding to the last cumulative degree plot. As expected, the fitness distribution is uniform in [0, µ t]. In particular µ = 1/2, t = 100000, and µ t ≈ 50000.
We expect our results to be universal regardless of the increment distribution. In order to properly address this topic, we need to identify two fitness families. Mailler, Mörters, and Senkevich 2019 propose two fitness categories in the context of competing growth processes and dynamical networks. The difference arises essentially in the behavior at the maximal fitness value (regular variation vs. exponential behavior) that implies a different treatment of the two regarding condensation. The families are: i) bounded random variables in the maximum domain of attraction of the Weibull distribution eg. Beta distribution (Embrechts, Klüppelberg, and Mikosch 2013, Section 3.3.2); ii) bounded random variables in the maximum domain of attraction of the Gumbel distribution eg. those with survival function (Embrechts, Klüppelberg, and Mikosch 2013, Section 3.3.3). F(x) = exp(−x/(1 − x)), x ∈ [0, 1]. (4.3) So far we have used in our simulations Beta-distributed increments. In order to better support our claims, we provide a realisation of our model in R3 with increments belonging to Class ii). Namely, we will use increments distributed as (4.3). As one can notice, the behavior shown in Figure 12 is qualitatively similar to Figure 11. The intuition behind this is that the central limit theorem works regardless of the initial increment distribution. Figure 12. Cumulative degree grouped by fitness in Regime R3 with m = t with increments distributed as (4.3). Bottom picture: empirical fitness distribution corresponding to the last cumulative degree plot. As expected, the fitness distribution is uniform in [0, µ t]. In particular µ = 1/2, t = 100000, and µ t ≈ 50000.

Concluding remarks
As mentioned in the Introduction most the main tools (urn models, continuous-time branching processes etc) developed to analyze preferential attachment models with fitness are still not able to treat dynamical fitness models. This is why the behavior of these models poses an interesting mathematical challenge. In this paper we started the investigation, both mathematical and empirical, of these models. We believe that a rigorous analysis of dynamical fitness preferential attachment graphs can shed light on the existence of universality classes for random graphs. In particular this can justify the use of the Barabási-Albert and the Bianconi-Barabási models in applications. As an example, since the attachment probability of a graph is hard to estimate, knowing that the benchmark models are robust under bounded fluctuations of the fitness makes them suitable to fit observed networks. Finally, a rigorous study of Regime R3 is advocated. The reason for this is that it creates a new universal model where the phase transition seems not to depend anymore on the fitness but rather on the speed of the fitness growth.