International Journal of Information Technology and Computer Science(IJITCS)

ISSN: 2074-9007 (Print), ISSN: 2074-9015 (Online)

Published By: MECS Press

IJITCS Vol.5, No.6, May. 2013

Random Connection Based Scale-free Networks

Full Text (PDF, 603KB), PP.10-15

Views:92   Downloads:2


Shun-Li Lou, Xu-Hua Yang

Index Terms

Scale-Free Network, Random Connection, Neighbor


Scale-free phenomenon has opened up a new network model as a special form of degree distribution. Preferential connection and growth constitutive are generally considered as the tow key factors in the formation of scale-free network. However, some network model with completely random connections instead of preferential connection can also generate scale-free networks, such as the protein interaction network in a cell. The article constructed such a random connection way: select an arbitrary neighbor vertex of a random vertex to add side. Through our simulation shows this model absolutely has the characteristics of scale-free networks. And the power-law distribution index [1+β^(-1)] of the new model is related to m which is the number of add edges every time. When m is sufficiently large, [1+β^(-1)] tends to quickly stable and the final size is 3. Then we use the Mean field theory analyzed theoretically, and get an analytic solution of degree distribution. Our study reveals that random connections without preferential strategy can also generate scale-free network.

Cite This Paper

Shun-Li Lou, Xu-Hua Yang,"Random Connection Based Scale-free Networks", International Journal of Information Technology and Computer Science(IJITCS), vol.5, no.6, pp.10-15, 2013. DOI: 10.5815/ijitcs.2013.06.02


[1]Matisziw T C, Grubesic T H, Guo Junyu. Robustness elasticity in complex networks[J]. Plos one,2012,7(7): e39788. doi:10.1371.

[2]Zhang X, Zhao Q G. Degree distribution of a new model for evolving networks[J]. Pramana-journal of physics, 2010,74:469-474.

[3]Dror Y. Kenett, Tobias Preis, Gitit G G, Eshel B J. Dependency network and node influence:application to the study of financial markets[J]. International Journal of Bifurcation and Chaos,2012, 22(7):1250181.

[4]Zhang J J, Ning H Y, Yin Z Y. A novel snowdrift game model with edge weighting mechanism on the square lattice[J]. Frontiers of physics,2012,7:366-372.

[5]Subelj L, Bajec M. Ubiquitousness of link-density and link-pattern communities in real-world networks[J], Eur. Phys. J.B,2012, 10.1140/epjb/e2011-20448-7.

[6]Ercsey Ravasz M, Lichtenwalter RN, Chawla NV, Toroczkai Z. Range-limited centrality measures in complex networks[J]. Phys. Rev. E,2012,85:066103.

[7]Xu X J, Hu X M, Zhang Li Jie. Network evolution by nonlinear preferential rewiring of edges[J]. Physica A,2011,390:2429-2434.

[8]Luo X J , Yu H Q , Wang X . Energy-Aware topology evolution model with link and node deletion in wireless sensor networks[M]. Mathematical problems in engineering ,2012,2012:281465.

[9]Jia T, Jiang B. Building and analyzing the US airport network based on en-route location information[J]. Physica A, 2012,391:4031-4042.

[10]Guan Z H, Wu Z P. The physical position neighbourhood evolving network model[J]. Physica A,2007,387:314-322. 

[11]Yang XuHua, Chen G, Sun B, Chen S Y, Wang W L. Bus transport network model with ideal n-depth clique network topology[J]. Physica A,2011,390:4660–4672.

[12]Yang XuHua, Wang B, Chen S-Y, Wang W-L. Epidemic dynamics behavior in some bus transport networks[J]. Physica A,2012,391:917–924.

[13]Lyocsa S, Vyrost T, Baumoehl E. Stock market networks: The dynamic conditional correlation approach[J]. Physica A,2012,391:4147-4158.

[14]Barabasi A L, Albert R. Emergence of scaling in random networks[J]. Science 286 (1999) 509-512. 

[15]Barabasi A L, Albert R, Jeong H. Mean-field theory for scale-free random networks[J]. Physica A ,1999,272:173-187.

[16]Liu Y Y, Slotine J J, Barabasi A L. Controllability of complex networks[J]. Nature, 2011,473:167-173.

[17]Wang W X, Ni X, Lai Y C. Optimizing controllability of complex networks by minimum structural perturbations[J]. Phys. Rev. E,2012,85 :026115.

[18]Liu Y Y, Slotine J J, Barabasi A L. Control centrality and hierarchical structure in complex networks[J].Plos one,2012, 7(9): e44459. doi:10.1371.

[19]Liu Y Y, Csoka Endre, Zhou Haijun, Posfai Marton. Core percolation on complex networks[J]. Phys. Rev. L, 2012,109: 205703.

[20]Liu R R, Jia C X, Wang B H. Heritability promotes cooperation in spatial public goods games[J]. Physica A,2010,389:5719-5724.

[21]Du W B, Cao X B, Hu M B. The effect of asymmetric payoff mechanism on evolutionary networked prisoner's dilemma game[J]. Physica A,2009,388:5005-5012.

[22]Nicolaides, C., Cueto-Felgueroso, L., & Juanes, R. (2010). Anomalous physical transport in complex networks. Physical Review E, 82(5), 055101.

[23]Dror Y. Kenett, Michele Tumminello, Asaf Madi, Gitit G G,Rosario N. Mantegna, Eshel B-J. Dominating Clasp of the Financial Sector Revealed by Partial Correlation Analysis of the Stock Market[J]. PLoS One, 2010; 5(12): e15032. 

[24]Fan Z P, Chen G R, Zhang Y N. A comprehensive multi-local-world model for complex networks[J]. Phys. Lett. A, 2009,373:1601–1605.

[25]Wang L N, Guo J L, Yang H X, Zhou T. Local preferential attachment model for hierarchical networks[J]. Physica A,2009,388:1713-1720.

[26]Sheridan P, Yagahara Y, Shimodaira H. A preferential attachment model with Poisson growth for scale-free networks[M]. Annals of the institute of statistical mathematics ,2008,60:747-761.

[27]Chen X Y. Weighted BA scale-Free random graph model[M]. Materials science and information technology ,2012,433-440:2780-2783. 

[28]Xie Y B, Zhou T, Wang B H. Scale-free networks without growth[J]. Physica A,2008,387:1683–1688.

[29]Park K, Lai Y-C. Self-organized scale-free networks[J]. Phys. Rev. E,2005,72: 026131.

[30]Kim B J, Trusina A, Minnhagen P, Kim S. Self-organized scale-Free networks from merging and regeneration[J]. European Physical Journal B,2005,43: 369-372.

[31]Fu C B, Wang X G. Network growth under the constraint of synchronization stability[J]. Phys. Rev. E,2011,83:066101. 

[32]Newman N E J. Ego-centered networks and the ripple effect[J]. Social Networks,2003,25:83–95.

[33]Feld S L. Why your friends have more friends than you do[J]. The American Journal of Sociology,1991,96:1464-1477.