{'fraction_non_alphanumeric': 0.038026315789473686, 'fraction_numerical': 0.011096491228070176, 'mean_word_length': 4.115772941440431, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Generalized preferential attachment: tunable power-law degree distribution and clustering coefficient

We propose a wide class of preferential attachment models of random graphs, generalizing previous approaches. Graphs described by these models obey the power-law degree distribution, with the exponent that can be controlled in the models. Moreover, clustering coefficient of these graphs can also be controlled. We propose a concrete flexible model from our class and provide an efficient algorithm for generating graphs in this model. All our theoretical results are demonstrated in practice on examples of graphs obtained using this algorithm. Moreover, observations of generated graphs lead to future questions and hypotheses not yet justified by theory.


Introduction
Numerous random graph models have been proposed to reflect and predict important quantitative and topological aspects of growing real-world networks, from Internet and society [1,4,7] to biological networks [22]. Though largely successful in capturing their key qualitative properties, such models may lack some important characteristics. An extensive review can be found elsewhere (e.g., see [1,4,5]). Such models are of use in experimental physics, bioinformatics, information retrieval, and data mining.
The simplest characteristic of a vertex in a network is the degree, the number of adjacent edges. Probably the most important and the most extensively studied property of networks is their vertices degree distribution. For the majority of studied real-world networks, the portion of vertices with degree d was observed to decrease as d −γ , usually with γ > 2, see [3,4,8,14]. Such networks are often called scale-free.
Another important characteristic of networks is their clustering coefficient, a measure capturing the tendency of a network to form clusters, densely interconnected sets of vertices. Various definitions of the clustering coefficient can be found in the literature, see [5] for a discussion on their relationship. We define the clustering coefficient of a graph G as the ratio of the triple number of triangles to the number of pairs of adjacent edges in G. For the majority of networks, the clustering coefficient varies in the range from 0.01 to 0.8 and does not change much as the network grows [4]. Modeling real-world networks with accurately capturing not only their power-law degree distribution, but also clustering coefficient, has been a challenge. We discuss this in detail in Section 2.
In order to combine tunable degree distribution and clustering in one model, some authors [20,21,22] proposed to start with a concrete prior distribution of vertex degrees and clustering and then generate a random graph under such constraints. However, adjusting a model to a particular graph seems to be not generic enough and can be suspected in "overfitting". A more natural approach is to consider a graph as the result of a random process defined by certain reasonable realistic rules guaranteeing the desired properties observed in real networks. Perhaps the most widely studied realization of this approach is preferential attachment. In Section 2, we give a background on previous studies in this field.
In this paper, we propose a new class of preferential attachment random graph models thus generalizing some previous approaches. We provide theoretical study, proving the power law for the degree distribution and approximating the clustering coefficient of the resulting graphs. We also propose an efficient algorithm realizing a concrete flexible model from our class with tunable both the power-law exponent and the clustering coefficient. All our theoretical results are verified experimentally with utilization of our algorithm. Moreover, observations of generated graphs lead to future questions and hypotheses not yet justified by theory.
The remainder of the paper is organized as follows. In Section 2, we give a background on previous studies of preferential attachment models. In Section 3, we propose a definition of a new class of models, and obtain some general results for all models in this class. Then, in Section 4, we describe one particular model from the proposed class and provide an efficient algorithm, which generates graphs in this model. We demonstrate results obtained by generating graphs in this model in Section 5. Section 6 concludes the paper.

Preferential Attachment Random Graph Models
In 1999, Barabási and Albert observed [3] that the degree distribution of the World Wide Web follows the power law with the exponent approximated by −2.1. As a possible explanation for this phenomenon, they proposed a graph construction stochastic process, which is a Markov chain of graphs, governed by the preferential attachment. At each time step in the process, a new vertex is added to the graph and is joined to m different vertices already existing in the graph chosen with probabilities proportional to their degrees.
Denote by d n i the degree of the vertex i in the growing graph at time n. For at each step m edges are added, we have i d n i = 2mn. This observation with the preferential attachment rule imply that Note that the condition (1) on the attachment probability does not specify the distribution of m vertices to be joined to, in particular their dependence. Therefore, it would be more accurate to say that Barabási and Albert proposed not a single model, but a class of models. As it was shown later, there is a whole range of models that fit the Barabási-Albert description, but possess very different behavior.
In [6], Bollobás and Riordan proposed a concrete precisely defined model of the Barabási-Albert type, known as the LCD-model, and proved that for d < n 1 15 , the portion of vertices with degree d asymptotically almost surely obeys the power law with the exponent −3. Recently Grechnikov substantially improved this result [15] and removed the restriction on d. It was shown also that the expectation of the clustering coefficient in the model is asymptotically proportional to (log n) 2 n and therefore tends to zero as the graph grows [5]. One obtains a natural generalization of the Barabási-Albert model, demanding the probability of attachment of the new vertex n + 1 to the vertex i to be proportional to d n i + β, where β is a constant representing the initial attractiveness of a vertex. Buckley and Osthus [9] proposed a precisely defined model with a positive integer β. Móri [17] generalized this model to real β > −1. For both models, the degree distribution was shown to follow the power law with the exponent −(3 + β) in the range of small degrees. The recent result of Eggemann and Noble [13] implies that the expectation of the clustering coefficient in the Móri model with β > 0 is asymptotically proportional to log n n . For β = 0, the Móri model is almost identical to the LCD-model. Therefore authors of [17] emphasize the confusing difference between clustering coefficients ( (log n) 2 n versus log n n ). The main drawback of the described preferential attachment models is unrealistic behaviour of the clustering coefficient. In fact, for all the proposed models the clustering coefficient tends to zero as a graph grows, while in the real-world networks the clustering coefficient is approximately a constant [4].
A model with asymptotically constant clustering coefficient was proposed by Holme and Kim [16]. However, experiments and empirical analysis show that the degree distribution in this model obeys the power law with the fixed exponent close to −3, which does not suit most real networks.
In the next section, we propose a new class of preferential attachment models with the power-law degree distribution. Further we consider a particular model in this class, which allows to tune both the power-law exponents and the clustering coefficient by varying its parameters.

Theoretical Results
In this section, we define a general class of preferential attachment models. For all models in this class we are able to prove the power-law degree distribution. We also estimate the number of pairs of adjacent edges in models from this class and therefore can analyze the behavior of the clustering coefficient as the network grows.

Definition of the P A-class
Let G n m be a graph with n vertices {1, . . . , n} and mn edges obtained as result of the following random graph process. We start at the time n 0 from an arbitrary graph G n0 m with n 0 vertices and mn 0 edges. On the (n + 1)-th step (n ≥ n 0 ), we make the graph G n+1 m from G n m by adding a new vertex n + 1 and m edges connecting this vertex to some m vertices from the set {1, . . . , n, n + 1}. Denote by d n i the degree of a vertex i in G n m . If for some constants A and B the following conditions are satisfied then we say that the random graph process G n m is a model from P A-class. Condition (5) means that the probability to have a loop in the vertex is small.
Since we add m edges at each step, we obtain 2mA + B = m (summing up the equality (3) over all the vertices). Furthermore, we have 0 ≤ A ≤ 1, since the probabilities defined in (2-5) must be positive for all d n i ≥ m and all n. Here we want to emphasize that we indeed defined not a single model but a class of models. In fact, there is a range of models possessing very different properties and satisfying the conditions (2)(3)(4)(5). For example, the LCD-model belongs to P A-class with A = 1/2 and B = 0. The Buckley-Osthus one is also from P A-class with A = 1 2+β and B = mβ 2+β . Another example is considered in detail in Sections 4 and 5. This situation is somewhat similar to that with the definition of the Barabási-Albert models, though our class is wider in a sense that the exponent of the power-law degree distribution is tunable.
In mathematical analysis of network models, there is a tendency to consider only fully defined models. In contrast, we provide results about general properties for the whole P A-class in the next two subsections.

Power Law Degree Distribution
Despite the precise distribution of vertices to be joined to is not fixed in P A-class, we are still able to obtain the following results on the degree distribution.
First, we estimate N n (d), the number of vertices with given degree d in G n m . Denote by θ(X) an arbitrary function such that |θ(X)| < X. We prove the following result on the expectation EN n (d) of N n (d).
and Γ(x) is the gamma function. Secondly, we show that the number of vertices with given degree d is highly concentrated around its expectation.
These two results mean that the degree distribution follows (asymptotically) the power law with the parameter −1 − 1 A . Proving Theorem 2, we use the induction on d and n. We use Azuma-Hoeffding inequality to prove concentration. The complete proofs of these theorems are placed in Appendix due to space constraints.

Clustering Coefficient
Here we consider the clustering in P A-class. Results for some classical preferential attachment models (LCD and Móri) can be found in Section 2. In both models the clustering coefficient tends to zero as the graph grows.
Usually the asymptotic value of the clustering coefficient can be estimated by taking three times the quotient of the expected number of triangles and the expected number of P 2 's since one can prove that both random variables are highly concentrated around their expectations.
In particular, for the LCD-model, the expected number of triangles turns out to be of order (log n) 3 and the expected number of P 2 's is of order n log n. In Móri model for β > 0, these quantities are of order log n and n respectively. We see that for the two different models, the results are quite different. Here we generalize the mentioned results. First, we study the random variable P 2 (n) equal to the number of P 2 's in a random graph G n m from an arbitrary model that belongs to the PA-class. In the theorems below, we use the following notation. By whp ("with high probability") we mean that for some sequence A n of events, P (A n ) → 1 as n → ∞. We write a n ∼ b n , provided a n = (1 + o(1))b n , and we write a n ∝ b n , provided C 0 b n ≤ a n ≤ C 1 b n for some constants C 0 , C 1 > 0.
The ideas behind the proof of Theorem 4 are given in Appendix. Here it is worth noting that the value P 2 (n) in scale-free graphs is usually determined by the power-law exponent γ. Indeed, we have Therefore if γ > 3, then P 2 (n) is linear in n. But if γ ≤ 3, then P 2 (n) is superlinear.
Next, we study the random variable T (n) equal to the number of triangles in G n m . Note that in any model from the P A-class we have T (n) = O(n) since at each step we add at most m(m−1) 2 triangles. If we combine this fact with the previous observation, we see that if γ < 3, then in any preferential attachment model (in which the out-degree of each vertex equals m) the clustering coefficient tends to zero as n grows.
Our aim is to find models with constant clustering coefficient. Let us consider a subclass of P A-class with the following property: Here e ij is the number of edges between vertices i and j in G n m .
Theorem 5. Let G n m satisfy the condition (6). Then whp T (n) ∼ D n .
The proof of this theorem is straightforward. The expectation of the number of triangles we add at each step is D + o(1). Therefore ET (n) = Dn + o(n). Azuma-Hoeffding inequality can be used to prove concentration. As a consequence of Theorems 4 and 5, we get the following result on the clustering coefficient C(n) of the graph G n m .
Theorem 6. Let G n m belongs to P A-class and satisfy the condition (6). Then .
In the next section we propose a concrete flexible model from the P A-class and provide an efficient algorithm which generates graphs in this model.

Polynomial Model
In this section, we consider polynomial random graph models, which belong to the general P A-class defined above. In Subsection 4.1, we give the definitions. We propose an efficient algorithm, which generates polynomial graphs, in Subsection 4.2. In Subsection 4.3, we find the relations between the polynomial model parameters and the ones of P A-class. Applying our above theoretical results to polynomial models, we find them to be very flexible: one can tune the parameter of the degree distribution, the clustering coefficient and other characteristics.

Definition of Polynomial Model
Let us define the polynomial model. As in the random graph process from 3.1, we construct a graph G n m step by step. On the (n + 1)-th step the graph G n+1 m is made from the graph G n m by adding a new vertex n + 1 and edges e 1 , . . . , e m connecting this vertex to some m vertices i 1 , . . . , i m ∈ {1, . . . , n + 1}. Some of i 1 , . . . , i m can be equal, so multiple edges are permitted. Also if i j = n + 1 for some j, then we obtain a loop (multiple loops are also permitted).
We say that an edge ij is directed from i to j if i ≥ j, so the out-degree of each vertex equals m. We also say that j is a target end of ij. Denote by (d n i ) in the in-degree of a vertex i in G n m . Remind that by e ij we denote the number of edges between vertices i and j.
Fix some k, l such that 0 ≤ k ≤ m/2 and 2k ≤ l ≤ m. Put  This random graph process defines the polynomial model. This model belongs to P A-class. Indeed, one can formally show by simple calculations that the conditions (2-5) hold for this model. We consider the construction of the polynomial model in detail in the following two subsections.
Many models are special cases of the polynomial model. If we take the poly- , then we obtain a model, which is practically identical to the LCD-model. The Buckley-Osthus model can be also interpreted in terms of the polynomial model.

Generating Algorithm
Let us present an algorithm to efficiently generate graphs in the polynomial model. When we add the n + 1-th vertex we do the following: Step 1 With probability proportional to {α k,l } we choose some k = k 0 and l = l 0 .
Step 2 We choose k 0 edges from the existing graph G n m uniformly and independently and take all the ends of these edges as vertices {i 1 , . . . , i 2k0 }.
Step 3 We choose (l 0 −2k 0 ) edges from the existing graph G n m uniformly and independently and take target ends of these edges as vertices {i 2k0+1 , . . . , i l0 }. Note that Step 2 of our algorithm is mainly responsible to the formation of triangles in our random graph. In [16] Holme and Kim propose another procedure for producing triangles. Namely, they choose edges to form triangles with probabilities proportional to the degree of the edge head. One can show that this fact pushes the Holme-Kim model out of the P A-class.
Our algorithm allows us to generate graphs in the polynomial model with O(n) complexity. The estimation of the algorithm complexity is straightforward assuming we can choose an arbitrary edge or vertex with O(1) complexity. To this end, we support an array of edges and vertices at each step. Thus, in order to choose an arbitrary edge or vertex we first take a random index and then take an element from the corresponding array with this index.

Properties
It is easy to check that the parameters α k,l from (7) and A from (2) are related in the following way: This means that we can get any value of A in [0, 1] and any power-law exponent γ ∈ (2, ∞). We also obtain D = kα k,l . In the next section we analyze some properties of graphs in the polynomial model. We generate polynomial graphs and compare their properties with theoretical results we obtain.

Experiments
In this section, we choose a three-parameter model from the family of polynomial graph models defined in Section 4 and analyze the properties of the generated graphs depending on the parameters.

Description of Empirically Studied Polynomial Model
We studied empirically graphs in the polynomial model with m = 2p and the polynomial Here we need α, β, δ ≥ 0 and α + β + δ = 1, therefore, we have three independent model parameters: m, α, and β.

Empirical Results
Degree Distribution and Clustering Coefficient. We studied two polynomial graphs with n = 10 7 , m = 2, and A = 0.2, putting α = 0.2, β = 0 for the first graph and α = 0, β = 0.4 for the second one. The observed degree distributions are almost identical and follow the power law with the expected parameter γ = 3.5, see Fig. 1, a). For both cases, we also studied the behaviour of the clustering coefficient of generated graphs, 40 samples for each n = 10 1+0.06i , i = 0, . . . , 100see Fig. 1, b). In the first case we observe C(n) → 0 and in the second one C(n) → 2 15 , as was expected due to (9).
Assortativity. In this section, we consider so-called assortative mixing (or degree correlations) in the polynomial model (see, e.g., [4,2]). One of the possible definitions is the following. For an undirected graph G, consider the average degree of the nearest neighbors of vertices with a given degree d : where E(G) is the set of edges of graph G. If vertices of high degree tend to connect with vertices of high degree in a network, then d nn (d) is an increasing function (the case of assortative network). Vice-versa, if vertices of high degree tend to connect with vertices of low degree, then d nn (d) decreases (disassortative case).
Comparison with Other Models. The following table summarizes our results for the polynomial model in comparison with other mentioned preferential attachment models: γ Clustering coefficient Assortativity BA 3 tends to zero no assortativity BO/Móri (2, ∞) tends to zero assortative for β > 0 disassortative for β < 0

Conclusions
In this paper, we introduced the P A-class of random graph models, which generalizes previous preferential attachment approaches. We proved that any model from the P A-class possess the power-law degree distribution with tunable exponent. We also estimated its clustering coefficient. Next, we described one particular model from the proposed class (with tunable both the degree distribution parameter and the clustering coefficient) and provided a linear algorithm, which generates graphs in this model. Experiments with generated graphs verify our theoretical results. Moreover, the study of assortative mixing in generated graphs leads to future questions and hypotheses not yet justified by theory.
As the degree distribution of a preferential attachment model permits an adjustment to reality, the clustering coefficient still gives rise to a problem in some cases. For most real-world networks the parameter γ of their degree distribution belongs to [2,3]. As we showed in Section 3, once γ ≤ 3 in a preferential attachment model, the clustering coefficient decreases as the graph grows, which does not response to the majority of real-world networks.
Fortunately, there are many ways to overcome this obstacle. Cooper and Pra lat proposed a modification of the Barabási-Albert model, where a new vertex added at time t generates t c edges [11]. Preferential attachment models with random initial degrees were considered in [12]. Also there are models with adding edges between already existing nodes (e.g., [10]). Using one of these ideas for the P A-class is a topic for future research.

Appendix: Proofs
Proof of Theorem 2 We need the following notation: Note that the remainder term of p j n (d) can depend on i. We omit i in notation p j n (d) for simplicity of proofs.
We use this equality several times in this proof.
The proof is by induction on d and then on i. We use the following equalities Consider the case d = m. For constant number of small i we obviously have EN i (m) = i Am+B+1 + θ(C 1 ) with some C 1 . Assume that EN i (m) = i Am+B+1 + θ(C 1 ). From (14) we obtain It remains to show that We have p i (m) ≥ mA+B i − C0 i 2 . It gives us This equality holds for big i and C 1 . This completes the proof for d = m. Consider d > m and assume that we can prove the theorem for all smaller degrees. We use induction on i. We have We need to prove that there exists a constant C that This inequality holds for big C and d. For constant number of small d we need to show that there exists a function f (d) > 0 such that Obviously this function exists. This concludes the proof. Now consider t: i ≤ t ≤ n − 1. Note that We obtained the same equalities in the proof of Theorem 2. Replace G i m bŷ G i m orḠ i m in these equalities. Substracting the equalities withḠ i m from the equalities withĜ i m we get (for d > m) From this recurrent relation it is easy to obtain that δ n (d) ≤ M d for some M . This concludes the proof of Theorem 3.

Proof of Theorem 4
Let us give the sketch of the proof of Theorem 4. We can prove this theorem by induction. Note that Therefore So we obtain We computed the expectation of P 2 . One can prove concentration using standard martingale methods. This completes the proof of Theorem 4.