Degree Distribution Of Several Interrelated Small World Network Model

Networks exist in every aspect of nature and society. Most of the systems, e.g. WWW, social relationship networks, biological neural networks and so on, can be described as complex network. Thus, complex network attracts much attention from all research circles and have found many potential applications in a variety of fields. Recently, the discovery of small-world effect and scale-free character in real-life network stimulate more researchers' interest.An important measure of complex networks is its steady-state degree distribution. The theoretical analysis of degree-distribution can promote the acquaintance of the topological structure and statistical features of network, so many scholars have concentrated their energy on the research of degree distribution. The main study methods to degree distribution are mean-field approach, master-equation approach, rate-equation approach and Markov chains approach. Generally, physicists derive steady-state degree distribution of networks by using the mean-field theory, master-equation and rate-equation approach, but their methods are not rigorous mathematically. From stating the average number of vertices in a graph with total degree k , Bollobas et al. analyze its asymptotical expression, and the steady-state degree distribution of a scale-free random graph process is proved by martingale inequality. But this method doesn't apply to other networks. Recently, based on the concept and techniques of first-passage probability in Markov chain theory, Professor Hou provides a rigorous proof for the existence of the steady-state degree distribution of BA model and mathematically re-derives the exact analytic formulas of the distribution. We named it first-passage probability approach.Based on master-equation approach and first-passage probability approach, this paper derives the exact formulas of the distribution of three relevant small-world network models, and proves the existence of the steady-state degree distribution. It shows the first-passage probability approach is applicable to small-world networks also.