Emergence of local structures in complex network:common neighborhood drives the network evolution

Cui Ai-Xiang; Fu Yan; Shang Ming-Sheng; Chen Duan-Bing; Zhou Tao

doi:10.7498/aps.60.038901

Abstract

After extensive study on the small-world and scale-free properties of networks, the research focus is shifting to detailed local structures. Empirical analysis shows that many real networks exhibit the power-law clique-degree distribution. This general regularity cannot be produced by the rich-get-richer mechanism. In this paper, we propose a common-neighborhood-dirven model in which the observed power-law clique-degree distribution con be well reproduced, indicating that the common-neighborhood-dirven mechanism is an essential factor leading to the emergence of local structures.

Keywords:

Authors and contacts

(1)Web Sciences Center, University of Electronic Science and Technology of China, Chengdu 611731, China; (2)Web Sciences Center, University of Electronic Science and Technology of China, Chengdu 611731, China;Department of Morden Physics, University of Science and Technology of China, Hefei 230026, China

References

[1]	Wang X F, Chen G R 2006 Complex Networks Theory and its Applications (Beijing:Tsinghua University Press)(in Chinese)[汪小帆、李翔、陈关荣 2006 复杂网络理论及其应用 (北京:清华大学出版社)]
[2]	He D R, Lin Z H, Wang B H 2008 Complex Systems and Complex Networks (Beijing: Higher Education Press)(in Chinese)[何大韧、刘宗华、汪秉宏 2008 复杂系统与复杂网络 (北京:高等教育出版社) ]
[3]	Wu J S, Di Z R 2004 Prog. Phys. 24 18 (in Chinese) [吴金闪、狄增如 2004 物理学进展 24 18]
[4]	Fang J Q 2006 Sci. Techn. Rev. 24 67 (in Chinese) [方锦清 2006 科技导报 24 67]
[5]	Zhou T, Bai W J, Wang B H, Liu Z J, Yan G 2005 Physics 34 31 (in Chinese) [周涛、柏文洁、汪秉宏、刘之景、严钢 2005 物理 34 31]
[6]	Li J, Wang B H, Jiang P Q, Zhou T, Wang W X 2006 Acta Phys. Sin. 55 4051 (in Chinese) [李季、汪秉宏、蒋品群、周涛、王文旭 2006 物理学报 55 4051]
[7]	Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹、李翔、汪小帆 2007 物理学报 56 1313]
[8]	Liu H K, Zhang X L, Cao L, Wang B H, Zhou T 2009 Sci. China Ser. G 39 935 (in Chinese) [刘宏鲲、张效莉、曹崀、汪秉宏、周涛 2009 中国科学G辑 39 935]
[9]	Zhang P P, He Y, Zhou T, Su B B, Chang H, Zhou Y P, Wang B H, He D R 2006 Acta Phys. Sin. 55 60 (in Chinese) [张培培、何阅、周涛、苏蓓蓓、常慧、周月平、汪秉宏、何大韧 2006 物理学报 55 60]
[10]	Weng W G, Ni S J, Shen S F, Yuan H Y 2007 Acta Phys. Sin. 56 1938 (in Chinese) [翁文国、倪顺江、申世飞、袁宏永 2007 物理学报 56 1938]
[11]	Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106 (in Chinese) [刘宏鲲、周涛 2007 物理学报 55 106]
[12]	Albert R, Barabasi A L 2002 Rev. Mod. Phys. 74 47
[13]	Dorogovtsev S N, Mendes J F F 2002 Adv. Phys. 51 1079
[14]	Watts D J, Strogatz S H 1998 Nature 393 440
[15]	Barabasi A L, Albert R 1999 Science 286 509
[16]	Holme P, Kim B J 2002 Phys. Rev. E 65 026107
[17]	Alon U 2002 Nat. Rev. Gene 8 450
[18]	Bianconi G, Caldarelli G, Capocci A 2008 Phys. Rev. Lett. 100 118701
[19]	Vazquez A, Dobrin R, Sergi D, Eckmann J P, Oltvai Z N, Barabasi A L 2004 Proc. Natl. Acad. Sci. USA 101 17940
[20]	Zhou T, Xiao W K, Ren J, Wang B H 2007 Complex Syst. Complex Sci. 4 10 (in Chinese) [周涛、肖伟科、任捷、汪秉宏 2007 复杂系统与复杂性科学 4 10]
[21]	Xiao W K, Ren J, Qi F, Zhu M X, Yang H F, Jin H Y, Wang B H, Zhou T 2007 Phys. Rev. E 76 037102
[22]	Yang H X, Wang B H, Liu J G, Han X P, Zhou T 2008 Chin. Phys. Lett. 25 2718
[23]	Caldarelli G 2007 Scale-free networks: complex webs in nature and technology (New York: Oxford University Press) p112
[24]	Barabási A L 2009 Science 325 412
[25]	Xing C M, Liu F A 2010 Acta Phys. Sin. 59 1608 (in Chinese) [邢长明、刘方爱 2010 物理学报 59 1608]
[26]	He M H, Zhang D M, Wang H Y, Li X G, Fang P J 2010 Acta Phys. Sin. 59 5175 (in Chinese) [何敏华、张端明、王海艳、李小刚、方频捷 2010 物理学报 59 5175]
[27]	Wang G Z, Cao Y J, Bao Z J, Han Z X 2009 Acta Phys. Sin. 58 3597 (in Chinese) [王光增、曹一家、包哲静、韩祯祥 2009 物理学报 58 3597]
[28]	Ou Y M, Fei Q, Yu M H 2008 Acta Phys. Sin. 57 6763 (in Chinese) [欧阳敏、费奇、余明晖 2008 物理学报 57 6763]
[29]	Tan S, Dai G Z, Wang L, Fan M 2007 Acta Phys. Sin. 56 6326 (in Chinese) [覃森、戴冠中、王林、范明 2007 物理学报 56 6326]
[30]	Kossinets G, Watts D J 2006 Science 311 88
[31]	Liben-Nowell D, Kleinberg J M 2007 J. Am. Soc. Inf. Sci . Tech. 58 1019
[32]	Zhou T, Lü L, Zhang Y C 2009 Eur. Phys. J. B 71 623
[33]	Klemm K, Eguiluz V M 2002 Phys. Rev. E 65 057102
[34]	Goldstein M L, Morris S A, Yen G G 2004 Eur. Phys. J. B 41 255
[35]	Garlaschelli D, Capocci A, Caldarelli G 2007 Nature Phyics. 3 813
[36]	Valverde S, Cancho R F, Sole R V 2002 Euro. Phys. Lett. 60 512
[37]	Baiesi M, Manna S S 2003 Phys. Rev. E 68 047103
[38]	Kim B J, Trusina A, Minnhagen P, Sneppen 2005 Eur. Phys. J. B 43 369
[39]	Perotti J I, Billoni O V, Tamarit F A, Chialvo D R, Cannas S A 2009 Phys. Rev. Lett. 103 10870

Cited By

[1]	Wang X F, Chen G R 2006 Complex Networks Theory and its Applications (Beijing:Tsinghua University Press)(in Chinese)[汪小帆、李翔、陈关荣 2006 复杂网络理论及其应用 (北京:清华大学出版社)]
[2]	He D R, Lin Z H, Wang B H 2008 Complex Systems and Complex Networks (Beijing: Higher Education Press)(in Chinese)[何大韧、刘宗华、汪秉宏 2008 复杂系统与复杂网络 (北京:高等教育出版社) ]
[3]	Wu J S, Di Z R 2004 Prog. Phys. 24 18 (in Chinese) [吴金闪、狄增如 2004 物理学进展 24 18]
[4]	Fang J Q 2006 Sci. Techn. Rev. 24 67 (in Chinese) [方锦清 2006 科技导报 24 67]
[5]	Zhou T, Bai W J, Wang B H, Liu Z J, Yan G 2005 Physics 34 31 (in Chinese) [周涛、柏文洁、汪秉宏、刘之景、严钢 2005 物理 34 31]
[6]	Li J, Wang B H, Jiang P Q, Zhou T, Wang W X 2006 Acta Phys. Sin. 55 4051 (in Chinese) [李季、汪秉宏、蒋品群、周涛、王文旭 2006 物理学报 55 4051]
[7]	Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹、李翔、汪小帆 2007 物理学报 56 1313]
[8]	Liu H K, Zhang X L, Cao L, Wang B H, Zhou T 2009 Sci. China Ser. G 39 935 (in Chinese) [刘宏鲲、张效莉、曹崀、汪秉宏、周涛 2009 中国科学G辑 39 935]
[9]	Zhang P P, He Y, Zhou T, Su B B, Chang H, Zhou Y P, Wang B H, He D R 2006 Acta Phys. Sin. 55 60 (in Chinese) [张培培、何阅、周涛、苏蓓蓓、常慧、周月平、汪秉宏、何大韧 2006 物理学报 55 60]
[10]	Weng W G, Ni S J, Shen S F, Yuan H Y 2007 Acta Phys. Sin. 56 1938 (in Chinese) [翁文国、倪顺江、申世飞、袁宏永 2007 物理学报 56 1938]
[11]	Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106 (in Chinese) [刘宏鲲、周涛 2007 物理学报 55 106]
[12]	Albert R, Barabasi A L 2002 Rev. Mod. Phys. 74 47
[13]	Dorogovtsev S N, Mendes J F F 2002 Adv. Phys. 51 1079
[14]	Watts D J, Strogatz S H 1998 Nature 393 440
[15]	Barabasi A L, Albert R 1999 Science 286 509
[16]	Holme P, Kim B J 2002 Phys. Rev. E 65 026107
[17]	Alon U 2002 Nat. Rev. Gene 8 450
[18]	Bianconi G, Caldarelli G, Capocci A 2008 Phys. Rev. Lett. 100 118701
[19]	Vazquez A, Dobrin R, Sergi D, Eckmann J P, Oltvai Z N, Barabasi A L 2004 Proc. Natl. Acad. Sci. USA 101 17940
[20]	Zhou T, Xiao W K, Ren J, Wang B H 2007 Complex Syst. Complex Sci. 4 10 (in Chinese) [周涛、肖伟科、任捷、汪秉宏 2007 复杂系统与复杂性科学 4 10]
[21]	Xiao W K, Ren J, Qi F, Zhu M X, Yang H F, Jin H Y, Wang B H, Zhou T 2007 Phys. Rev. E 76 037102
[22]	Yang H X, Wang B H, Liu J G, Han X P, Zhou T 2008 Chin. Phys. Lett. 25 2718
[23]	Caldarelli G 2007 Scale-free networks: complex webs in nature and technology (New York: Oxford University Press) p112
[24]	Barabási A L 2009 Science 325 412
[25]	Xing C M, Liu F A 2010 Acta Phys. Sin. 59 1608 (in Chinese) [邢长明、刘方爱 2010 物理学报 59 1608]
[26]	He M H, Zhang D M, Wang H Y, Li X G, Fang P J 2010 Acta Phys. Sin. 59 5175 (in Chinese) [何敏华、张端明、王海艳、李小刚、方频捷 2010 物理学报 59 5175]
[27]	Wang G Z, Cao Y J, Bao Z J, Han Z X 2009 Acta Phys. Sin. 58 3597 (in Chinese) [王光增、曹一家、包哲静、韩祯祥 2009 物理学报 58 3597]
[28]	Ou Y M, Fei Q, Yu M H 2008 Acta Phys. Sin. 57 6763 (in Chinese) [欧阳敏、费奇、余明晖 2008 物理学报 57 6763]
[29]	Tan S, Dai G Z, Wang L, Fan M 2007 Acta Phys. Sin. 56 6326 (in Chinese) [覃森、戴冠中、王林、范明 2007 物理学报 56 6326]
[30]	Kossinets G, Watts D J 2006 Science 311 88
[31]	Liben-Nowell D, Kleinberg J M 2007 J. Am. Soc. Inf. Sci . Tech. 58 1019
[32]	Zhou T, Lü L, Zhang Y C 2009 Eur. Phys. J. B 71 623
[33]	Klemm K, Eguiluz V M 2002 Phys. Rev. E 65 057102
[34]	Goldstein M L, Morris S A, Yen G G 2004 Eur. Phys. J. B 41 255
[35]	Garlaschelli D, Capocci A, Caldarelli G 2007 Nature Phyics. 3 813
[36]	Valverde S, Cancho R F, Sole R V 2002 Euro. Phys. Lett. 60 512
[37]	Baiesi M, Manna S S 2003 Phys. Rev. E 68 047103
[38]	Kim B J, Trusina A, Minnhagen P, Sneppen 2005 Eur. Phys. J. B 43 369
[39]	Perotti J I, Billoni O V, Tamarit F A, Chialvo D R, Cannas S A 2009 Phys. Rev. Lett. 103 10870

[1]	Ruan Yi-Run, Lao Song-Yang, Tang Jun, Bai Liang, Guo Yan-Ming. Node importance ranking method in complex network based on gravity method. Acta Physica Sinica, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
[2]	Wang Zhen-Hua, Liu Zong-Hua. Partial synchronization in complex networks: Chimera state, remote synchronization, and cluster synchronization. Acta Physica Sinica, 2020, 69(8): 088902. doi: 10.7498/aps.69.20191973
[3]	Kong Jiang-Tao, Huang Jian, Gong Jian-Xing, Li Er-Yu. Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models. Acta Physica Sinica, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
[4]	Wang Xiao-Yang, Wang Ying, Zhu Can-Shi, Zhu Lin, Fu Chao-Qi. Information radiation model with across neighbor spread abilities of nodes. Acta Physica Sinica, 2017, 66(3): 038901. doi: 10.7498/aps.66.038901
[5]	Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong. Node importance measurement based on neighborhood similarity in complex network. Acta Physica Sinica, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
[6]	Han Zhong-Ming, Chen Yan, Li Meng-Qi, Liu Wen, Yang Wei-Jie. An efficient node influence metric based on triangle in complex networks. Acta Physica Sinica, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
[7]	Min Lei, Liu Zhi, Tang Xiang-Yang, Chen Mao, Liu San-Ya. Evaluating influential spreaders in complex networks by extension of degree. Acta Physica Sinica, 2015, 64(8): 088901. doi: 10.7498/aps.64.088901
[8]	Yuan Ming. A cascading failure model of complex network with hierarchy structure. Acta Physica Sinica, 2014, 63(22): 220501. doi: 10.7498/aps.63.220501
[9]	Wang Ya-Qi, Wang Jing, Yang Hai-Bin. An evolution model of microblog user relationship networks based on complex network theory. Acta Physica Sinica, 2014, 63(20): 208902. doi: 10.7498/aps.63.208902
[10]	Duan Dong-Li, Zhan Ren-Jun. Evolution mechanism of node importance based on the information about cascading failures in complex networks. Acta Physica Sinica, 2014, 63(6): 068902. doi: 10.7498/aps.63.068902
[11]	Liu Shu-Xin, Ji Xin-Sheng, Liu Cai-Xia, Guo Hong. A complex network evolution model for network growth promoted by information transmission. Acta Physica Sinica, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902
[12]	Hu Feng, Zhao Hai-Xing, He Jia-Bei, Li Fa-Xu, Li Shu-Ling, Zhang Zi-Ke. An evolving model for hypergraph-structure-based scientific collaboration networks. Acta Physica Sinica, 2013, 62(19): 198901. doi: 10.7498/aps.62.198901
[13]	Zhang Cong, Shen Hui-Zhang, Li Feng, Yang He-Qun. Multi-resolution density modularity for finding community structure in complex networks. Acta Physica Sinica, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
[14]	Zhou Xuan, Zhang Feng-Ming, Li Ke-Wu, Hui Xiao-Bin, Wu Hu-Sheng. Finding vital node by node importance evaluation matrix in complex networks. Acta Physica Sinica, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
[15]	Xing Chang-Ming, Liu Fang-Ai. Research on the deterministic complex network model based on the Sierpinski network. Acta Physica Sinica, 2010, 59(3): 1608-1614. doi: 10.7498/aps.59.1608
[16]	Wang Guang-Zeng, Cao Yi-Jia, Bao Zhe-Jing, Han Zhen-Xiang. A novel local-world evolving network model for power grid. Acta Physica Sinica, 2009, 58(6): 3597-3602. doi: 10.7498/aps.58.3597
[17]	Ouyang Min, Fei Qi, Yu Ming-Hui. Estimation and improvement of disaster spreading models based on complex network. Acta Physica Sinica, 2008, 57(11): 6763-6770. doi: 10.7498/aps.57.6763
[18]	Lin Hai, Wu Chen-Xu. Evolution of strategies based on genetic algorithm in the iterated prisoner’s dilemma on complex networks. Acta Physica Sinica, 2007, 56(8): 4313-4318. doi: 10.7498/aps.56.4313
[19]	Li Ji, Wang Bing-Hong, Jiang Pin-Qun, Zhou Tao, Wang Wen-Xu. Growing complex network model with acceleratingly increasing number of nodes. Acta Physica Sinica, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
[20]	Guo Jin-Li. The bilateral power-law distribution model of supply chain networks. Acta Physica Sinica, 2006, 55(8): 3916-3921. doi: 10.7498/aps.55.3916

Catalog

Vol. 60, Issue 3 - 2011-02-05

Metrics

Abstract views: 11161
PDF Downloads: 3504
Cited By: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

Search

Article

留言板