title: Markov chain-based numerical method for degree distributions of growing networks.
abstract: 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 (t(2)), 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.
authors.affiliation: Department of Mathematics, Shanghai University, Shanghai 200436, China.
authors.forename: Dinghua
authors.initials: D
authors.lastname: Shi
authors.forename: Qinghua
authors.initials: Q
authors.lastname: Chen
authors.forename: Liming
authors.initials: L
authors.lastname: Liu