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

2004/09/30 by Dinghua Shi, Qinghua Chen, Shi, Dinghua +3
Mathematics · Physics and Astronomy · #64.60.Fr #87.23.Ge #FOS: Physical sciences #Mathematical Physics (math-ph) #PACS: 84.35.+i #math-ph #math.MP #msc:64.60.Fr #msc:87.23.Ge

paper · pdf · doi:10.48550/arxiv.math-ph/0409080

11 pages, 3 figures, and 5 tables

arxiv created 2004/10/05 · arxiv updated 2009/12/01

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²), 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.

Related

• Degree-distribution stability of scale-free networks
• Degree distribution of complex networks from statistical mechanics principles
• Problems with classification, hypothesis testing, and estimator convergence in the analysis of degree distributions in networks
• Emerging properties of the degree distribution in large non-growing networks
• Quantification and Comparison of Degree Distributions in Complex Networks