A Markov Chain-Based Numerical Method for Calculating Network Degree Distributions

Abstract

This paper establishes a relation between scale-free networks and Markov chains, and proposes a computation framework for degree distributions of scale-free networks. We first find that, under the BA model, the degree evolution of individual nodes in a scale-free network follows some non-homogeneous Markov chains. Exploring the special structure of these Markov chains, we are able to develop an efficient algorithm to compute the degree distribution numerically. The complexity of our algorithm is O(t^2), where $t$ is the number of time steps for adding new nodes. We use three examples to demonstrate the computation procedure and compare the results with those from the existing methods.

11 pages, 3 figures, and 5 tables

References in corpus (12)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Lethality and centrality in protein networks
• The diameter of the world wide web
• Mean-field theory for scale-free random networks
• Hierarchical Organization in Complex Networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Topology of evolving networks: local events and universality
• Connectivity of Growing Random Networks
• Bose-Einstein condensation in complex networks
• Evolution of reference networks with aging
• Scaling properties of scale-free evolving networks: Continuous approach