复杂网络局部结构的涌现:共同邻居驱动网络演化

崔爱香; 傅彦; 尚明生; 陈端兵; 周涛

doi:10.7498/aps.60.038901

摘要

在对真实网络的小世界和无标度特性进行了大量深入考量之后,最近的研究热点开始转移到更加细致的局部结构.实证数据显示,大量真实网络具有幂律的低阶集团度分布.这一普适的规律,无法由富者愈富以及熟人推荐的网络生长机理再现.本文提出一种由共同邻居驱动的网络演化模型,该模型能够重现实证研究所观察到的幂律集团度分布,暗示共同邻居驱动是复杂网络局部结构涌现形成的内在机理.

关键词:

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:

作者及机构信息

(1)电子科技大学计算机科学与工程学院,互联网科学中心,成都 611731; (2)电子科技大学计算机科学与工程学院,互联网科学中心,成都 611731;中国科学技术大学近代物理系,合肥 230026

基金项目: 国家自然科学基金重大研究计划(批准号:90924011), 国家自然科学基金重点项目(批准号:10635040)和国家自然科学基金(批准号:60973069)资助的课题.

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

参考文献

[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]	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]	阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
[2]	王振华, 刘宗华. 复杂网络上的部分同步化: 奇异态、遥同步与集团同步. 物理学报, 2020, 69(8): 088902. doi: 10.7498/aps.69.20191973
[3]	孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
[4]	汪筱阳, 王瑛, 朱参世, 朱琳, 傅超琦. 具有跨邻居传播能力的信息辐射模型研究. 物理学报, 2017, 66(3): 038901. doi: 10.7498/aps.66.038901
[5]	阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
[6]	韩忠明, 陈炎, 李梦琪, 刘雯, 杨伟杰. 一种有效的基于三角结构的复杂网络节点影响力度量模型. 物理学报, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
[7]	闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙). 基于扩展度的复杂网络传播影响力评估算法. 物理学报, 2015, 64(8): 088901. doi: 10.7498/aps.64.088901
[8]	袁铭. 带有层级结构的复杂网络级联失效模型. 物理学报, 2014, 63(22): 220501. doi: 10.7498/aps.63.220501
[9]	王亚奇, 王静, 杨海滨. 基于复杂网络理论的微博用户关系网络演化模型研究. 物理学报, 2014, 63(20): 208902. doi: 10.7498/aps.63.208902
[10]	段东立, 战仁军. 基于相继故障信息的网络节点重要度演化机理分析. 物理学报, 2014, 63(6): 068902. doi: 10.7498/aps.63.068902
[11]	刘树新, 季新生, 刘彩霞, 郭虹. 一种信息传播促进网络增长的网络演化模型. 物理学报, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902
[12]	胡枫, 赵海兴, 何佳倍, 李发旭, 李淑玲, 张子柯. 基于超图结构的科研合作网络演化模型. 物理学报, 2013, 62(19): 198901. doi: 10.7498/aps.62.198901
[13]	张聪, 沈惠璋, 李峰, 杨何群. 复杂网络中社团结构发现的多分辨率密度模块度. 物理学报, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
[14]	周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
[15]	邢长明, 刘方爱. 基于Sierpinski分形垫的确定性复杂网络演化模型研究. 物理学报, 2010, 59(3): 1608-1614. doi: 10.7498/aps.59.1608
[16]	王光增, 曹一家, 包哲静, 韩祯祥. 一种新型电力网络局域世界演化模型. 物理学报, 2009, 58(6): 3597-3602. doi: 10.7498/aps.58.3597
[17]	欧阳敏, 费奇, 余明晖. 基于复杂网络的灾害蔓延模型评价及改进. 物理学报, 2008, 57(11): 6763-6770. doi: 10.7498/aps.57.6763
[18]	林海, 吴晨旭. 基于遗传算法的重复囚徒困境博弈策略在复杂网络中的演化. 物理学报, 2007, 56(8): 4313-4318. doi: 10.7498/aps.56.4313
[19]	李季, 汪秉宏, 蒋品群, 周涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
[20]	郭进利. 供应链型网络中双幂律分布模型. 物理学报, 2006, 55(8): 3916-3921. doi: 10.7498/aps.55.3916

计量

文章访问数: 13993
PDF下载量: 3531
被引次数: 0

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

搜索

留言板