复杂网络演化与软件平台研究
|
摘要
复杂网络是一个新兴的跨学科研究领域,它描述了自然及社会中的一系列系统。在过去的几年中,复杂网络的研究得到了迅速的发展,已经遍及各个学科领域,例如物理学,社会科学、生物学等等。
本文的工作可以分为三部分:第一部分介绍了复杂网络的发展历程及其在社会生活中重要意义,总结了复杂网络的基础理论知识。第二部分介绍了几种无标度网络模型,通过仿真,给出了每种网络模型的度分布并且分析了各种网络模型中各个参数对网络演化的影响;在分析了这些无标度网络模型的基础上,联系现实世界中的网络,提出了一个改进的网络模型,该模型与以往的模型相比有以下三点改进:第一,网络内部在每个时间步有一个随机数目的连线被删除;第二,新加入的结点在选择旧结点进行择优连接时,不仅考虑了结点的度,还考虑了结点的权值,也称竞争力;第三,两节点只有在他们之间的直线距离小于某个给定值的时候才产生连线。通过仿真给出改进网络模型的度分布,可以看到改进的网络模型同样具有无标度网络的特性。本文的另一个研究工作放在第三部分,在这一部分里,以面向对象程序设计的思想在Visual C++编译环境下设计并实现了“复杂网络演化软件平台”,它既可以根据不同的输入参数生成不同的网络模型的拓扑结构,也可以分析给定网络的特性,例如度分布、鲁棒性和脆弱性。
Complex network is a new interdisciplinary research field, which describes a wide range of systems in nature and society. Over the past few years, the research on complex network has been developed rapidly and extended many science fields, such as physics, social science, biology, and so on.
This paper can be divided into three sections. Section I introduces the development process of complex networks and its importance in social life, and then the basic theories of complex networks are summarized. In section II, several scale-free network models are introduced, then their degree distributions are described through simulation, and the impact of the various in each model on its evolution is analyzed. After analyzing these models and referring the real-world networks, an improved network model is proposed. There are three improvements in the improved network model: Firstly, there are a random amount of lines are deleted after every interval. Secondly, the priority of an old node connected by the new node are decided not only by its degree, but also by its weight, also called competence. Thirdly, the creation of a new line must satisfy the situation that the distance between the new node and the old node under a given value. The degree distribution of this model is given through situation finally. It is found that the improved network model has the properties of the scale-free network. Another research of this paper is described in section III. In this section,a software platform of complex networks is designed with Visual C++ according to the thought of object-oriented programming. It can not only create topological structure graph of networks according to different parameters, but also can analyze the properties of the given network, such as degree distribution, robustness and frangibility.
本文的工作可以分为三部分:第一部分介绍了复杂网络的发展历程及其在社会生活中重要意义,总结了复杂网络的基础理论知识。第二部分介绍了几种无标度网络模型,通过仿真,给出了每种网络模型的度分布并且分析了各种网络模型中各个参数对网络演化的影响;在分析了这些无标度网络模型的基础上,联系现实世界中的网络,提出了一个改进的网络模型,该模型与以往的模型相比有以下三点改进:第一,网络内部在每个时间步有一个随机数目的连线被删除;第二,新加入的结点在选择旧结点进行择优连接时,不仅考虑了结点的度,还考虑了结点的权值,也称竞争力;第三,两节点只有在他们之间的直线距离小于某个给定值的时候才产生连线。通过仿真给出改进网络模型的度分布,可以看到改进的网络模型同样具有无标度网络的特性。本文的另一个研究工作放在第三部分,在这一部分里,以面向对象程序设计的思想在Visual C++编译环境下设计并实现了“复杂网络演化软件平台”,它既可以根据不同的输入参数生成不同的网络模型的拓扑结构,也可以分析给定网络的特性,例如度分布、鲁棒性和脆弱性。
Complex network is a new interdisciplinary research field, which describes a wide range of systems in nature and society. Over the past few years, the research on complex network has been developed rapidly and extended many science fields, such as physics, social science, biology, and so on.
This paper can be divided into three sections. Section I introduces the development process of complex networks and its importance in social life, and then the basic theories of complex networks are summarized. In section II, several scale-free network models are introduced, then their degree distributions are described through simulation, and the impact of the various in each model on its evolution is analyzed. After analyzing these models and referring the real-world networks, an improved network model is proposed. There are three improvements in the improved network model: Firstly, there are a random amount of lines are deleted after every interval. Secondly, the priority of an old node connected by the new node are decided not only by its degree, but also by its weight, also called competence. Thirdly, the creation of a new line must satisfy the situation that the distance between the new node and the old node under a given value. The degree distribution of this model is given through situation finally. It is found that the improved network model has the properties of the scale-free network. Another research of this paper is described in section III. In this section,a software platform of complex networks is designed with Visual C++ according to the thought of object-oriented programming. It can not only create topological structure graph of networks according to different parameters, but also can analyze the properties of the given network, such as degree distribution, robustness and frangibility.
引文
[1] M E J Newman. The structure of scientific collaboration networks. PNAS,2001,98:404-409
[2] M Faloutsos,P Faloutsos,C Faloutsos. On Power-law relationships of the Internet topology. Comp. Comm. Rev. 1999,29:251-260
[3] R Albert,H Jeong,A L Barabási. Diameter of the World Wide Web. Nature,1999,401:130-131
[4] T Xu,R Chen,Y He,et al. Complex network properties of Chinese power grid. International Journal of Modern physics B,2004,18(17-19):2599-2603
[5] R Albert,I Albert,G L Nakarado. Structural vulnerability of the North American Power grid. Physical Review E,2004,69:025103(R)
[6] R Kinney,P Crucitti,R Albert,et al. Modeling cascading failures in the North American power grid. The European Physical Journal B,2005,46:101-107
[7] R Guimera,S Mossa,A Turtschi,et al. The worldwide air transportation network:Anomalous centrality,community structure and cities? global roles. PNAS,2005,102(22):7794-7799
[8] R Guimera,L A N Amaral. Modeling the worldwide airport network. The European Physical Journal B,2004,38:381-385
[9]汪小帆,李翔,陈光荣.复杂网络及其应用.清华大学出版社.2006
[10] P Erd?s,A Rényi. On random graphs. Publ. Math.,1959,6:290-296
[11] P Erd?s,Rényi A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci.,1960,5:17-60
[12] D J Watts,S H Strogatz. Collective dynamics of ?small-world? networks. Nature,1998,393(6684):440-442
[13] A Broder,R Kumar,F Maghoul,et al. Graph structure of the web. Proceedings of the 9th WWW Conference. Amsterdam. 2000,309:15-19
[14] M E J Newman,Forrest Stephanie,Justin Balthrop. Email networks and the spread of computer viruses. Physical Review E,2002,66:035101
[15] J Podani,Z N Oltvai,H Jeong,et al. Comparable system-level organization of Archaea and Eukaryotes. Nature,2001,29:54-56
[16] A L Barabási,R Albert. Emergence of scaling in random networks. Science,1999,286(5439):509-512
[17] R Pastor-Satoras,A Vespignani. Immunization of complex networks. Physical Review E,2002,65:036104
[18] Z Dezs?,A L Barabási. Halting viruses in scale-free networks. Physical Review E,2002,65:055103(R)
[19] L A Meyers,B Pourbohloul,M E J Newman,et al. Network theory and SARS:Predicting outbreak diversity. Journal of Theoretical Biology,2005,232:71-81
[20] D H Zanette. Dynamics of rumor propagation on small–world networks. Physical Review E,2002,65:041908
[21] J Wang,P D Wilde. Properties of evolving e-mail networks. Physical Review E,2004,70:066121
[22] J Balthrop,S Forest,M E J Newman,et al. Technological networks and the spread of computer viruses. Science,2004,304:527-529
[23] A L Barabási,E Bonabeau. Scale-Free Networks. Scientific American,2003,288: 60-69
[24] C Schulze. Advertising in the Sznajd marketing model. International Journal of Modem Physics C,2003,14(1):95-98
[25] S Luding. Granular media:Information propagation. Nature,2005,435:159-160
[26] P S Dodds,D J Watts,C F Sabel. Information exchange and the robustness of organizational networks. PNAS,2003,100(21):12516-12521
[27] B VersPagen,G Duysters. The small worlds of strategic technology alliances. Technovation,2004,24:563-571
[28] J Park,M E J Newman. A network-based ranking system for US co1lege football. Journal of Statistical Mechanics:Theory and Experiment,2005:P10014
[29] A S Elgazzar. Applications of small-world networks to some socio-economic system. Physics A,2003,324:402-407
[30] Watts D J, The "new" science of networks, Annual Review of Sociology, 2004, 30:243-270
[31]Wang X F, Complex networks: topology, dynamics and synchronization, International Journal of Bifurcation and Chaos, 2002, 12:885-916
[32]方锦清,汪小帆.刘曾荣,略论复杂性问题和作线性复杂网络系统的研究,科技导报,2004, 2:9-12
[33] Scott J, Social network analysis: a handbook, London, 2000
[34] Jeong H, Tombor B, Albert R, et al., The large-scale organization of metabolic networks,Nature, 2000, 407:651-654
[35] Wang X.F., Chen G.,“Complex Networks: Small-world, scale-free andbeyond.”IEEE Circuits & Systems Magazine, 2003, 3(1):6-20
[36] Newman M.E.J., Watts D.J.,“Renormalization group analysis of the small-world network model”, Phys. Lett. A, 1999, 263:341-346
[37] A.-L. Barabasi, Linked: The New Science of Networks, (Perseus, Cambridge, MA,2002)
[38] A. Fronczak, J. A. Holyst, M. Jedynak and J. Sienkiewicz, Physica A 316, 688 (2002)
[39] K.-1. Goh, E. Oh, H. Jeong, B. Kahng and D. Kim, Proc. Nall. Acad. Sci. USA 99,12583 (2002)
[40] H. Jeong, Z. Neda and A.-L. Barabasi, Europhys. Lett. 61, 567 (2003)
[41] T. Zhou, B.-H. Wang, Chin. Phys. Lett. 22, 1072 (2005)
[42] G. Caldarelli, A. Capocci, P. De Los Rios and M. A. Muiioz, Phys. Rev. Lett. 89, 258702 (2002)
[43] S. N. tsev and J. F. F. Mendes, Europhys. Lett. 52, 33 (2000)
[44] P. Holme and B. J. Kim, Phys. Rev. E 65, 026107 (2002)
[45] R. Albert and A. L. Barabási, Rev. Mod. Phys. 74, 47 (2002)
[46] Bailey N T J. The Mathematical Theory of Infectious Diseases and Its Applications. New York:Hafner,1975
[47] Anderson R M,May R M. Infectious Diseases in Humans.Oxford:Oxford University Press,1992
[48] Diekmann O, Heesterbeek J A P. Mathematical Epidemiology of Infectous Disease:Model Building,Analysis and Interpretation.New York:John Wiley & Son publisher,2000
[49]车宏安,顾基发.无标度网络及其系统科学意义[J].系统工程理论与实践. 2004,(4)
[50] A.-L.barabasi, R. Albert, and H. Jeong, Mean-field theory for scale-free random networks, Physica A,272(1999), 173-187
[51] Li X, Chen G R. A local-world evolving network model [ J]. PhysicaA: Statistical Mechanics and Its Applications, 2003, 328(1-2):274~286
[52]陈禹,方美琪,宗骁等. BA模型的三种扩展.系统工程学报,2005,20(2): 120-127
[53] Albert R. and Barabasi A.-L., Statistical mechanics of complex networks, Rev. Mod. Phys. 74, 2002 ,47-97
[54] Bollobas B., Mathematical results on scale-free random graphs, see Bornholdt S. and Schuster H. G. (eds), Handbook of Graphs and Networks–From the Genome to Internet, Wiley--VCH, 2002, 1-34
[55] Newman M. E. J., The Structure and function of complex networks, SIAM Rev. 45, 2003, 167-256
[56] Albert R. and Barabasi A.-L., Topology of evolving networks:local events and universality, Phys. Rev. Lett. 85, 2000, 5234-5237
[57] Shi D. H., Liu L. M., Zhu X., and Zhou H. J., Degree distributions of evolving networks, Europhys. Lett. 76(4), 2006, 10315-2
[58] Klemm K. and Eguiluz, V. M., Growing scale-free networks with small-world behavior, Phys. Rev. E 65. 2002, 057102
[59]吴金闪,狄增如,物理学进展,Vol24,No.1(2004)
[60]吕凤翥.C++语言基础教程(第2版).北京:清华大学出版社,2008
[61]刘放路.Visual C++与面向对象程序设计教程.北京:高等教育出版社,2001
[62]林锐,韩永泉.高质量程序设计指南—C/C++语言.3.北京:电子工业出版社,2007
[63]孙鑫,余安萍.VC++深入详解.北京:电子工业出版社,2009
[64] Booch G, Rumbaugh J, Jacobson I, et al. UML用户指南.北京:人民邮电出版社.2006
[2] M Faloutsos,P Faloutsos,C Faloutsos. On Power-law relationships of the Internet topology. Comp. Comm. Rev. 1999,29:251-260
[3] R Albert,H Jeong,A L Barabási. Diameter of the World Wide Web. Nature,1999,401:130-131
[4] T Xu,R Chen,Y He,et al. Complex network properties of Chinese power grid. International Journal of Modern physics B,2004,18(17-19):2599-2603
[5] R Albert,I Albert,G L Nakarado. Structural vulnerability of the North American Power grid. Physical Review E,2004,69:025103(R)
[6] R Kinney,P Crucitti,R Albert,et al. Modeling cascading failures in the North American power grid. The European Physical Journal B,2005,46:101-107
[7] R Guimera,S Mossa,A Turtschi,et al. The worldwide air transportation network:Anomalous centrality,community structure and cities? global roles. PNAS,2005,102(22):7794-7799
[8] R Guimera,L A N Amaral. Modeling the worldwide airport network. The European Physical Journal B,2004,38:381-385
[9]汪小帆,李翔,陈光荣.复杂网络及其应用.清华大学出版社.2006
[10] P Erd?s,A Rényi. On random graphs. Publ. Math.,1959,6:290-296
[11] P Erd?s,Rényi A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci.,1960,5:17-60
[12] D J Watts,S H Strogatz. Collective dynamics of ?small-world? networks. Nature,1998,393(6684):440-442
[13] A Broder,R Kumar,F Maghoul,et al. Graph structure of the web. Proceedings of the 9th WWW Conference. Amsterdam. 2000,309:15-19
[14] M E J Newman,Forrest Stephanie,Justin Balthrop. Email networks and the spread of computer viruses. Physical Review E,2002,66:035101
[15] J Podani,Z N Oltvai,H Jeong,et al. Comparable system-level organization of Archaea and Eukaryotes. Nature,2001,29:54-56
[16] A L Barabási,R Albert. Emergence of scaling in random networks. Science,1999,286(5439):509-512
[17] R Pastor-Satoras,A Vespignani. Immunization of complex networks. Physical Review E,2002,65:036104
[18] Z Dezs?,A L Barabási. Halting viruses in scale-free networks. Physical Review E,2002,65:055103(R)
[19] L A Meyers,B Pourbohloul,M E J Newman,et al. Network theory and SARS:Predicting outbreak diversity. Journal of Theoretical Biology,2005,232:71-81
[20] D H Zanette. Dynamics of rumor propagation on small–world networks. Physical Review E,2002,65:041908
[21] J Wang,P D Wilde. Properties of evolving e-mail networks. Physical Review E,2004,70:066121
[22] J Balthrop,S Forest,M E J Newman,et al. Technological networks and the spread of computer viruses. Science,2004,304:527-529
[23] A L Barabási,E Bonabeau. Scale-Free Networks. Scientific American,2003,288: 60-69
[24] C Schulze. Advertising in the Sznajd marketing model. International Journal of Modem Physics C,2003,14(1):95-98
[25] S Luding. Granular media:Information propagation. Nature,2005,435:159-160
[26] P S Dodds,D J Watts,C F Sabel. Information exchange and the robustness of organizational networks. PNAS,2003,100(21):12516-12521
[27] B VersPagen,G Duysters. The small worlds of strategic technology alliances. Technovation,2004,24:563-571
[28] J Park,M E J Newman. A network-based ranking system for US co1lege football. Journal of Statistical Mechanics:Theory and Experiment,2005:P10014
[29] A S Elgazzar. Applications of small-world networks to some socio-economic system. Physics A,2003,324:402-407
[30] Watts D J, The "new" science of networks, Annual Review of Sociology, 2004, 30:243-270
[31]Wang X F, Complex networks: topology, dynamics and synchronization, International Journal of Bifurcation and Chaos, 2002, 12:885-916
[32]方锦清,汪小帆.刘曾荣,略论复杂性问题和作线性复杂网络系统的研究,科技导报,2004, 2:9-12
[33] Scott J, Social network analysis: a handbook, London, 2000
[34] Jeong H, Tombor B, Albert R, et al., The large-scale organization of metabolic networks,Nature, 2000, 407:651-654
[35] Wang X.F., Chen G.,“Complex Networks: Small-world, scale-free andbeyond.”IEEE Circuits & Systems Magazine, 2003, 3(1):6-20
[36] Newman M.E.J., Watts D.J.,“Renormalization group analysis of the small-world network model”, Phys. Lett. A, 1999, 263:341-346
[37] A.-L. Barabasi, Linked: The New Science of Networks, (Perseus, Cambridge, MA,2002)
[38] A. Fronczak, J. A. Holyst, M. Jedynak and J. Sienkiewicz, Physica A 316, 688 (2002)
[39] K.-1. Goh, E. Oh, H. Jeong, B. Kahng and D. Kim, Proc. Nall. Acad. Sci. USA 99,12583 (2002)
[40] H. Jeong, Z. Neda and A.-L. Barabasi, Europhys. Lett. 61, 567 (2003)
[41] T. Zhou, B.-H. Wang, Chin. Phys. Lett. 22, 1072 (2005)
[42] G. Caldarelli, A. Capocci, P. De Los Rios and M. A. Muiioz, Phys. Rev. Lett. 89, 258702 (2002)
[43] S. N. tsev and J. F. F. Mendes, Europhys. Lett. 52, 33 (2000)
[44] P. Holme and B. J. Kim, Phys. Rev. E 65, 026107 (2002)
[45] R. Albert and A. L. Barabási, Rev. Mod. Phys. 74, 47 (2002)
[46] Bailey N T J. The Mathematical Theory of Infectious Diseases and Its Applications. New York:Hafner,1975
[47] Anderson R M,May R M. Infectious Diseases in Humans.Oxford:Oxford University Press,1992
[48] Diekmann O, Heesterbeek J A P. Mathematical Epidemiology of Infectous Disease:Model Building,Analysis and Interpretation.New York:John Wiley & Son publisher,2000
[49]车宏安,顾基发.无标度网络及其系统科学意义[J].系统工程理论与实践. 2004,(4)
[50] A.-L.barabasi, R. Albert, and H. Jeong, Mean-field theory for scale-free random networks, Physica A,272(1999), 173-187
[51] Li X, Chen G R. A local-world evolving network model [ J]. PhysicaA: Statistical Mechanics and Its Applications, 2003, 328(1-2):274~286
[52]陈禹,方美琪,宗骁等. BA模型的三种扩展.系统工程学报,2005,20(2): 120-127
[53] Albert R. and Barabasi A.-L., Statistical mechanics of complex networks, Rev. Mod. Phys. 74, 2002 ,47-97
[54] Bollobas B., Mathematical results on scale-free random graphs, see Bornholdt S. and Schuster H. G. (eds), Handbook of Graphs and Networks–From the Genome to Internet, Wiley--VCH, 2002, 1-34
[55] Newman M. E. J., The Structure and function of complex networks, SIAM Rev. 45, 2003, 167-256
[56] Albert R. and Barabasi A.-L., Topology of evolving networks:local events and universality, Phys. Rev. Lett. 85, 2000, 5234-5237
[57] Shi D. H., Liu L. M., Zhu X., and Zhou H. J., Degree distributions of evolving networks, Europhys. Lett. 76(4), 2006, 10315-2
[58] Klemm K. and Eguiluz, V. M., Growing scale-free networks with small-world behavior, Phys. Rev. E 65. 2002, 057102
[59]吴金闪,狄增如,物理学进展,Vol24,No.1(2004)
[60]吕凤翥.C++语言基础教程(第2版).北京:清华大学出版社,2008
[61]刘放路.Visual C++与面向对象程序设计教程.北京:高等教育出版社,2001
[62]林锐,韩永泉.高质量程序设计指南—C/C++语言.3.北京:电子工业出版社,2007
[63]孙鑫,余安萍.VC++深入详解.北京:电子工业出版社,2009
[64] Booch G, Rumbaugh J, Jacobson I, et al. UML用户指南.北京:人民邮电出版社.2006