社团结构下信息网络若干特性研究
|
摘要
本文通过分析谣言短信传播的特点以及方式,把谣言短信的传播过程抽象成一个网络的生长过程。根据谣言短信传播的特点,以星形网络表示初始网络,在局域世界中选择新增节点的连接节点。局域世界的选取,采用了依据节点之间的网络路径值作为选取局域世界的原则。给出了生成谣言短信传播网络模型的算法,并且通过理论推导说明网络模型的度分布为幂律函数,模拟了网络节点的度分布、聚类系数和平均路径长度,通过GN算法对模型的社团结构进行分析,发现谣言短信传播网络具有明显的社团结构特征。仿真结果表明,谣言短信传播网络同时具有具有无标度特性、小世界特性以及明显的社团结构特征。
社团结构是反映网络结构整体性质的重要特征,网络的稳定性和健壮性在很大程度上取决于网络的社团结构特征。通过在具有不同的社团结构的信息传播网络模型上,对网络进行相继故障仿真,研究社团结构对信息传播网络稳定性影响。为此,设计开发了复杂网络综合仿真平台。利用复杂网络仿真平台,改变信息网络的社团结构强度,从而形成不同社团结构强度的信息网络。再利用改进的节点动态相继故障模型,对不同社团结构强度信息网络进行故障传播过程模拟;研究网络在不同的社团结构强度下,网络的稳定性和健壮性。仿真结果表明,网络的稳定性和健壮性是随着社团结构之间链接紧密程度的增加,先减弱再增强,存在一个与网络规模、容差系数有关的临界值。
最后,对研究工作做出了总结,并对课题的进一步研究进行了展望。
The characteristic and the way of rumor short message propagation are analyzed in view of the course of the rumor short message propagation as networks growth. The initial network is star like, and the link nodes connected with the new added one are chosen in the local world. The selection of the local world depends on the value of network path between nodes. Model generating algorithm of rumor short message propagation networks is suggested. Degree distribution, clustering coefficient along with average path length are analyzed. Simulation result shows that the rumor short message propagation network has both small-world and scale-free property with clear community structure.
Community structure not only reflects the important characteristics of overall structure properties of networks, but also it determines the stability and the robustness to a large extent. As a result, on the different network modes of community structures’message propagation, network casecade failure simulation has been carried out to study community structures which affect the stability of the message propagation network. To this end, the complex network simulation platform has been designed. By the platform, the different community structures network are generated. On the base of improved node dynamic cascading failure model, Cascading failure on the message propagation networks was investigated. To the different density values of community structures, the stability of networks was explored, respectively. Simulation result shows that the stability of networks weakened at first and then enhanced with the increase of the community structures density value, and there was threshold value which was related with the scale and capacity coefficient of networks.
Finally, a summary about this theory is given, and a further prospect about this theme is offered.
社团结构是反映网络结构整体性质的重要特征,网络的稳定性和健壮性在很大程度上取决于网络的社团结构特征。通过在具有不同的社团结构的信息传播网络模型上,对网络进行相继故障仿真,研究社团结构对信息传播网络稳定性影响。为此,设计开发了复杂网络综合仿真平台。利用复杂网络仿真平台,改变信息网络的社团结构强度,从而形成不同社团结构强度的信息网络。再利用改进的节点动态相继故障模型,对不同社团结构强度信息网络进行故障传播过程模拟;研究网络在不同的社团结构强度下,网络的稳定性和健壮性。仿真结果表明,网络的稳定性和健壮性是随着社团结构之间链接紧密程度的增加,先减弱再增强,存在一个与网络规模、容差系数有关的临界值。
最后,对研究工作做出了总结,并对课题的进一步研究进行了展望。
The characteristic and the way of rumor short message propagation are analyzed in view of the course of the rumor short message propagation as networks growth. The initial network is star like, and the link nodes connected with the new added one are chosen in the local world. The selection of the local world depends on the value of network path between nodes. Model generating algorithm of rumor short message propagation networks is suggested. Degree distribution, clustering coefficient along with average path length are analyzed. Simulation result shows that the rumor short message propagation network has both small-world and scale-free property with clear community structure.
Community structure not only reflects the important characteristics of overall structure properties of networks, but also it determines the stability and the robustness to a large extent. As a result, on the different network modes of community structures’message propagation, network casecade failure simulation has been carried out to study community structures which affect the stability of the message propagation network. To this end, the complex network simulation platform has been designed. By the platform, the different community structures network are generated. On the base of improved node dynamic cascading failure model, Cascading failure on the message propagation networks was investigated. To the different density values of community structures, the stability of networks was explored, respectively. Simulation result shows that the stability of networks weakened at first and then enhanced with the increase of the community structures density value, and there was threshold value which was related with the scale and capacity coefficient of networks.
Finally, a summary about this theory is given, and a further prospect about this theme is offered.
引文
[1] Albert R,Barabási A L.Statistical mechanics of complex networks Rev.Mod.Phys.,2002,74:47-97.
[2] Evans T S. Complex networks. Arxiv:cond-mat:0405123.
[3] Newman M E J. The structure and function of complex networks. SIAM Review, 2003, 45:167-256.
[4] Albert R, Barabási A L. Statistical mechanics of complex networks. Rev Mod Phys, 2002, 74:47-97.
[5] Newman M E J, Watts D J. Scaling and Percolation in the Small-World Network Model. Phys. Rev. E, 1999, 60: 7332-7342.
[6] Adamic A L, Adar E. Friends and neighbors on the webs. Social Networks, 2003, 25(3):211-230.
[7] Newman M E J. The structure of scientific collaboration networks. Proc. Natl Acad. Sci. USA. 2001, 98:404-409.
[8] Williams, R. J., Martinez, N. D. Simple rules yield complex food webs. Nature, 2000, 404:180-183.
[9] Ebel H, Mielsch L I, Borbholdt S. Scale-free topology of e-mail networks. Phys. Rev. E. 2002, 66:035103.
[10] Liljeros F, Rdling C R, Amaral L A N. et al. The Web of human sexual contact. Nature, 2001, 411:907-908.
[11] Sen P, Dasgupta P, Chatterjee A, et al. Small-world properties of the Indian railway networks. Phys. Rev E, 2003, 67:036106.
[12] Newman M E J, Stephanie Forrest, Justin Balthrop. Email networks and the spread of computer viruses. Phys. Rev E, 2002, 66:035101.
[13] Watts D J,Small Words: The dynamic of Networks between Order and Randomness, Princeton University Press, Princeton, NJ, 1999.
[14] Watts D J,Six Degrees: The Science of a Connected Age,Norton,New York,2003.
[15] Barabási A L. Linked: The New Science of Networks,Perseus,Cambridge,2002.
[16] Buehanan M,Nexus: Small Worlds and the Ground Breaking Science of Networks,Norton,New York,2002.
[17] Strogatz S H., SYNC: The Emerging Science of Spontaneous Order. New York: HyPerion, 2003.
[18] Erdos P. and Renyi A., on random graphs, Publications Mathematies, 1959, 6: 290.
[19] Watts, D. J. and Strogatz, S. H. Collective dynamics of“small-words”networks. Nature 1998, 393: 440-442.
[20] Barabási, A-L., Albert, R, Emergence of scaling in random networks, Science 1999, 286:509-512.
[21]李洁,李仕雄.复杂网络研究及其在电力系统中的应用.电力学报,2008, 23(4):279-282.
[22]倪向萍,梅生伟.基于复杂网络社团结构理论的同调等值算法.电力系统自动化,2008,23(7):10-13.
[23]袁韶谦,赵海,张昕.李超. Internet拓扑的社团结构分析.复杂系统与复杂性科学,2007,4(3):17-27.
[24]杨波.复杂社会网络的结构测度与模型研究:[博士论文].上海:上海交通大学管理科学与工程,2007.
[25]宣照国,苗静,党延忠,刘建国.科研领域关联网络的社团结构分析.上海理工大学学报,2008,20(3):249-252.
[26]李晓佳,张鹏,狄增如,樊瑛.复杂网络中的社团结构.第四届全国网络科学学术论坛暨研究生暑期学校论文集, 2008.
[27]程学旗.信息网络拓扑结构与内容相关性研究:[博士论文].北京:中国科学院计算技术研究所,2006.
[28]欧阳敏,费奇,余明辉,栾恩杰.复杂网络的功效性与脆弱性研究综述.计算机科学,2008,35(6):1-4.
[29]史明江,李翔,汪小帆.基于复杂网络理论的即时通讯病毒研究.计算机工程与应用,2006,11:110-115.
[30]山秀明,刘旸,等. P2P应用系统用户共享行为的复杂网络模型.计算机应用研究,2008,25(6):1853-1855.
[31]王林,戴冠中.基于复杂网络社区结构的论坛热点主题发现.计算机工程,2008,34(11):214-216.
[32]胡海波,王科,徐玲,汪小帆.基于复杂网络理论的在线社会网络分析.复杂系统与复杂性科学,2008,5(2):1-14.
[33]杨洪勇,李凯旋,林娜.基于复杂网络的学生交流网络模型.控制工程,2008,15(4):427-439.
[34]胡海波,王林.幂律分布研究简史.物理,2005,34(12):589-896.
[35]汪小帆,李翔,陈关荣.复杂网络理论及其应用.清华大学出版社,2006.
[36] Albert R, Barabasi A L, Jeong H. Mean-field theory for scale-free random networks. Physica A, 1999, 272:173-187.
[37]郭雷,许晓明等.复杂网络.上海教育科技出版社,2006.
[38] Girvan and M.E.J. Newman, Community structures in social and biological, Proc. Nat .Acad. Sci. USA99, 2002:7821-7826.
[39] Flake G W, Lawrence S R, Gile C L, Self-organization and identification of web communities [J]. IEEE Computer, 2002, 35(3):66-71.
[40] Adamic A L, Adar E. Friends and neighbors on the webs. Social Networks, 2003, 25(3):211-230.
[41] Williams, R. J., Martinez, N. D. Simple rules yield complex food webs. Nature, 2000, 404:180-183.
[42] Onnela J P, Chakraborti A., Kaski K, et al. Dynamics of makers correlations: Taxonomy and portfolio analysis. Physical Review E, 2003, 68: 056110.
[43]鲁宗相.电网复杂性及大停电事故的可靠性研究.电力系统自动化, 2005, 29(12): 93-97.
[44] Barabási A-L, Albert R, Jeong H. Scale-free characteristics of random networks: the topology of the World Wide Web. Physica A, 2000, 281:69-77.
[45] Newman M E J, Girvan M. Finding and Evaluating Community Structure in Networks. Physical Review E, 2004, 69(2):26-113.
[46] Kernighan B W, L in S.A efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970, 49(2):291-307.
[47] Fiedler M. Algebraic connectivity of graphs. Czech Math J, 1973, 23(98): 298-305.
[48] Pothen A, Simon H, Lou K-P. Partitioning sparse matrices with eigenvectors of graphs. SIAM J Matrix Anal App l, 1990, 11(3):430-452.
[49] Girvan M, Newman M E J. Community structure in social and biological networks. Proc Natl Acad Sci, 2001, 99(12):7821-7826.
[50] Tyler J, Wilkins on D, Huberman B. Email as spectroscopy: automated discovery ofcommunity structure within organizations. International Conference on Communities and Technologie. 2003:81-96.
[51] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in net works. Proc Natl Acad Sci, 2004, 101(9):2658-2663.
[52] Tsuchiura H, Ogata M, Tanaka Y, et al. Electronic states around a vortex core in high-Tc superconductors based on the t-J model. Phys Rev B, 2003, 68(1): 012509
[53] Zhou H. Distance, dissimilarity index and net work community structure. Phys Rev E, 2003, 67(6):061901.
[54] Fortunato S, Latora V, Marchiori M. A method t o find community structures based on information centrality. Phys Rev E, 2004, 70(5):056104.
[55] Latora V, Marchiori M. Efficient behavior of s mall-world networks. Phys Rev Lett, 2002, 87(19):198701.
[56] Duch J, Arenas A. Community detection in complex net works using extreme optmization. Arxiv: cond2 mat /0501368, 2005.
[57] Newman M E J. Fast algorithm for detecting community structure in net works. Phys Rev E, 2004, 69(6):066133.
[58] Motter A E, Nishikawa T, Lai Y C, Casade-based attacks on complex networks. Phys. Rev. E, 2002, 66:065102.
[59]许丹,李翔,汪小帆.复杂网络病毒传播的局域控制研究.物理学报,2007,56(3):1313-1317.
[60]王健,刘衍珩,徐沛娟,等.田大新;Internet相继故障分析与控制, 2006全国复杂网络学术会议论文集,2006.
[61]倪向萍,梅生伟,张雪敏.基于复杂网络理论的输电线路脆弱度评估方法.电力系统自动化,2007,32(4):1-5.
[62]丁明,韩平平.小世界电网的连锁故障传播机理分析.电力系统自动化,2007,31(18):6-9.
[63]丁道齐.用复杂网络理论分析电网连锁性大停电事故机理.中国电力,2007,40(11):25-30.
[64] Wang X F, Xu J. Cascading failures in coupled map lattices. Physical Review E, 2004, 70: 056113.
[65] Xu J, Wang X F. Cascading failures in scale-free coupled map lattices. Physica A, 2005,349:685-692.
[66] Crucitti P, Latora V, Marchiori M. Model for cascading failures in complex networks. Phys. Rev. E, 2004, 69:045104.
[67]李京,吴斌,杨鑫,等.基于复杂网络方法的奥运数据分析.复杂系统与复杂性科学,2008,5(2):80-87.
[68] Wouter D N,Andrej M,Vladimir B. Exploratory Social Network Analysis with Pajek. Cambridge University Press, 2005:3-6
[2] Evans T S. Complex networks. Arxiv:cond-mat:0405123.
[3] Newman M E J. The structure and function of complex networks. SIAM Review, 2003, 45:167-256.
[4] Albert R, Barabási A L. Statistical mechanics of complex networks. Rev Mod Phys, 2002, 74:47-97.
[5] Newman M E J, Watts D J. Scaling and Percolation in the Small-World Network Model. Phys. Rev. E, 1999, 60: 7332-7342.
[6] Adamic A L, Adar E. Friends and neighbors on the webs. Social Networks, 2003, 25(3):211-230.
[7] Newman M E J. The structure of scientific collaboration networks. Proc. Natl Acad. Sci. USA. 2001, 98:404-409.
[8] Williams, R. J., Martinez, N. D. Simple rules yield complex food webs. Nature, 2000, 404:180-183.
[9] Ebel H, Mielsch L I, Borbholdt S. Scale-free topology of e-mail networks. Phys. Rev. E. 2002, 66:035103.
[10] Liljeros F, Rdling C R, Amaral L A N. et al. The Web of human sexual contact. Nature, 2001, 411:907-908.
[11] Sen P, Dasgupta P, Chatterjee A, et al. Small-world properties of the Indian railway networks. Phys. Rev E, 2003, 67:036106.
[12] Newman M E J, Stephanie Forrest, Justin Balthrop. Email networks and the spread of computer viruses. Phys. Rev E, 2002, 66:035101.
[13] Watts D J,Small Words: The dynamic of Networks between Order and Randomness, Princeton University Press, Princeton, NJ, 1999.
[14] Watts D J,Six Degrees: The Science of a Connected Age,Norton,New York,2003.
[15] Barabási A L. Linked: The New Science of Networks,Perseus,Cambridge,2002.
[16] Buehanan M,Nexus: Small Worlds and the Ground Breaking Science of Networks,Norton,New York,2002.
[17] Strogatz S H., SYNC: The Emerging Science of Spontaneous Order. New York: HyPerion, 2003.
[18] Erdos P. and Renyi A., on random graphs, Publications Mathematies, 1959, 6: 290.
[19] Watts, D. J. and Strogatz, S. H. Collective dynamics of“small-words”networks. Nature 1998, 393: 440-442.
[20] Barabási, A-L., Albert, R, Emergence of scaling in random networks, Science 1999, 286:509-512.
[21]李洁,李仕雄.复杂网络研究及其在电力系统中的应用.电力学报,2008, 23(4):279-282.
[22]倪向萍,梅生伟.基于复杂网络社团结构理论的同调等值算法.电力系统自动化,2008,23(7):10-13.
[23]袁韶谦,赵海,张昕.李超. Internet拓扑的社团结构分析.复杂系统与复杂性科学,2007,4(3):17-27.
[24]杨波.复杂社会网络的结构测度与模型研究:[博士论文].上海:上海交通大学管理科学与工程,2007.
[25]宣照国,苗静,党延忠,刘建国.科研领域关联网络的社团结构分析.上海理工大学学报,2008,20(3):249-252.
[26]李晓佳,张鹏,狄增如,樊瑛.复杂网络中的社团结构.第四届全国网络科学学术论坛暨研究生暑期学校论文集, 2008.
[27]程学旗.信息网络拓扑结构与内容相关性研究:[博士论文].北京:中国科学院计算技术研究所,2006.
[28]欧阳敏,费奇,余明辉,栾恩杰.复杂网络的功效性与脆弱性研究综述.计算机科学,2008,35(6):1-4.
[29]史明江,李翔,汪小帆.基于复杂网络理论的即时通讯病毒研究.计算机工程与应用,2006,11:110-115.
[30]山秀明,刘旸,等. P2P应用系统用户共享行为的复杂网络模型.计算机应用研究,2008,25(6):1853-1855.
[31]王林,戴冠中.基于复杂网络社区结构的论坛热点主题发现.计算机工程,2008,34(11):214-216.
[32]胡海波,王科,徐玲,汪小帆.基于复杂网络理论的在线社会网络分析.复杂系统与复杂性科学,2008,5(2):1-14.
[33]杨洪勇,李凯旋,林娜.基于复杂网络的学生交流网络模型.控制工程,2008,15(4):427-439.
[34]胡海波,王林.幂律分布研究简史.物理,2005,34(12):589-896.
[35]汪小帆,李翔,陈关荣.复杂网络理论及其应用.清华大学出版社,2006.
[36] Albert R, Barabasi A L, Jeong H. Mean-field theory for scale-free random networks. Physica A, 1999, 272:173-187.
[37]郭雷,许晓明等.复杂网络.上海教育科技出版社,2006.
[38] Girvan and M.E.J. Newman, Community structures in social and biological, Proc. Nat .Acad. Sci. USA99, 2002:7821-7826.
[39] Flake G W, Lawrence S R, Gile C L, Self-organization and identification of web communities [J]. IEEE Computer, 2002, 35(3):66-71.
[40] Adamic A L, Adar E. Friends and neighbors on the webs. Social Networks, 2003, 25(3):211-230.
[41] Williams, R. J., Martinez, N. D. Simple rules yield complex food webs. Nature, 2000, 404:180-183.
[42] Onnela J P, Chakraborti A., Kaski K, et al. Dynamics of makers correlations: Taxonomy and portfolio analysis. Physical Review E, 2003, 68: 056110.
[43]鲁宗相.电网复杂性及大停电事故的可靠性研究.电力系统自动化, 2005, 29(12): 93-97.
[44] Barabási A-L, Albert R, Jeong H. Scale-free characteristics of random networks: the topology of the World Wide Web. Physica A, 2000, 281:69-77.
[45] Newman M E J, Girvan M. Finding and Evaluating Community Structure in Networks. Physical Review E, 2004, 69(2):26-113.
[46] Kernighan B W, L in S.A efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970, 49(2):291-307.
[47] Fiedler M. Algebraic connectivity of graphs. Czech Math J, 1973, 23(98): 298-305.
[48] Pothen A, Simon H, Lou K-P. Partitioning sparse matrices with eigenvectors of graphs. SIAM J Matrix Anal App l, 1990, 11(3):430-452.
[49] Girvan M, Newman M E J. Community structure in social and biological networks. Proc Natl Acad Sci, 2001, 99(12):7821-7826.
[50] Tyler J, Wilkins on D, Huberman B. Email as spectroscopy: automated discovery ofcommunity structure within organizations. International Conference on Communities and Technologie. 2003:81-96.
[51] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in net works. Proc Natl Acad Sci, 2004, 101(9):2658-2663.
[52] Tsuchiura H, Ogata M, Tanaka Y, et al. Electronic states around a vortex core in high-Tc superconductors based on the t-J model. Phys Rev B, 2003, 68(1): 012509
[53] Zhou H. Distance, dissimilarity index and net work community structure. Phys Rev E, 2003, 67(6):061901.
[54] Fortunato S, Latora V, Marchiori M. A method t o find community structures based on information centrality. Phys Rev E, 2004, 70(5):056104.
[55] Latora V, Marchiori M. Efficient behavior of s mall-world networks. Phys Rev Lett, 2002, 87(19):198701.
[56] Duch J, Arenas A. Community detection in complex net works using extreme optmization. Arxiv: cond2 mat /0501368, 2005.
[57] Newman M E J. Fast algorithm for detecting community structure in net works. Phys Rev E, 2004, 69(6):066133.
[58] Motter A E, Nishikawa T, Lai Y C, Casade-based attacks on complex networks. Phys. Rev. E, 2002, 66:065102.
[59]许丹,李翔,汪小帆.复杂网络病毒传播的局域控制研究.物理学报,2007,56(3):1313-1317.
[60]王健,刘衍珩,徐沛娟,等.田大新;Internet相继故障分析与控制, 2006全国复杂网络学术会议论文集,2006.
[61]倪向萍,梅生伟,张雪敏.基于复杂网络理论的输电线路脆弱度评估方法.电力系统自动化,2007,32(4):1-5.
[62]丁明,韩平平.小世界电网的连锁故障传播机理分析.电力系统自动化,2007,31(18):6-9.
[63]丁道齐.用复杂网络理论分析电网连锁性大停电事故机理.中国电力,2007,40(11):25-30.
[64] Wang X F, Xu J. Cascading failures in coupled map lattices. Physical Review E, 2004, 70: 056113.
[65] Xu J, Wang X F. Cascading failures in scale-free coupled map lattices. Physica A, 2005,349:685-692.
[66] Crucitti P, Latora V, Marchiori M. Model for cascading failures in complex networks. Phys. Rev. E, 2004, 69:045104.
[67]李京,吴斌,杨鑫,等.基于复杂网络方法的奥运数据分析.复杂系统与复杂性科学,2008,5(2):80-87.
[68] Wouter D N,Andrej M,Vladimir B. Exploratory Social Network Analysis with Pajek. Cambridge University Press, 2005:3-6