Acta mathematica scientia, Series B >
MARKOV CHAIN-BASED ANALYSIS OF THE DEGREE DISTRIBUTION FOR A GROWING NETWORK
Received date: 2008-07-09
Revised date: 2008-11-25
Online published: 2011-01-20
Supported by
This research is supported by the National Natural Science Foundation (11071258, 60874083, 10872119, 10901164)
In this article, we focus on discussing the degree distribution of the DMS model from the perspective of probability. On the basis of the concept and technique of first-passage probability in Markov theory, we provide a rigorous proof for existence of the steady-state degree distribution, mathematically re-deriving the exact formula of the distribution. The approach based on Markov chain theory is universal and performs well in a large class of growing networks.
Key words： Growing networks; preferential attachment; power law
HOU Zhen-Ting , TONG Jin-Ying , SHI Ding-Hua . MARKOV CHAIN-BASED ANALYSIS OF THE DEGREE DISTRIBUTION FOR A GROWING NETWORK[J]. Acta mathematica scientia, Series B, 2011 , 31(1) : 221 -228 . DOI: 10.1016/S0252-9602(11)60222-1
[1] Erd\"{o}s P, Rényi P. On Random Graphs I. Debrecen: Publications Mathematicae, 1959
[2] Bollobás B. Random Graphs. London: Academic Press, 1985
[3] Barabási A, Albert R. Emergence of scaling in random networks. Science, 1999, 286: 509--512
[4] Hou Z T, Kong X X, et al. Degree-distribution stability of scale-free networks, e-print cond-mat/08051434v1
[5] Barabási A L, Albert R, Jeong H. Mean-field theory for scale-free random networks. Physica A, 1999, 272: 173--197
[6] Boccaletti S, Latora V, et al. Complex networks: structure and dynamics. Phys Reports, 2006, 424: 175--308
[7] Dorogovtsev S N, Mendes J F F, Samukhin A N. Structure of growing networks with preferential linking. Phys Rev Lett, 2000, 85: 4633--4636
[8] Bollobás B, Riordan O M, et al. The degree sequence of a scale-free random graph process. Random Structures and Algorithms, 2001, 18: 279--290
[9] Shi D H, Chen Q H, Liu L M. Markov chain-based numerical method for degree distributions of growing networks. Phys Rev E, 2005, 71: 036140--036149
[10] Shi D H, Liu L M, et al. Degree distributions of evolving networks. Europhys Lett, 2006, 76: 731--737
[11] Cooper C, Frieze A. A general model of web graphs. Random Structures and Algorithms, 2003, 22: 311--335
[12] Jia W, Fan W T. The avalanche dynamics in random nearest neighbor models of evolution with interaction strength. Acta Mathematica Scientia, 2006, 26B(1): 179--187
[13] Stolz O. Vorlesungen uber Allgemeine Arithmetic. Teubner: Leipzig, 1886
/
| 〈 |
|
〉 |