Recursive tree network

Let's call the number of nodes with degree $q$ at time $t$ , $N_q(t)$ .

According to the way the network is grown, the total number of nodes at time $t$ is given by $N(t) = \sum\limits_qN_q(t) = 1+t$ .

Also, we have the following relation between the number of nodes of degree $q$ at a given time, and the probability that a given node has degree $q$ at a given time: $\displaystyle p_q(t) \equiv \frac{N_q(t)}{1+t}$

At each step in the growth process, the number of nodes of degree $q$ can increase or decrease by 1. It can increase if the new node attaches to an existing node of degree $q-1$ . It can also decrease if the new node attaches to an existing node of degree $q$ , turning it into a node of degree $q+1$ . Every individual node has a chance $\frac{1}{1+t}$ of being picked for attachment at every round and thus a degree class has a chance $\displaystyle \frac{N_q(t)}{1+t}$ for one of its members being picked. We therefore have:

$N_q(t+1) = \frac{N_{q-1}(t)}{1+t} + N_q(t)\left(1-\frac{1}{1+t}\right) + \delta_{1,q}$

(The $\delta_{1,q}$ because a node of degree 1 is added at each time step).

We can rewrite this in terms of the probabilities, $p_q(t)$ :

$\left(t+2\right)p_q(t+1) = p_{q-1}(t) + tp_q(t) + \delta_{1,q}$

At long times, the network statistics become more or less constant and we have

$p_q(t) = p_q(t+1)$

This leads to

$2p_q = p_{q-1} + \delta_{1,q}$

After time zero, $p_0 = 0$ and so, for $q = 1$ , we have

$2p_1 = 0 + \delta_{1,1}$

so that $p_1 = \frac{1}{2}$ . Similarly, we have $2p_j = p_{j-1} + 0$ , $\forall j > 1$ . Therefore, $\boxed{p_d = \frac{1}{2^d}}$ for degree $d > 0$ and $\boxed{p_0 = 0}$ .

A program to test with a random generated tree:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from random import random

N=100000
degrees = N*[1]

for i in xrange(2, N):
    degrees[ int(random() * i) ] += 1

degree = 1
tot = 0
while tot < N or int(round(N/(2**degree)))>0:
        nb = len([1 for i in degrees if i == degree])
        tot += nb
        print degree, ":", nb, "(theory:", int(round(N/(2**degree))), ")"
        degree += 1