{'fraction_non_alphanumeric': 0.05617810760667904, 'fraction_numerical': 0.012801484230055659, 'mean_word_length': 3.825604297224709, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Evolution of a modified binomial random graph by agglomeration

In the classical Erd\"os-R\'enyi random graph G(n,p) there are n vertices and each of the possible edges is independently present with probability p. The random graph G(n,p) is homogeneous in the sense that all vertices have the same characteristics. On the other hand, numerous real-world networks are inhomogeneous in this respect. Such an inhomogeneity of vertices may influence the connection probability between pairs of vertices. The purpose of this paper is to propose a new inhomogeneous random graph model which is obtained in a constructive way from the Erd\"os-R\'enyi random graph G(n,p). Given a configuration of n vertices arranged in N subsets of vertices (we call each subset a super-vertex), we define a random graph with N super-vertices by letting two super-vertices be connected if and only if there is at least one edge between them in G(n,p). Our main result concerns the threshold for connectedness. We also analyze the phase transition for the emergence of the giant component and the degree distribution. Even though our model begins with G(n,p), it assumes the existence of some community structure encoded in the configuration. Furthermore, under certain conditions it exhibits a power law degree distribution. Both properties are important for real applications.


Introduction
The subject of random graphs began in 1959-1960 with the papers "On random graphs I" and "On the evolution of random graphs" by Erdős and Rényi [17,18], and since then many properties about this model have been analyzed in order to answer questions of physical and mathematical interest. In the last decades a big interest in random graphs and random graphs processes has arisen because this kind of models can be used to analyze real situations, since the evolution of random graphs may be considered as a model of the evolution of real nets, e.g. the electric network system of a city or the development of social relations.
The original model studied by Erdős and Rényi begins with no edges at time 0 and adds new edges, one at a time, uniformly at random among all edges not already present. The M-th stage of this process can be identified with the uniform random graph model G(n, M ), in which a graph is chosen with uniform probability over all graphs with n vertices and exactly M edges. It was observed that the uniform model G(n, M ) can be also studied by another random graph model closely related, where a set of n vertices is given, and each possible edge is present independently with probability p. This model is called the binomial model G(n, p) and was introduced by Gilbert [20] at about the same time. It is well known that the models G(n, p) and G(n, M ) are essentially equivalent for the correct choice of M and p.
One of the most famous results of Erdős and Rényi [18] is the threshold for connectedness, a phenomenon which is tightly related to the nonexistence of isolated vertices. Clearly, when there exists at least one isolated vertex the graph is disconnected, but the opposite implication is not in general true. Remarkably, it was showed that when there are no isolated vertices, the random graph is with high probability (meaning with probability tending to one as n → ∞ and denoted by whp) connected (see [18,8]).
Many other properties were also studied in [18], perhaps the most striking result found was the discovery of a drastic change in the size of the largest component at time n/2 and, as a consequence, the emergence of a giant component. More precisely, Erdős  . This rapid transformation of the graph is called the 'phase transition' of the random graph and is related to the phase transitions in percolation, a model well studied in mathematical physics and which is also one of the main branches of contemporary probability, see [9,21].
During the last few decades, it was empirically observed that real world graphs fall into the class of small-world networks. Such networks are characterized to be highly but locally correlated among its vertices, thus forming communities or cliques, and having short paths that globally link all vertices of the network. This means that all vertices are linked through relatively few number of steps, but most vertices maintain only a few direct connections, mostly within a clique of neighbors. In other words, if a network is represented by a number of vertices connected by edges, then each community or click contains several densely interconnected vertices, and there are relatively few connections between vertices in different cliques. This evidence inspired the small world random graph introduced by Strogatz and Watts [31] in which each vertex is connected with k nearest neighbors vertices and also with long-range vertices obtained at random. At about the same time, it was observed that the number of connections in many real networks has a power law distribution. This property was the starting point of the preferential attachment model introduced by Barabasi and Albert [1]. These and related models are interesting since they are found in many real networks including the Internet [19], networks of brain neurons [11,12] and a variety of many others networks arising in the fields of economy, physics and social sciences.
It was also observed that many real-world networks are inhomogeneous, in the sense that vertices can be of different types and they are connected according to it. A general model of an inhomogeneous random graph is proposed by Bollobás, Janson and Riordan [7], which consider a conditional independence between the edges, where the number of edges is linear in the number of vertices. This model includes as special cases many models previously studied in the literature, see for instance Durret [6] and Bollobás, Janson and Riordan [16]. In the inhomogeneous random graph model introduced in [7], it is shown that under a weak (convergence) assumption on the expected number of edges, many interesting properties can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. Additionally other properties are also studied, including the degree distribution, the numbers of paths and cycles, and the typical distance between pairs of vertices in the giant component. More recently, van der Hofstad [22] analyzes the critical behavior of the largest component in inhomogeneous random graphs in the so called rank-1 case, where the vertices receive vertex weights, and edges are present between vertices with a probability that is approximately proportional to the product of the weights of the vertices in the edge. Such work mainly considers the Poisson random graph or Norros-Reittu random graph [28], where the degree of vertex i is close in distribution to a Poisson random variable with parameter w i , where w i denotes the weight of i. In [22] is showed that the critical behavior depends sensitively on the asymptotic properties of their degree sequence, i.e., the asymptotic proportion of vertices with degree k for each k ≥ 1, furthermore the author extended these results to the model studied by Chung and Lu [13,14] and the one studied by Britton, Deijfen and Martin-Löf [10].
This explosion of research in random graphs has been originated with the aim to find models which describe the complexity of real world networks. The purpose of this paper is to contribute to this task by proposing a new inhomogeneous random graph model which is obtained in a constructive way from the classical Erdős-Rényi model. By a constructive way, we mean an explicit scheme for constructing the graph from a given configuration of G(n, p). We consider a configuration of subsets of vertices that represents the agglomeration of nodes, and we will call it a configuration of super-vertices. Then, from it an inhomogeneous random graph model is defined by letting two super-vertices be connected if there is at least one edge between them in G(n, p). Note that we are not assuming that the vertices in the super-vertices should be all connected, so they are not necessarily clusters in G(n, p).
As we have already pointed out, the study of inhomogeneous random graphs and its mathematical properties is an issue of current research and there are many recent work dealing with this kind of models. We believe that constructive models like the one proposed here are an useful contribution to addressing the modeling of real networks. Our model assumes the existence of community structure and under certain conditions it exhibits a power law degree distribution, which are both well important properties for real applications. Related constructive random graph models are analyzed for instance by Janson and Spencer [24] and by Seshadhri, Kolda and Pinar [29].
For our model we determine the precise critical point for connectedness. In order to obtain our main result, we apply Stein's method, instead of the method of moments used in the original proof by Erdős and Rényi [18], and show that the number of isolated super-vertices converges in law to the Poisson distribution, similar to the alternative proof by Janson, Luczak and Ruciński [23]. In addition, we analyze the degree distribution and the phase transition of the emergency of the giant component.

The model and main results
The motivation of our model comes from the construction of a random graph inspired in real networks with a community structure. In order to model such a situation we consider a random graph with a given number of "super-vertices" (the agglomerates) of given sizes where we assume that the underlying graph structure follows a G(n, p) law. By a "super-vertex" of size i we mean a subset of i vertices from G(n, p), not necessarily connected.
Let N ∈ N + , r ∈ N + ∪ {∞}, K = {k i : k i ∈ N, 1 ≤ i ≤ r} and p ∈ (0, 1) be given. We define G(N, K, p) to be a random graph on N super-vertices with configuration K, where k i denotes the number of super-vertices of size i, for i = 1, 2, . . . , r, in which an edge between a pair of super-vertices of sizes i and j is present with probability independently of each other, and we assume there are no loops. In what follows we may write r = ∞ if it is possible to have a super-vertex of any size. In words, (1) is the probability that a pair of super-vertices of sizes i and j is connected if there is at least one edge between the corresponding subsets of vertices in G(n, p), see  Our goal is to study properties of this random graph by considering different values of p as a function of either n or N . It seems difficult to obtain substantial asymptotic results for G(N, K, p) without further restrictions. In this work we therefore assume that, for i = 1, 2, . . . , r, the following limit exist We note that, when r ∈ N + , this implies that the limit of n/N exists and is given by which means, for N big enough, there are many (of order N ) super-vertices of size i, for some 1 ≤ i ≤ r. We let i * = min{i : µ i > 0}.
In this paper we show that the threshold for connectedness for G(N, K, p) is where c(N ) could be either a function of N or a constant. We also study the phase transition of the emergency of the giant component and the degree distribution of a random super-vertex. It is possible to note that our model belongs to the class of inhomogeneous random graphs studied by Bollobás, Janson and Riordan [7] and, under technical assumptions, we will see that the results about degree distribution and phase transition for the giant component can be obtained from Theorem 3.13 and Theorem 3.1 in [7], when the limit of n/N exists. The threshold for connectedness is not studied in [7] and it is the main result of the current work. All our results are asymptotic, and the limits are taken as N → ∞. We will use the following standard notation: for (deterministic) functions f = f (N ) and We say that an event holds with high probability whp, if it holds with probability tending to 1 as N → ∞. Formally, it is a sequence E N of events that hold whp, but the N is often suppressed in the notation. We will also use the standard notation µ-a.e. on some metric space (S, µ), to say that the set of elements for which a property does not hold is a set of µ-measure zero. We shall suppress the measure µ in our notation, so we will just write a.e.
Our main result gives a precise location for the threshold for connectedness.
Theorem 1. Consider the random graph G(N, K, p) with r ∈ N + and let where i * = min{i : µ i > 0}. Additionally, assume that the following limits exist (2) If c * = c ∈ R is a constant and β < ∞, then (3) If c * = +∞, then Remark 1. To analyze connectivity for G(N, K, p), it is also necessary to know something about the behavior of the limit of k i /N , for i < i * . Note that in this case µ i = 0. Essentially, our conditions on β give us this information which is related to the velocity at which k i /N goes to 0 for i < i * . As an illustration, consider the following two cases for r = 2. In the first, take For the second assume that k 1 = CN 1/2 , where C is a given constant, then we have that µ 1 = 0, µ 2 = 1 and i * = 2. However, now lim N →∞ (k 1 /N 1/2 ) = C and thus β < ∞. The previous theorem says that these configurations give a different result of connectivity provided c * is a constant. In the first case the random graph is whp disconnected, while in the last one is connected with positive probability.
Remark 2. In order to compare Theorem 1 with the threshold for connectedness in G(n, p), let p = 1 n (ln n + c(n)). If lim n→∞ c(n) = −∞, then whp G(n, p) is disconnected, but if lim n→∞ c(n) = +∞, then whp G(n, p) is connected. Furthermore, if lim n→∞ c(n) = c is a constant, the probability of G(n, p) being connected is in the limit equal to e −e −c . Thus, Theorem 1 (2) says that if c * is a fixed constant, the probability of G(N, K, p) being connected is the same as that of G(n, p) being connected provided lim N →∞ (n/N ) = 1. We observe that last condition means that µ 1 = 1 and µ i = 0 for i > 1, which implies i * = 1 and therefore β = 0. Then we have a similar result than the well known result for G(n, p). The conclusion is natural because in this case both models have the same asymptotic number of simple vertices.
Remark 3. The property of connectedness for inhomogeneous random graphs was recently studied by Devroye and Fraiman in [15], where the authors consider an inhomogeneous random graph on a set of n vertices described in a similar way as the general model of [7]. In such model, each pair of vertices, say k and l, are connected independently with a probability that dependents on x k , x l and p, where x k , x l are associated values to the vertices k and l, respectively, and p = ln n/n. In that paper a connectivity threshold is obtained in terms of some isolation parameter λ * , thus whp when λ * > 1 the graph is connected, while if λ * < 1 the graph is disconnected. Even though our model G(N, K, p) is close to a discrete version of the model studied in [15] by taking p = ln N/N , the critical point λ * does not tell us when our model is not connected. For example, if µ 1 > 0 the isolation parameter should be u := lim N →∞ n N and if µ 1 = 0 but µ 2 > 0, then the isolation parameter should be 2u. However u ≥ 1 because n ≥ N , so the isolation parameter does not tell us when G(N, K, p) is disconnected. Therefore, we need to re-parametrize p differently in order to get the threshold for connectedness for G(N, K, p).
Another properties we study are the phase transition for the emergence of the giant component and the degree distribution of a random super-vertex. We denote the sizes of components of a graph G by L 1 (G) ≥ L 2 (G) ≥ . . . , with L j (G) = 0 if G has fewer than j components. (2) We have that, is the solution of the nonlinear equation Furthermore, ρ > 0 iff cs 2 > 1.

Remark 4.
Observe that s 2 is the average size of a super-vertex containing a random vertex, and the limits 2 is equal to r j=1 j 2 µj u . If the super-vertices would be connected components of G(n, p), s 2 would be the susceptibility parameter defined for example in [24].
in probability, where and P o(ci) denotes a random variable with Poisson distribution with mean ci.
Example 1. It is well known that in many real networks the vertex connectivities follow a power-law distribution. This means that the degree of a given vertex is a random variable X such that P (X = k) ∼ C k −α where α and C are constants. See for instance [27] for a review of the empirical evidence of this property. If we take our model G(N, K, p) with p = 1/n and an initial configuration of super-vertices K such that it follows as a corollary of the previous theorem that where Z ≥k denotes the number of super-vertices of degree at least k, the first convergence is in probability when N goes to ∞ and k fixed, and the last approximation is true for values of k big enough. See [7] (Corollary 13.1) for more details. In particular, as mentioned in that work, if D is the degree of a random super-vertex, then lim N →∞ P (D ≥ k) ∼ C k −α as k → ∞. As a consequence we have a random graph model obtained in a constructive way and such that it presents community structure and power law degree distribution.
2.1. Related model. In our model we assume the limit of n/N exists when N goes to ∞. This is a natural condition in the light of a general inhomogeneous random graph introduced by Bollobás, Janson and Riordan [7]. In order to describe such model, we briefly recall some definitions from [7]. (1) A vertex space V is a triple (S, µ, (x N ) N ≥1 ) where S is a separable metric space, µ is a Borel probability measure on S and, for each N ≥ 1, x N is a random sequence (x 1 , x 2 , . . . , x N ) of points of S, such that in probability, for every µ-continuity set A ⊂ S. (2) A kernel κ N on a vertex space V is a symmetric non-negative Borel measurable function on S × S.
Let G V (N, κ N ) be the inhomogeneous random graph with N vertices such that two vertices are connected by and edge, say the vertices k and l, with probability This model is an extension of one defined by Söderberg [30] and various properties are studied under specific restrictions. The main results about the existence and uniqueness of the size of the giant component are proved by using an appropriated multi-type branching process and an integral operator to which is related the component structure.
We can obtain our random graph model of N super-vertices as a particular case of the previous one. To see that, we consider the set S = Z + , the probability measure on S defined by µ({i}) = µ i given by (2), and the sequence x N = (x 1 , x 2 , . . . , x N ) of points of S, such that x k represents the size of the k-th super-vertex. Then the triple V := (S, µ, (x N ) N ≥1 ) is a vertex space in the sense of Definition 1. Observe that, for all i = 1, 2, . . . , r, where I A denotes the indicator random variable of the event A. Then by our construction the x k 's are deterministic and therefore condition (5) is satisfied by (2). In our case, when p = c/n, the connection probabilities between two supervertices can be written as is a kernel on the vertex space V. Hence, our model G(N, K, p) is the random graph model corresponding to G V (N, κ N ), and the phase transition and degree distribution results (Theorem 2 and Theorem 3) follow from [7]. The threshold for connectedness is not study in [7] and is the main result of Theorem 1 in the current work.

3.1.
Proof of Theorem 1. We prove the first part of the theorem by showing that with high probability isolated super-vertices exist, using the second moment method. The second part of the theorem is proved by showing that in the limit, G(N, K, p) consists of a giant component and isolated super-vertices. Moreover, the number of isolated super-vertices follows asymptotically a Poisson law. Here we use Stein's method. Finally, the last part follows from the first moment method and by showing that in the limit, G(N, K, p) does not contain components of order m, for 2 ≤ m ≤ N/2. In the rest of this subsection we consider the random graph G(N, K, p) with r ∈ N + and where i * := min{i : µ i > 0}. Additionally, we denote the number of isolated super-vertices in G(N, K, p) by X and we define the values  (1). Observe that if the graph has isolated super-vertices, then it is not connected. Therefore, we shall show that whp isolated super-vertices exist on the graph.
and hence On the other hand, we get For i = j, we obtain In fact, we will see that E[X] → ∞ and E[X 2 ]/E 2 [X] → 1 as N → ∞. We will start analyzing E[X]. Note that 1 − x = e −x+O(x 2 /2) if |x| < 1. For any constants a, b > 0 we can write Thus by (9) and (12) with a = b = 1, we have If c * = −∞, c(N ) > − ln N , and since i * = min{i : µ i > 0}, we get from (13) In the case that c * = c ∈ R is a constant and β = ∞, we have that there exists an i < i * such that lim N →∞ k i /(N i/i * ) = ∞, we also get that (13) goes to infinity as N goes to infinity. Thus, we have that under the condition of this lemma, E(X) → ∞ as N → ∞. Now observe that by (10), (11) and (12) that and by (9) and (12) we obtain Thus, E(X 2 )/E 2 (X) → 1 and  Proof. Since c * = +∞, by (9) and (12) we have Thus, by Markov's inequality we get lim N →∞ P(X = 0) = 1.
To prove that whp G (N, K, p) is connected, we still need to see that whp there are no components of order m, for 2 ≤ m ≤ N/2. Let S m be the set of all subsets of m super-vertices. For each S ∈ S m , let m i (S) be the number of super-vertices of size i in S, and note that m = m 1 (S) + · · · + m r (S). Observe that if the super-vertices in S form a component in G (N, K, p), the following two events should hold: (1) A S 1 := {the super-vertices in S are connected}, and (2) A S 2 := {there is no super-vertex in S connected with a super-vertex in S c }, where S c denotes the complement of S. Thus, Since a component of size m contains a tree of order m and p ij ≤ ijp ≤ r 2 p, then Now, let A m * = {S ∈ S m : S contain at least one s.v. of size smaller than i * }. Hence, by (15), (16) and (17), we have that P(∃ a component of size m) is smaller than the sum of the following two terms We will work the case m = 2 separately. When m = 2 we have that M 2 ≤ 2r, then from (18) and (19), Now we analyze both terms of the right side of last inequality. Note that, where the last inequality follows by observing that M * (S 2 − A 2 * ) ≥ 2i * since we are considering sets S formed only by super-vertices of sizes bigger than i * . On the other hand, since we obtain Therefore, from (20), (21) and (22) we conclude that In general, for m > 2 we have, as above, from (18) and (19) that (1) Now we will analyze the cases Therefore, by (20) and (24) we obtain 3.1.3. Proof of Theorem 1 (2). We will start by proving that if c * = c ∈ R is a fixed constant, and under some extra conditions, the number of isolated supervertices asymptotically follows a Poisson distribution. To this end we will use Stein's method, in particular Theorem 6.24 [23]. Write Theorem 6.24 [23] says that if the random variables {I k } k are positively related, then where λ = E(X), and d T V (, ) is the total variation distance.
Lemma 3. Consider the random graph G(N, K, p) with p defined by (7). Assume that c * = c ∈ R is a fixed constant and β < ∞. Then, X has asymptotically Poisson distribution with mean β + µ i * e −c .
Proof. Without loss of generality we assume that c(N ) ≡ c ∈ R is a constant. Let G k (N, K, p) be the random graph G(N, K, p) with all edges from the k-th supervertex removed, and let J lk = 1 if the l-th super-vertex is isolated in G k (N, K, p), and J lk = 0 otherwise. Observe that . Moreover, we can check that J lk ≥ I l for every l = k, thus the random variables {I k } k are positively related and we can apply Theorem 6.24 [23]. To do that we need to calculate the magnitude of V(X) and E(X).

Furthermore,
Thus, we can conclude that X has asymptotically Poisson distribution with mean β + µ i * e −c , where Observe that since n = r j=1 jk j and N = r j=1 k j , then Thus under the condition that lim N →∞ n/N = 1, we have that lim N →∞ k j /N = 0, for all j ≥ 2, since r is fixed. Due to our assumption (2), µ 1 = 1 and therefore β = 0. Then if c is a fixed constant what we have from previous Lemma is that X has asymptotically Poisson distribution with mean e −c .
Lemma 4. Consider the random graph G(N, K, p) with p defined by (7). Assume that c * = c ∈ R is a fixed constant and β < ∞. Then, In particular, if lim N →∞ n/N = 1 then, Proof. By (25)  3.2. Proof of Theorem 2 and Theorem 3. Consider the random graph G(N, K, p) with r ∈ N + ∪ {∞} and p = c/n, where c is a given constant. Assume also that the limit u = lim N →∞ (n/N ) exists. As discussed in Subsection 2.1, our model G(N, K, p) belongs to the class of inhomogeneous random graphs studied by Bollobás, Janson and Riordan in [7], where the emergence of the giant component and the degree distribution were analyzed under some extra conditions on the sequence of kernels {κ N } N ≥1 . Let us begin by some definitions of [7].
Note that weather κ is graphical depends on the sequences x N . Next lemma says that the only condition in our model for κ being graphical is that the limit u exists.
Lemma 5. Consider the random graph G(N, K, p) with p = c/n, where c is a given constant. If the limit u exists, then the sequence of kernels (κ N ) given by (6) is graphical on V with limit κ(i, j) = (c/u)ij.
Proof. It is not difficult to see that κ is in fact a kernel on V, and that conditions (2) and (3) are satisfied. To check condition (1) in previous definition, we fix a point (i, j) of Z + × Z + and we consider two sequences (i N ) N ≥1 and (j N ) N ≥1 such that i N → i and j N → j. Since and u = lim N →∞ (n/N ) exists we conclude To show that condition (4) is satisfied, note first that in our case (1/2) S 2 κ(x, y)dµ(x)dµ(y)  In order to obtain results about the size of the giant component, one additional definition is required.
For technical reason, we consider a slight weakening of irreducibility.
Definition 4 (Definition 2.11 [7]). A kernel κ on (S, µ) is quasi-irreducible if there is a µ-continuity set S ′ ⊆ S with µ(S ′ ) > 0 such that the restriction of κ to S ′ × S ′ is irreducible, and κ(x, y) = 0 if x / ∈ S ′ or y / ∈ S ′ . Now, our Theorems 2 and 3 can be obtained as a consequence of Theorem 3.1 and Theorem 3.13 in ( [7]) which we include here for the sake of completeness.  Proposition 2. (Theorem 3.13 [7]) Let (κ N ) be a graphical sequence of kernels on a vertex space V with limit κ, and let G N = G V (N, κ N ). Write Z k for the number of vertices of G N with degree k. Then, for any fixed k ≥ 0, in probability, where Ξ has the mixed Poisson distribution S P o(λ(x))dµ(x), and λ(x) := S κ(x, y)dµ(y).
3.2.2. Proof of Theorem 3. Theorem 3 follows by consequence of Proposition 2 and Lemma 5.