Taylor’s power law is a well-known empirical pattern in ecology. Its general form is V(μ)≈aμb, where μ is the mean and V(μ) is the variance of a non-negative random variable, a and b are constants. V(μ) is also called the variance function (see [15]). Taylor’s power law is called after the British ecologist L. R. Taylor (see [18]). Taylor’s power law is observed for population densities of hundreds of species in ecology. It is observed in medical sciences, demography ([6]), physics, finance (for an overview see [11]). Most papers on the topic present empirical studies, but some of them offer models as well (e.g. [6] for mortality data, [7] for population dynamics, [11] for complex systems). We mention that in the theory of complex systems Taylor’s power law is called ‘fluctuation scaling’, V(μ) is called the fluctuation and μ is the average. There are papers studying Taylor’s power law on networks (see, e.g. [9]). In those papers Taylor’s law concerns some random variable produced by a certain process on the network.

However, there is another power law for networks. There are large networks satisfying pk∼Ck−γ as k→∞ , where pk is the probability that a node has degree k. This relation is often referred to as a power-law degree distribution or a scale-free network. Here and in what follows ak∼bk means that limk→∞ak/bk=1 . In their seminal paper [3] Barabási and Albert list several scale-free large networks (actor collaboration, WWW, power grid, etc.), they introduce the preferential attachment model and give an argument and numerical evidence that the preferential attachment rule leads to a scale-free network. A short description of the preferential attachment network evolution model is the following. At every time step t=2,3,… a new vertex with N edges is added to the existing graph so that the N edges link the new vertex to N old vertices. The probability πi that the new vertex will be connected to the old vertex i depends on the degree di of vertex i, so that πi=di/∑jdj , where ∑jdj is the cumulated sum of degrees. A rigorous definition of the preferential attachment model was given in [4], where a mathematical proof of the power law degree distribution was also presented. The idea of preferential attachment and the scale-free property incited enormous research activity. The mathematical theory is described in the monograph [19] written by van der Hofstad (see also [10] and [5]). The general aspects of network theory are included in the comprehensive book [2] by A. L. Barabási.

There are lot of modifications of the preferential attachment model, here we can list only a few of them. The following general graph evolution model was introduced by Cooper and Frieze in [8]. At each time step either a new vertex or an old one generates new edges. In both cases the terminal vertices can be chosen either uniformly or according to the preferential attachment rule. In [1, 13] and [12] the ideas of Cooper and Frieze [8] were applied, but instead of the original preferential attachment rule, the terminal vertices were chosen according to the weights of certain cliques.

In several cases the connection of two edges in a network can be interpreted as co-operation (collaboration). For example in the movie actor network two actors are connected by an edge if they have appeared in a film together. In the collaboration graph of scientists an edge connects two people if they have been co-authors of a paper (see, e.g. [10]). In social networks, besides connections of two members, other structures are also important. In [17] or [1] cliques are considered to describe co-operations. In a clique any two vertices are connected, that is, any two members of the clique co-operate. However, in real-life examples, in a co-operation the members can play different roles. In a team usually one person plays central role and the other ones play peripheral roles. Trying to handle this situation and to find a mathematically tractable model leads to the study of star-like structures, see [14].

In [14] the concept of [13] was applied but instead of cliques, star-like structures were considered. A team has star structure if there is a head of the team and all other members are connected to him/her. We call a graph N-star graph if it has N vertices, one of them is called the central vertex, the remaining N−1 vertices are called peripheral vertices, and it has N−1 edges. The edges are directed, they start from the N−1 peripheral vertices and their end point is the central vertex. In [14] the following N-stars network evolution model was presented. In this model at each step either a new N-star is constructed or an old one is selected (activated) again. When N vertices form an N star, then we say that they are in interaction (in other words they co-operate). During the evolution, a vertex can be in interaction several times. We define for any vertex its central weight and its peripheral weight. The central weight of a vertex is w1 , if the vertex is a central vertex in interactions w1 times. The peripheral weight of a vertex is w2 , if the vertex is a peripheral vertex in interactions w2 times. In [14] asymptotic power law distribution was proved both for w1 and w2 .

We are interested in the following general question. Is the original Taylor’s power law true for random networks? First we considered data sets of real life networks. We analysed them and the statistical analysis showed that there are cases when Taylor’s law is true and there are cases when it is not true (our empirical results will be published elsewhere). So we encountered the following more specific problem: Find network structures where Taylor’s power law is true. To this end we analysed the above N-stars network evolution model.

In this paper we prove an asymptotic Taylor’s power law for the N-stars network evolution model. We shall calculate the mean and the variance of w2 when w1 is fixed, and we shall see that the variance function is asymptotically quadratic. In Section 2, the precise mathematical description of the model and the results are given. We recall from [14] the asymptotic joint distribution of w1 and w2 (Proposition 2.1). Then we calculate the marginal distribution (Proposition 2.2), the expectation (Proposition 2.3), and the second moment (Proposition 2.4). The main result is Theorem 2.1. The proofs are presented in Section 3. Besides mathematical proofs, we give also a numerical evidence. In Section 4 simulation results are presented supporting our theoretical results.

First we give a short mathematical description of our random graph model from [14].

Let N≥3 be a fixed number. We start at time 0 with an N-star graph. Throughout the paper we call a graph N-star graph if it has N vertices, one of them is the central vertex, the remaining N−1 vertices are peripheral ones, and the graph has N−1 directed edges. The edges start from the N−1 peripheral vertices and their end point is the central vertex. So the central vertex has in-degree N−1 , and each of the N−1 peripheral vertices has out-degree 1. The evolution of our graph is governed by the weights of the N-stars and the (N−1) -stars. In our model, the initial weight of the N-star is 1, and the initial weights of its (N−1) -star sub-graphs are also 1. (An (N−1) -star sub-graph is obtained if a peripheral vertex is deleted from the N-star graph. The number of these (N−1) -star sub-graphs is N−1 .)

We first explain the model on a high level, before giving a formal definition in the next paragraphs. The general rules of the evolution of our graph are the following. At each time step, N vertices interact, that is, they form an N-star. It means that we draw all edges from the peripheral vertices to the central vertex so that the vertices will form an N-star graph. During the evolution we allow parallel edges. When N vertices interact, not only new edges are drawn, but the weights of the stars are also increased. At the first interaction of N vertices the newly created N-star gets weight 1, and its new (N−1) -star sub-graphs also get weight 1. If an (N−1) -star sub-graph is not newly created, then its weight is increased by 1. When an existing N-star is selected (activated) again, then its weight and the weights of its (N−1) -star sub-graphs are increased by 1. So the weight of an N-star is the number of its activations. We can see that the weight of an (N−1) -star is equal to the sum of the weights of the N-stars containing it. The weights will play crucial role in our model. The higher the weight of a star the higher the chance that it will be selected (activated) again.

Now we describe the details of the evolution steps of our graph. We have two options in every step of the evolution. Option I has probability p. In this case we add a new vertex, and it interacts with N−1 old vertices. Option II has probability 1−p . In this case we do not add any new vertex, but N old vertices interact. Here 0<p≤1 is fixed.

Option I. In this case, that is, when a new vertex is born, we have again two possibilities: I/1 and I/2.

I/1. The first possibility, which has probability r, is the following. (Here 0≤r≤1 is fixed.) We choose one of the existing (N−1) -star sub-graphs according to the preferential attachment rule, and its N−1 vertices and the new vertex will interact. Here the preferential attachment rule means that an (N−1) -star of weight vt is chosen with probability vt/∑hvh , where ∑hvh is the cumulated weight of the (N−1) -stars. The interaction of the new vertex and the old (N−1) -star means that they establish a new N-star. In this newly created N-star the center will be the vertex which was the center in the old (N−1) -star, the former N−2 peripheral vertices remain peripheral and the newly born vertex will be also peripheral. A new edge is drawn from each peripheral vertex to the central one, and then the weights are increased by 1. More precisely, the just created N-star gets weight 1, among its (N−1) -star sub-graphs there are (N−2) new ones, so each of them gets weight 1, finally the weight of the only old (N−1) -star sub-graph is increased by 1.

I/2. The second possibility has probability 1−r . In this case we choose N−1 old vertices uniformly at random, and they will form an N-star graph with the new vertex, so that the new vertex will be the center. The edges are drawn from the peripheral vertices to the center. As here the newly created N-star graph and all of its (N−1) -star sub-graphs are new, so all of them get weight 1.

Option II. In this case, that is, when we do not add any new vertex, we have two ways again: II/1 and II/2.

II/1. The first way has probability q. (Here 0≤q≤1 is fixed.) We choose one of the existing N-star sub-graphs by the preferential attachment rule, then draw a new edge from each of its peripheral vertices to its center vertex. Then the weight of the N-star and the weights of its (N−1) -star sub-graphs are increased by 1. Here the preferential attachment rule means that an N-star of weight vt is chosen with probability vt/∑hvh , where ∑hvh is the cumulated weight of the N-stars.

II/2. The second way has probability 1−q . In this case we choose N old vertices uniformly at random, and they establish an N-star graph. Its center is chosen again uniformly at random out of the N vertices. Then, as before, new edges are drawn from the peripheral vertices to the central one, and the weights of the N-star and its (N−1) -star sub-graphs are increased by 1.

Throughout the paper 0<p≤1 , 0≤r≤1 , 0≤q≤1 are fixed numbers. In our formulae the following parameters are used. (2.1) α11=pr,α12=(1−p)q,α1=α11+α12,α2=prN−2N−1+(1−p)q,β1=(1−p)(1−q)p,β2=(N−1)[(1−r)+(1−p)(1−q)p],α=α1+α2,β=β1+β2.

In [14] it was shown that the above evolution leads to a scale-free graph. To describe the result, let Vn denote the number of all vertices and let X(n,w1,w2) denote the number of vertices with central weight w1 and peripheral weight w2 after the nth step.

Now we turn to the new results of this paper. First we consider the marginals of the asymptotic joint distribution xw1,w2 . Let (2.7) xw1,·= ∑l=0∞xw1,l be the first marginal distribution.

Now we turn to the conditional expectations of the asymptotic distribution. Let (2.12) Ew1= ∑l=0∞xw1,ll/xw1,· be the expectation when the central weight w1 is fixed.

Now we turn to the conditional second moments of the asymptotic distribution. Let (2.16) Mw1= ∑l=0∞xw1,ll2/xw1,· be the second moment when the central weight w1 is fixed.

Now Propositions 2.3, 2.4 imply the main result of this paper, that is, we obtain that Taylor’s law is satisfied asymptotically. Theorem 2.1.

Let 0<p<1 , 0<q<1 , 0<r<1 . Assume that β1+1>2α2 2{\alpha _{2}}$]]>. Then (2.19) Mw1∼CEw12 as w1→∞ , where C is an appropriate constant. So Taylor’s law is satisfied asymptotically with exponent 2.

For the joint limiting distribution we have the following result.

Throughout the proof we shall use the following facts on the Γ-function. (3.2) ∑i=0nΓ(i+a)Γ(i+b)=1a−b+1[Γ(n+a+1)Γ(n+b)−Γ(a)Γ(b−1)], see [16]. Stirling’s formula implies that (3.3) Γ(n+a)Γ(n+b)∼n−(b−a). The above two formulae imply that (3.4) ∑i=0∞Γ(i+a)Γ(i+b)=1b−a−1Γ(a)Γ(b−1) if b>a+1 a+1$]]>. The following facts on xw1,w2 will be useful.

Now we turn to the proofs of the new results. First we deal with the marginal distribution.