基于统计方法研究复杂网络的演化特性
|
摘要
目前,复杂系统与复杂性研究已经成为跨世纪的核心科学问题之一,随着各个领域的学者和研究人员对复杂网络的研究,并在各个领域都得了惊人的成果。但是同样对于复杂网络知识的不完备提出了挑战,存在的十大研究问题包括是否存在规范的网络分类方法,是否有更多的统计分布以及统计性质来深入刻画复杂网络的结构和分类,网络动力学如何影响网络的拓扑结构等等。
基于以上存在的几类问题,本文主要研究了网络的节点数目以及静态网络构造的优化,动态网络的演化机制和统计特征。首先采用分层抽样针对任意一个实际静态网络节点数目进行优化,同时最大程度保证网络的统计特性,并利用武汉市公交换乘网络和线路网络对此进行了实证研究。实证表明,该思想和方法在实际网络的应用和研究中,能够很大程度减少计算的工作量,同时很大程度上保证了网络的统计特征和拓扑结构。考虑到网络优化是一个动态过程,然后本文基于“穷者越穷,富者越富”和“生命游戏”两种演化机制来研究演化网络的演化机制和统计特性,同时证明了网络演化具有马氏性,并计算节点状态改变的一步转移概率矩阵和平稳分布,最后给出了一般性的实际动态复杂网络的马氏性研究。而在网络的演化机制中。本文利用贝叶斯理论思想给出了如何基于网络的先验信息,即目前的随机网络、无标度网络和小世界网络中连边的概率分布和实际网络演化中的样本信息,确定某一类实际网络真正的节点连接的后验概率分布。以上的三种统计方法为静态复杂网络的节点和结构的优化,动态演化网络的演化机制的确定,网络的预测和抗毁性研究提供了很好的研究参考和平台。
本文的创新点在于:
1)采用分层抽样对任意的一个实际复杂网络进行抽样设计,该理论和思想的应用在国内外都没有理论的分析和应用。实证研究表明该理论和方法并没有改变原有的统计性质,但是却很大程度上改变了工作量和计算量。
2)利用随机数学中的马尔科夫过程对复杂网络的演化过程进行研究,针对一般性的网络给出如何利用马尔科夫的理论对其进行计算转移概率矩阵,平稳分布并进行预测的方法。根据贝叶斯的理论与知识对复杂网络中连边或者去边的概率的选取,给出了一般网络的连边概率的后验密度函数的确定方法。
Complex system and complex networks have become to be the focus of scientific research issue over the 21~(st) century. Along with more and more researcher involving into complex networks, many significant achievements have been accomplished in various fields. However, which also has brought challenge because of its incomplete theoretical foundation. Whether there exists a normative method for classification? Or have more statistical distribution and properties for characterization of complex structure? How do the dynamics of complex networks affect its topological structure and etc?
Based on these several problems mentioned above, this thesis mainly researched on the optimization of nodes and construction in complex networks, evolution mechanism of dynamic networks and its statistical properties. At first, this paper designed a stratified sampling scheme for the common network, which meanwhile maximally maintains its statistical properties. Then the author also used public transfer network of Wuhan city and route network as an empirical study. It shows that this stratified sampling method not only greatly reduces the workload in computation, but also keeps the statistical characters and topological structure in practical application. Considering optimization of complex networks is a dynamic process, this paper researched on the evolution mechanism and statistical properties according to two dynamic evolutions-"rich are richer, poor are poorer" and "life game", simultaneously proved the Markov property of network evolution, and computed the first-step transpose matrix on variation of the node's states and its stationary distribution. Finally, the author studied on the Markov properties of common dynamic complex networks. More over, the author discussed how to determine the posteriori probability distribution of a certain practical network based on the prior information-the connecting probability distribution of edges in stochastic network, scale free network and small world network and the sampling information in practical evolution network. These three statistical methods will provide an excellent reference and platform for the optimization of nodes and structure of static complex networks, the determination of dynamic mechanism in complex networks and also the forecasting and study of invulnerability in complex networks.
The innovative points or this thesis are:
1) Used stratified sampling method to do sampling design on a practical complex network, of which the theory and thinking have not been analyzed or applied so far in the world. The empirical study shows that this theory and method has not changed its original statistical properties, but greatly reduced the workload and simplifies its computation.
2) Researched on the evolution process of complex networks based on Markov process, and also presented a way of computed transpose matrix, stationary distribution and forecasting according to Markov theory. Moreover, on the basic of Bayesian theory, this thesis also originally gave a way for obtaining the posteriori probability function to determine the probability of edges' connection or deletion.
基于以上存在的几类问题,本文主要研究了网络的节点数目以及静态网络构造的优化,动态网络的演化机制和统计特征。首先采用分层抽样针对任意一个实际静态网络节点数目进行优化,同时最大程度保证网络的统计特性,并利用武汉市公交换乘网络和线路网络对此进行了实证研究。实证表明,该思想和方法在实际网络的应用和研究中,能够很大程度减少计算的工作量,同时很大程度上保证了网络的统计特征和拓扑结构。考虑到网络优化是一个动态过程,然后本文基于“穷者越穷,富者越富”和“生命游戏”两种演化机制来研究演化网络的演化机制和统计特性,同时证明了网络演化具有马氏性,并计算节点状态改变的一步转移概率矩阵和平稳分布,最后给出了一般性的实际动态复杂网络的马氏性研究。而在网络的演化机制中。本文利用贝叶斯理论思想给出了如何基于网络的先验信息,即目前的随机网络、无标度网络和小世界网络中连边的概率分布和实际网络演化中的样本信息,确定某一类实际网络真正的节点连接的后验概率分布。以上的三种统计方法为静态复杂网络的节点和结构的优化,动态演化网络的演化机制的确定,网络的预测和抗毁性研究提供了很好的研究参考和平台。
本文的创新点在于:
1)采用分层抽样对任意的一个实际复杂网络进行抽样设计,该理论和思想的应用在国内外都没有理论的分析和应用。实证研究表明该理论和方法并没有改变原有的统计性质,但是却很大程度上改变了工作量和计算量。
2)利用随机数学中的马尔科夫过程对复杂网络的演化过程进行研究,针对一般性的网络给出如何利用马尔科夫的理论对其进行计算转移概率矩阵,平稳分布并进行预测的方法。根据贝叶斯的理论与知识对复杂网络中连边或者去边的概率的选取,给出了一般网络的连边概率的后验密度函数的确定方法。
Complex system and complex networks have become to be the focus of scientific research issue over the 21~(st) century. Along with more and more researcher involving into complex networks, many significant achievements have been accomplished in various fields. However, which also has brought challenge because of its incomplete theoretical foundation. Whether there exists a normative method for classification? Or have more statistical distribution and properties for characterization of complex structure? How do the dynamics of complex networks affect its topological structure and etc?
Based on these several problems mentioned above, this thesis mainly researched on the optimization of nodes and construction in complex networks, evolution mechanism of dynamic networks and its statistical properties. At first, this paper designed a stratified sampling scheme for the common network, which meanwhile maximally maintains its statistical properties. Then the author also used public transfer network of Wuhan city and route network as an empirical study. It shows that this stratified sampling method not only greatly reduces the workload in computation, but also keeps the statistical characters and topological structure in practical application. Considering optimization of complex networks is a dynamic process, this paper researched on the evolution mechanism and statistical properties according to two dynamic evolutions-"rich are richer, poor are poorer" and "life game", simultaneously proved the Markov property of network evolution, and computed the first-step transpose matrix on variation of the node's states and its stationary distribution. Finally, the author studied on the Markov properties of common dynamic complex networks. More over, the author discussed how to determine the posteriori probability distribution of a certain practical network based on the prior information-the connecting probability distribution of edges in stochastic network, scale free network and small world network and the sampling information in practical evolution network. These three statistical methods will provide an excellent reference and platform for the optimization of nodes and structure of static complex networks, the determination of dynamic mechanism in complex networks and also the forecasting and study of invulnerability in complex networks.
The innovative points or this thesis are:
1) Used stratified sampling method to do sampling design on a practical complex network, of which the theory and thinking have not been analyzed or applied so far in the world. The empirical study shows that this theory and method has not changed its original statistical properties, but greatly reduced the workload and simplifies its computation.
2) Researched on the evolution process of complex networks based on Markov process, and also presented a way of computed transpose matrix, stationary distribution and forecasting according to Markov theory. Moreover, on the basic of Bayesian theory, this thesis also originally gave a way for obtaining the posteriori probability function to determine the probability of edges' connection or deletion.
引文
[1] A.L.Barabasi. Linked: The New Science of Networks [M]. Perseus: Cambridge, 2002: 2-13
[2] S.H.Strogatz. SYNC: The Emerging Science of Spontaneous Order[M]. NewYork: Hperion, 2003:1-15
[3] S.H.Strogatz. Exploring complex networks[J]. Nature, 2001,410: 268-276
[4] Albert, Barabasi. Statistical mechanics of complex networks[J]. Mod. PhysRev, 2002, 74: 47-97
[5] S.N.Dorogovtsev, J.F.F.Mendes. Evolution of networks[J]. Advances in Physics, 2002 ,51: 1079-1187
[6] Newman M.E.J. The structure and function of complex networks[J]. SIAM Review, 2003 , 45: 167-256
[7] P.Erdos, A.Renyi. On random graphs[J]. Publications Mathematicae, 1959, 6: 290-297
[8] P.Erdos, A.Renyi. On the evolution of random graphs[J]. Pub. Math, inst.hung. Acad, sci., 1960,5: 17-61
[9] P.Erdos, A.Renyi. On the strength of connectedness of a random graphs[J]. Acta Math. Sci. Hungary, 1961,12:261-267
[10] Barabasi, A.-L. and Albert, R. Emergence of scaling in random networks[J]. Science, 1999, 286:509-512
[11] Barabasi, A.-L., Albert, R., and Jeong, H. Scale-free characteristics of random networks: The topology of the World Wide Web[J]. Physica A, 2000, 281: 69-77
[12] Albert-Laszlo Barabasi and E. Bonabeau. Scale-Free Networks[J]. Scientific American, 2003, 288: 60-69
[13] M. E. J. Newman, C. Moore, and D. J. Watts. Mean-Field Solution of the small world network model[J]. physical review letters, 2000, 84(14): 3201-3204
[14] D.J.Watts, S.H.Strogatz. Collective dynamics of "small-world" networks[J]. Nature, 1998, 393: 440-442
[15] M.Barthelemy, L.A.N.Amaral. small-world networks:Evidence for a crossver picture[J]. Phys. Rev, Lett ,1999, 82: 3180-3183
[16] Tadic B. Dynamics of directed graphs: the world-wideWeb[J], Physical A, 2001,293: 273-284
[17]A.Ramezanpour and V.Karimipour.Simple models of small-world networks with directed links[J].Phys.Rev.E,2002,66:036128
[18]N.Schwartz,R.Cohen,D,ben-Avraham,A.-L.Barabasi,and S.Havlin.Percolation in directed scale-free networks[J],physical review E,2002,66:015104
[19]Tetsuro Murai.master thesis:Spectral Analysis of Directed Complex Networks[M].Japan:Tokyo,2002:5-10
[20]Newman M E J,Forrest S,Balthrop J.Email networks and the spread of computer viruses[J].Physical Review E,2002,66:035101
[21]Roopnarine P D.Extinction cascades and catastrophe in ancient food webs[J].Paleobiology,2006,32(1):1-19
[22]Latora V,Marchiori M.Vulnerability and protection of infrastructure networks[J].Physical Review E,2005,71:015103
[23]Paolo Crucitti,Vito Latora,etal.Error and attack tolerance of complex networks[J],Physica A,2004,340:388-394
[24]Dezso Z,Barabasi A-L.Halting Viruses in scale-free networks[J].Physical Review E,2002,65:036104
[25]Gomez-Gardenes J,Echennigue P,Moreno Y.Immunization of real complex communication networks[J].The European Physical Joural B,2006,49:259-264
[26]Latora V,Marchiori.How the science of complex networks can help develeping strategies against terrorism[J].Chaos,Solitons and Fractals,2004,20:69-75
[27]Christinansen,M,H.Kirby S.Language evolution:consensus and controversies[J].Trends in cognitive Science,2003,7(7):300-307
[28]Costa L F.Learning about knowledge:A complex network approach[J].Physical Review E,2006,74(2):026103
[29]Elgazzar A S.Applications of small-world networks to some socio-economic systems[J].Physica A,2003,423:402-407
[30]Sznajd-Weron K,Weron R.A Simple model for price formation.Internation[J].Jounal of Modern Physics,2002,13(1):115-123
[31]Stauffer D,Aharony A,Costa L F,etal.Efficient Hopfield pattern recognition on a scale-free neural network[J].The European Physical Joural B,2003,32:395-399
[32]抽样调查,孙山泽 编著 北京大学出版社
[33]M.E.J.Newman,The structure and function of complex networks.The European Physical Journal B.2004.143-145
[34]刘江鸿.道路交通管理:城市交通可持续发展的瓶颈[J].城市规划,2002,1(3):27
[35]韩传峰,胡志伟.城市公交路网性能评估的网络图方法[J].系统工程,2003,(5):58-61.
[36]师桂兰,邓卫,葛亮.基于平均换乘的城市公交线网性能评价[J].洛阳大学学报.
[37]钱学森,于景元.一个科学的新领域-开放的复杂巨系统及其方法论[J]自然杂志,1990,13(1):3-10.
[38]赵金山,狄增如,王大辉.北京市公交网络几何性质的实证研究.复杂系统与复杂性科学.2005.4.
[39]傅方,王东炜.新建区域道路网络系统全局优化设计方法及应用[J].哈尔滨建筑大学学报,2002,35(3):115
[40]Chen,Q.,Chang,H.,Govindan,R.,Jamin,S.,Shenker,S.J.and Willinger,W..The origin of power laws in Internet topologies revisited,in Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies,IEEE Computer Society,2002.
[41]吴金闪,狄增如.从统计物理学看复杂网络研究,物理学进展,2004,24(1):18-46
[42]Faloutsos,M.,Faloutsos,P.&Faloutsos,C.On power-law relationships of the internet topology,ACM SIGCOMM'99.Comput.Commun.Rev,1999,29:251-263
[43]A.-L.Barabasi,R.Albert.Emergence of scaling in random networks,Science,1999,286:509-512
[44]Alert R,Barabasi A L.statistical mechanics of complex networks[J].Rev Mod Phys.2002.74:47-97
[45]R.Albert,A.L.Barabasi and H.Jeong.Mean-field theory for scale-free random networks,Physica A,1999,272:173-187,cond-mat/9907068.
[46]Réka Albert and Albert-László Barabási.Statistical mechanics of complex networks,Reviews of Modern Physics,2002,74:47.
[47]S.H.Strogatz.Exploring complex networks,Nature,2001,410:268-276
[48]宋学锋.复杂性、复杂系统与复杂性科学.中国科学基金,2003(5):262-269
[49]X.li,G.Chen.A local-world evolving network model,Physica A,Oct.2003,328:274-286
[50]Hartwell L H,Hopfield JJ,Leibler S,Murray A W.From molecular to modular cell biology[J]nature,1999,402:47-52
[51]Hanjd,Bertin N,Hao etal.evidence for dynamically organized modularity in the yeast protein-protein interaction network[J],nature,2004,430:88-93
[52]Milor,Shen Orr S S,Itkovitz,S,etal.Network motifs:somple building blocks of complex networks[J].Science,2002,298:824-827
[2] S.H.Strogatz. SYNC: The Emerging Science of Spontaneous Order[M]. NewYork: Hperion, 2003:1-15
[3] S.H.Strogatz. Exploring complex networks[J]. Nature, 2001,410: 268-276
[4] Albert, Barabasi. Statistical mechanics of complex networks[J]. Mod. PhysRev, 2002, 74: 47-97
[5] S.N.Dorogovtsev, J.F.F.Mendes. Evolution of networks[J]. Advances in Physics, 2002 ,51: 1079-1187
[6] Newman M.E.J. The structure and function of complex networks[J]. SIAM Review, 2003 , 45: 167-256
[7] P.Erdos, A.Renyi. On random graphs[J]. Publications Mathematicae, 1959, 6: 290-297
[8] P.Erdos, A.Renyi. On the evolution of random graphs[J]. Pub. Math, inst.hung. Acad, sci., 1960,5: 17-61
[9] P.Erdos, A.Renyi. On the strength of connectedness of a random graphs[J]. Acta Math. Sci. Hungary, 1961,12:261-267
[10] Barabasi, A.-L. and Albert, R. Emergence of scaling in random networks[J]. Science, 1999, 286:509-512
[11] Barabasi, A.-L., Albert, R., and Jeong, H. Scale-free characteristics of random networks: The topology of the World Wide Web[J]. Physica A, 2000, 281: 69-77
[12] Albert-Laszlo Barabasi and E. Bonabeau. Scale-Free Networks[J]. Scientific American, 2003, 288: 60-69
[13] M. E. J. Newman, C. Moore, and D. J. Watts. Mean-Field Solution of the small world network model[J]. physical review letters, 2000, 84(14): 3201-3204
[14] D.J.Watts, S.H.Strogatz. Collective dynamics of "small-world" networks[J]. Nature, 1998, 393: 440-442
[15] M.Barthelemy, L.A.N.Amaral. small-world networks:Evidence for a crossver picture[J]. Phys. Rev, Lett ,1999, 82: 3180-3183
[16] Tadic B. Dynamics of directed graphs: the world-wideWeb[J], Physical A, 2001,293: 273-284
[17]A.Ramezanpour and V.Karimipour.Simple models of small-world networks with directed links[J].Phys.Rev.E,2002,66:036128
[18]N.Schwartz,R.Cohen,D,ben-Avraham,A.-L.Barabasi,and S.Havlin.Percolation in directed scale-free networks[J],physical review E,2002,66:015104
[19]Tetsuro Murai.master thesis:Spectral Analysis of Directed Complex Networks[M].Japan:Tokyo,2002:5-10
[20]Newman M E J,Forrest S,Balthrop J.Email networks and the spread of computer viruses[J].Physical Review E,2002,66:035101
[21]Roopnarine P D.Extinction cascades and catastrophe in ancient food webs[J].Paleobiology,2006,32(1):1-19
[22]Latora V,Marchiori M.Vulnerability and protection of infrastructure networks[J].Physical Review E,2005,71:015103
[23]Paolo Crucitti,Vito Latora,etal.Error and attack tolerance of complex networks[J],Physica A,2004,340:388-394
[24]Dezso Z,Barabasi A-L.Halting Viruses in scale-free networks[J].Physical Review E,2002,65:036104
[25]Gomez-Gardenes J,Echennigue P,Moreno Y.Immunization of real complex communication networks[J].The European Physical Joural B,2006,49:259-264
[26]Latora V,Marchiori.How the science of complex networks can help develeping strategies against terrorism[J].Chaos,Solitons and Fractals,2004,20:69-75
[27]Christinansen,M,H.Kirby S.Language evolution:consensus and controversies[J].Trends in cognitive Science,2003,7(7):300-307
[28]Costa L F.Learning about knowledge:A complex network approach[J].Physical Review E,2006,74(2):026103
[29]Elgazzar A S.Applications of small-world networks to some socio-economic systems[J].Physica A,2003,423:402-407
[30]Sznajd-Weron K,Weron R.A Simple model for price formation.Internation[J].Jounal of Modern Physics,2002,13(1):115-123
[31]Stauffer D,Aharony A,Costa L F,etal.Efficient Hopfield pattern recognition on a scale-free neural network[J].The European Physical Joural B,2003,32:395-399
[32]抽样调查,孙山泽 编著 北京大学出版社
[33]M.E.J.Newman,The structure and function of complex networks.The European Physical Journal B.2004.143-145
[34]刘江鸿.道路交通管理:城市交通可持续发展的瓶颈[J].城市规划,2002,1(3):27
[35]韩传峰,胡志伟.城市公交路网性能评估的网络图方法[J].系统工程,2003,(5):58-61.
[36]师桂兰,邓卫,葛亮.基于平均换乘的城市公交线网性能评价[J].洛阳大学学报.
[37]钱学森,于景元.一个科学的新领域-开放的复杂巨系统及其方法论[J]自然杂志,1990,13(1):3-10.
[38]赵金山,狄增如,王大辉.北京市公交网络几何性质的实证研究.复杂系统与复杂性科学.2005.4.
[39]傅方,王东炜.新建区域道路网络系统全局优化设计方法及应用[J].哈尔滨建筑大学学报,2002,35(3):115
[40]Chen,Q.,Chang,H.,Govindan,R.,Jamin,S.,Shenker,S.J.and Willinger,W..The origin of power laws in Internet topologies revisited,in Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies,IEEE Computer Society,2002.
[41]吴金闪,狄增如.从统计物理学看复杂网络研究,物理学进展,2004,24(1):18-46
[42]Faloutsos,M.,Faloutsos,P.&Faloutsos,C.On power-law relationships of the internet topology,ACM SIGCOMM'99.Comput.Commun.Rev,1999,29:251-263
[43]A.-L.Barabasi,R.Albert.Emergence of scaling in random networks,Science,1999,286:509-512
[44]Alert R,Barabasi A L.statistical mechanics of complex networks[J].Rev Mod Phys.2002.74:47-97
[45]R.Albert,A.L.Barabasi and H.Jeong.Mean-field theory for scale-free random networks,Physica A,1999,272:173-187,cond-mat/9907068.
[46]Réka Albert and Albert-László Barabási.Statistical mechanics of complex networks,Reviews of Modern Physics,2002,74:47.
[47]S.H.Strogatz.Exploring complex networks,Nature,2001,410:268-276
[48]宋学锋.复杂性、复杂系统与复杂性科学.中国科学基金,2003(5):262-269
[49]X.li,G.Chen.A local-world evolving network model,Physica A,Oct.2003,328:274-286
[50]Hartwell L H,Hopfield JJ,Leibler S,Murray A W.From molecular to modular cell biology[J]nature,1999,402:47-52
[51]Hanjd,Bertin N,Hao etal.evidence for dynamically organized modularity in the yeast protein-protein interaction network[J],nature,2004,430:88-93
[52]Milor,Shen Orr S S,Itkovitz,S,etal.Network motifs:somple building blocks of complex networks[J].Science,2002,298:824-827