Cite this Article
Zhang Xiao-Jun, Yang Hui-Lan. Degree distribution of random birth-and-death network with network size decline. Chinese Physics B, 2016, 25(6): 060202  
Permissions
Degree distribution of random birth-and-death network with network size decline
Zhang Xiao-Jun†, , Yang Hui-Lan
School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, China

 

† Corresponding author. E-mail: sczhxj@uestc.edu.cn

Project supported by the National Natural Science Foundation of China (Grant No. 61273015) and the Chinese Scholarship Council.

Abstract
Abstract

In this paper, we provide a general method to obtain the exact solutions of the degree distributions for random birth-and-death network (RBDN) with network size decline. First, by stochastic process rules, the steady state transformation equations and steady state degree distribution equations are given in the case of m ≥ 3 and 0 < p < 1/2, then the average degree of network with n nodes is introduced to calculate the degree distributions. Specifically, taking m = 3 for example, we explain the detailed solving process, in which computer simulation is used to verify our degree distribution solutions. In addition, the tail characteristics of the degree distribution are discussed. Our findings suggest that the degree distributions will exhibit Poisson tail property for the declining RBDN.

PACS: 02.50.Ga;02.60.Cb;64.60.aq
Keyword:random birth-and-death network (RBDN);Markov chain;generating function;degree distribution
1. Introduction

In the real world, there exist many birth-and-death networks such as the World Wide Web,[1–3] the communication networks,[4–6] the friend relationship networks,[7–10] and the food chain networks,[11–13] in which nodes may enter or exit at any time. For these kinds of evolving networks, the degree distribution is always one of the most important statistical properties.[14–31] Several methods have been proposed to calculate their degree distributions like the first-order partial-differential equation method,[14] the mean-field approach,[15,16] the rate equation approach,[17–20,30] and the master-equation approach.[31] While these approaches aim at the networks whose sizes keep growing or remain unchanged at each time step, Zhang et al. put forward the stochastic-process-rules (SPR)-based Markov chain method to solve the degree distributions of evolving networks in which the network size may increase or decrease at each time step.[21]

Furthermore, a random birth-and-death network model (RBDN) is considered,[27] in which at each time step, a new node is added into the network with probability p (0 < p < 1) and connected with m old nodes uniformly, or an existing node is deleted from the network with the probability q = 1 − p. For 0 < p < 1/2, since m is a critical parameter for the degree distributions, solution methods may vary for different values of m. Zhang et al. only considered special cases, i.e., m = 1 and 2.[27] In this paper, a general approach is proposed for solving the degree distributions of RBDN with network size decline in the case of m ≥ 3. Taking m = 3 for example, we provide the exact solutions of the degree distributions for RBDN. Our findings indicate that the tail of the degree distribution for the declining RBDN is subject to Poisson tail.

The rest of this paper is structured as follows: Section 2 gives the RBDN model with 0 < p < 1/2 and its steady-state equations; Section 3 provides the method of solving degree distribution of RBDN with 0 < p < 1/2; Section 4 further discusses the tail characteristics of the degree distribution; Section 5 concludes the paper.

2. Steady state equations of RBDN with network size decline
2.1. RBDN model

Consider the RBDN model:[27]

By the above evolving roles, the network size of the RBDN is always fluctuating in the evolving process. In particular, in the limit t → + ∞, the distribution of the network size follows geometric distributions.[27]

2.2. Steady state transformation equations

Using SPR,[21] we use (n,k) to describe the state of node v, where n is the number of nodes in the network that contains v, and k is the degree of node v. Let NK(t) denote the state of node v at time t, the stochastic process {NK(t), t ≥ 0} is an ergodic aperiodic homogeneous Markov chain with the state space E = {(n,k),n ≥ 1,0 ≤ k ≤ n − 1}.

Let be the probability distribution of NK(t), i.e.,

The state transformation equation is as follows (see Appendix A for the details):

where P is the one-step transition probability matrix. Let

Taking the limit of Eq. (2) as t → + ∞, the steady state transformation equations can be obtained

For r ≥ m + 1, we have

2.3. Steady state degree distribution equations

Let K be the steady state degree distribution,[15,30,31] and Π (k) be the probability distribution of K, then we will have

Combining Eq. (9) and steady state transformation equations (4)–(8), we can obtain the steady state degree distribution equations as follows:

3. Degree distribution of RBDN with network size decline

Let N(t) be the number of nodes in RBDN at time t, N(0) = m + 1, N the steady state network size, and ΠN(n) the probability distribution of N, then we will have

Considering the fact that {N(t),t ≥ 0} is a one-dimensional (1D) random walk with a left bound 1, we have

As shown in Eq. (10), we may employ the probability generating function method to obtain the exact solution of the degree distribution,[27] in which, Π(i,k) is a critical parameter. In the case of m=1, 2, as a special case, Π(1,0) can be obtained directly as follows:

However, in the case of m ≥ 3, as a general case, Π(i,k) is much more difficult to obtain. Thus in the following subsection, we focus on the calculation of Π(i,k).

3.1. Calculation of Π(i,k)

To obtain Π(i,k), is introduced, i.e.

Since

represents the contribution of the network with n nodes to the average degree E[K]. From Eq. (14) and the steady state transformation equations (4)–(8), we can obtain the equations of as follows:

where

To sum up the first n (n > m) items in Eq. (16), we can obtain

Note

then we will have

From Eq. (18), we have

Then the generation function for Eq. (16) can be rewritten as

satisfying

Solving the differential equation (23), can be obtained. Combining Eqs. (14) and (4)–(8), we have

Then Π(i,k) can be solved by Eq. (24).

3.2. Exact solutions of the degree distributions for m = 3,0<p<1/2

Once Π(i,k) is obtained, the probability generating function approach can be employed for Eq. (10) to obtain the steady state degree distribution Π (k). In this section, taking m = 3 for example, we explain how this approach is used. From Eq. (10), we can obtain the degree distribution equations of RBDN with 0 < p < 1/2, m = 3 as follows:

From Eq. (25) we may find that Π(2,0) and Π(2,1) are needed before we solve the degree distribution. In the case of m = 3, equation (16) can be rewritten as

Introducing the following generating function:

and combining Eq. (26), we have

Solving the differential equation (28), we have

Thus

Let

then

So, we have

For

Rewriting Eq. (34), we have

To solve Π (k), let the probability generating function be

According to Eqs. (25) and (35), we can obtain

Solving Eq. (37), we can obtain

So, the degree distributions of RBDN for 0 < p < 1/2, m = 3 are as follows:

where

Figure 1 illustrates the exact solutions (es) and simulation results of the degree distributions for 0 < p < 1/2, m = 3, where the horizontal and vertical ordinates denote the degree of nodes and the probability respectively. Each simulation number is an average value of 1000 simulation results for t = 104. As shown in Fig. 1, the exact solutions match perfectly with the numerical solutions (ns), verifying the correctness of our exact solutions.

Fig. 1. Comparisons between exact solution and numerical solution (t = 104) of degree distribution of RBDN for p < 1/2, m = 3.
4. Poisson tail

By Eq. (39), we may find that for the large k (k ≥ m + 1), the degree distribution of RBDN exhibits a backward accumulation form of Poisson distribution, that is,

where α is a positive constant and λ=mp/q. For sufficiently large k, we have

Thus in the case of 0 < p < 1/2, the degree distribution of RBDN exhibits a Poisson tail. Here we employ the same approach as in Ref. [27] to verify this Poisson tail for the degree distribution.

Let

then using Eq. (42), we will have

that is, r(k) is a line with slope −1 for large k in the two-logarithm axis diagram.

Figure 2 illustrates the Poisson tails of the degree distributions for various values of p (0 < p < 1/2). As we can see, in the case of k ≥ m+1, the slopes of lines tend to be −1, showing the Poisson tails for the degree distributions of RBDN.

Fig. 2. Poisson tails of RBDN with 0 < p < 1/2.
5. Conclusions

In this paper, we provide a general approach to obtaining the exact solutions of the degree distributions for RBDN in the case of 0 < p < 1/ 2, m ≥ 3. Specifically, taking m = 3 for example, we explain the detailed solving process and computer simulation is used to verify our degree distribution solutions. In addition, the characteristics of the degree distribution are discussed. Our findings suggest that the degree distributions will exhibit Poisson tail property for the declining RBDN.

Reference
1Barábasi A LAlbert R1999Science2865439
2Albert RBarabási A L 2002 Rev. Mod. Phys. 74 47
3Adamic L AHuberman B ABarabási A LAlbert RJeong HBianconi G2000Science2875461
4Dorogovtsev S NMendes J F F 2002 Adv. Phys. 51 1079
5Roger GAlex AAlbert D GFrancesc G 2002 Phys. Rev. 66 026704
6Onuttom NIraj S2010Phys. Rev. E82036102
7Watts D JStrogatz S H 1998 Nature 393 440
8Newman M E J 2003 SIAM Rev. 45 167
9Newman M E J 2001 Phys. Rev. 64 016131
10Newman M E J 2001 Phys. Rev. 64 016132
11Williams R JMartinez N D 2000 Nature 404 180
12Barbosa L ASilva A CSilva J K L 2006 Phys. Rev. 73 041903
13Otto S BRall B CBrose U 2007 Nature 450 1226
14Salda na J2007Phys. Rev. E75027102
15Barabási A LAlbert RJeong H 1999 Physica 272 173
16Slater J LHughes B DLandman K A 2006 Phys. Rev. 73 066111
17Sarshar NRoychowdhury V 2004 Phys. Rev. 69 026101
18Moore CGhoshal GNewman M E J 2006 Phys. Rev. 74 036121
19Garcia-Domingo J LJuher DSalda?na J 2008 Physica 237 640
20Ben-Naim EKrapivsky P L 2007 J. Phys. A: Math. Theor. 40 8607
21Zhang X JHe Z SHe ZLez R B 2012 Physica 391 3350
22Zou Z YLiu PLei LGao J Z 2012 Chin. Phys. 21 028904
23Tian L XHe Y HHuang Y2012Acta Phys. Sin.61228903(in Chinese)
24Ren X ZYang Z MWang B HZhou T 2012 Chin. Phys. Lett. 29 038904
25Wang X WYang G HLi X LXu X J 2013 Chin. Phys. 22 018903
26Yang G YLiu J G 2014 Chin. Phys. 23 018901
27Zhang X JHe ZLez R B 2016 J. Stat. Phys. 162 842
28Wang J RWang J PHe ZXu H T 2015 Chin. Phys. 24 060101
29Xu R JHe ZXie J RWang B H 2016 Physica 445 231
30Krapivsky P LRedner SLeyvraz F 2000 Phys. Rev. Lett. 85 4629
31Dorogovtsev S NMendes J F FSamukhin A N 2000 Phys. Rev. Lett. 85 4633