Hidden Tree Structure is a Key to the Emergence of Scaling in the World Wide Web
ZHENG Bo-Jin1,2**, WANG Jian-Min1, CHEN Gui-Sheng3, JIANG Jian4, SHEN Xian-Jun5
1School of Software, Tsinghua University, Beijing 100084 2College of Computer Science, South-Central University for Nationalities, Wuhan 430074 3Institute of Chinese Electronic Engineering, Beijing 100840 4Institute of Command and Technology of Equipment, Beijing 101416 5Department of Computer Science, Central-China Normal University, Wuhan 430072
Hidden Tree Structure is a Key to the Emergence of Scaling in the World Wide Web
ZHENG Bo-Jin1,2**, WANG Jian-Min1, CHEN Gui-Sheng3, JIANG Jian4, SHEN Xian-Jun5
1School of Software, Tsinghua University, Beijing 100084 2College of Computer Science, South-Central University for Nationalities, Wuhan 430074 3Institute of Chinese Electronic Engineering, Beijing 100840 4Institute of Command and Technology of Equipment, Beijing 101416 5Department of Computer Science, Central-China Normal University, Wuhan 430072
摘要Preferential attachment is the most popular explanation for the emergence of scaling behavior in the World Wide Web, but this explanation has been challenged by the global information hypothesis, the existence of linear preference and the emergence of new big internet companies in the real world. We notice that most websites have an obvious feature that their pages are organized as a tree (namely hidden tree) and hence propose a new model that introduces a hidden tree structure into the Erdös–Rényi model by adding a new rule: when one node connects to another, it should also connect to all nodes in the path between these two nodes in the hidden tree. The experimental results show that the degree distribution of the generated graphs would obey power law distributions and have variable high clustering coefficients and variable small average lengths of shortest paths. The proposed model provides an alternative explanation to the emergence of scaling in the World Wide Web without the above-mentioned difficulties, and also explains the "preferential attachment" phenomenon.
Abstract：Preferential attachment is the most popular explanation for the emergence of scaling behavior in the World Wide Web, but this explanation has been challenged by the global information hypothesis, the existence of linear preference and the emergence of new big internet companies in the real world. We notice that most websites have an obvious feature that their pages are organized as a tree (namely hidden tree) and hence propose a new model that introduces a hidden tree structure into the Erdös–Rényi model by adding a new rule: when one node connects to another, it should also connect to all nodes in the path between these two nodes in the hidden tree. The experimental results show that the degree distribution of the generated graphs would obey power law distributions and have variable high clustering coefficients and variable small average lengths of shortest paths. The proposed model provides an alternative explanation to the emergence of scaling in the World Wide Web without the above-mentioned difficulties, and also explains the "preferential attachment" phenomenon.
ZHENG Bo-Jin;**;WANG Jian-Min;CHEN Gui-Sheng;JIANG Jian;SHEN Xian-Jun
. Hidden Tree Structure is a Key to the Emergence of Scaling in the World Wide Web[J]. 中国物理快报, 2011, 28(1): 18901-018901.
ZHENG Bo-Jin, **, WANG Jian-Min, CHEN Gui-Sheng, JIANG Jian, SHEN Xian-Jun
. Hidden Tree Structure is a Key to the Emergence of Scaling in the World Wide Web. Chin. Phys. Lett., 2011, 28(1): 18901-018901.
[1] Barabási A L and Albert R 1999 Science 286 509
[2] Willis J C and Yule G U 1922 Nature 109 177
[3] Yule G U 1925 Philos. Trans. R. Soc. London B 213 21
[4] Price D 1965 Science 149 510
[5] Bornholdt S and Ebel H 2000 arXiv:cond-mat/0008465
[6] Bornholdt S and Ebel H 2001 Phys. Rev. E 64 035104(R)
[7] Vázquez A 2000 arXiv:cond-mat/0006132v4
[8] Krapivsky P L and Redner S 2001 Phys. Rev. E 63 066123
[9] Adamic L A and Huberman B A 2000 Science 287 2115
[10] Barabási A L, Albert R, Jeong H and Bianconi G 2000 Science 287 2115a
[11] Bianconi G and Barabási A L 2001 Phys. Rev. Lett. 86 5632
[12] Bianconi G and Barabási A L 2001 Europhys. Lett. 54 436
[13] Ravasz E and Barabási A L 2003 Phys. Rev. E 67 026112
[14] Merton R K 1968 Science 159 56
[15] Holland J 1995 Hidden Order: How Adaptation Builds Complexity (Massachusetts, USA: Perseus Books)
[16] Newman M E J 2005 Contemp. Phys. 46 323
[17] Reed W J and Hughes B D 2002 Phys. Rev. E 66 067103
[18] Miller G A 1957 Am. J. Psychol. 70 311
[19] Li W 1992 IEEE Trans. Inf. Theory 38 1842
2011, Vol. 28 
