Acta mathematica scientia, Series B >
Received date: 2008-07-17
Online published: 2010-09-20
Supported by
Supported by the National Natural Science Foundation of China (10671212, 60874083, 10872119).
The growing network model with loops and multiple edges proposed by Bollobás et al. (Random Structures and Algorithms 18(2001))
is restudied from another perspective. Based on the first-passage probability of Markov chains, we prove that the degree distribution of the LCD model is power-law with degree exponent 3 as the network size grows to infinity.
Key words： Markov chain; stability; power-law
HOU Zhen-Ting , TAN Li , SHI Ding-Hua . [J]. Acta mathematica scientia, Series B, 2010 , 30(5) : 1523 -1528 . DOI: 10.1016/S0252-9602(10)60145-2
[1] Albert R, Jeong H, Barab\'{a}si A L. Diameter of the world wide web. Nature, 1999, 401: 130--131
[2] Barabási A L, Albert R, Jeong H. Mean-field theory for scale-free random networks. Physics A, 1999, 272: 173--187
[3] Krapivsky P L, Redner S, Leyvraz F, Connectivity of growing random networks. Phys Rev Lett, 2000, 85: 4629--4632
[4] Dorogovtsev S N, Mendes J F F, Samukhin A N. Structure of growing networks with preferential linking. Phys Rev Lett, 2000, 85: 4633-4636
[5] Bollob\'{a}s B, Riordan O. Mathematical results on scale-free random graphs//Handbook of Graphs and Networks. Berlin: Wiley-VCH, 2002: 1--34
[6] Bollobás B, Riordan O M, Spencer J, Tusnády G. The degree sequence of a scale-free random graph process. Random Structures and Algorithms, 2001, 18: 279--290
[7] Shi D H, Chen Q H, Liu L M. Markov chain-based numerical method for degree distribution of growing networks. Phys Rev E, 2005, 71: 036140
[8] Hagberg O, Wiuf C. Convergence properties of the degree distribution of some growing network models. Bulletin of Mathematical Biology, 2006, 68: 1275--1291
[9] Hou Z T, Kong X X. Exact solution of the degree distribution for an evolving network. Acta Mathematica Scientia, 2009, 29B(3): 723--730
[10] Tan L, Hou Z T, Kong X X, Zhao Q G. Degree distribution analysis of a random graph process based on Markov chains//Du Dingzhu, Zhang Xiangsun, eds. Operations Research and Its Applications. Beijing: World Publishing Corporation, 2009: 394--401
[11] Stolz O. Vorlesungen Uber Allgeiene Arithmetic. Teubner: Leipzig, 1886
[12] Buckley P G, Osthus D. Popularity based random graph models leading to a scale-free degree degree sequence. Discrete Mathematics, 2004, 282: 53--68
/
| 〈 |
|
〉 |