Markov chain-based numerical method for degree distributions of growing networks

In this paper, we establish a relation between growing networks and Markov chains, and propose a computational approach for network degree distributions. Using the Barabási-Albert model as an example, we first show that the degree evolution of a node in a growing network follows a nonhomogeneous Markov chain. Exploring the special structure of these Markov chains, we develop an efficient algorithm to compute the degree distribution numerically with a computation complexity of $O\left(t^2\right)$, where $t$ is the number of time steps. We use three examples to demonstrate the computation procedure and compare the results with those from existing methods.

Figure 1

The complete degree distributions of the BA model with different $m$ and $t$. From left to right by the numerical method: (1) $m=1$ and $S=1$ with $t=150000$; (2) $m=3$ and $S=2$ with $t=100000$, 150 000, and 200 000, respectively; and (3) $m=5$ and $S=3$ and $t==150000$. The analytical results from formula (4) is the dashed line, with $m=5$.

Figure 2

The degree distributions of the BA model with $m=5$ for $S=3$ and 13.

Figure 3

The degree distributions of the BA model for $m=1$, 3, and 5 from left to right.

Figure 4

The degree distributions of the power function case. Five solid curves for numerical results from left to right for (1) $m=1$ with $t=150000$; (2) $m=3$ with $t=100000$, 150 000, and 200 000; and (3) $m=5$ with $t=150000$. Three dashed lines for the corresponding analytic results from left to right for: $m=1$, $t=150000$; $m=3$, $t=200000$; and $m=5$, $t=150000$.

Figure 5

The degree distributions of the logarithmic function case. Five curves from left to right for (1) $m=1$ with $t=150000$; (2) $m=3$ with $t=100000$, 150 000, and 200 000; and (3) $m=5$ with $t=150000$.