复杂网络理论及其在生物网中的应用
|
摘要
本文首先把二项随机图模型进行了推广,提出了两顶点连接的概率服从拟几何分布的随机图模型。在此基础上利用随机分析理论,分析了此类随机图的几何性质。提出了计算此类随机图的顶点度分布及团聚系数的一种方法,并且给出了计算此类随机图团聚系数的解析式。大量实证研究表明,加权网络具有无权网络中所没有的现象和权重的丰富特性,因此如何构造加权模型来实现这些性质就自然成为加权网络研究的重要问题,因此,本文的第二部分在边权演化模型的基础上提出了一种广义的加权演化网络模型,该模型改变了已有的加权网络中顶点强度的定义,同时把网络的拓扑演化与权重演化相结合建立模型,目的是来探讨加权网络中形成无标度现象的机理。利用连续性理论得出该模型中度分布、点的强度与边的强度均呈现无标度现象,同时利用分析的方法文章给出计算该模型中度分布和点的强度分布的解析式,并把解析的结果与数值模拟的结果作比较,得到与模拟的结果相一致的结论。由于生物网络是从系统和整体角度研究生物学现象的有效方法,因此,在文章的最后一部分,首先构造了一个反映细胞内部蛋白质之间相互作用的生物网络模型,然后利用图值马氏过程及随机网络衍生过程的理论对该模型进行了研究,给出了该模型中节点度分布函数满足的递推方程,利用此递推方程得到度分布为幂律分布的重要结论,同时利用数值模拟的方法验证了该模型的合理性。
In this paper, in order to explore further the mechanism responsible for complex networks, we extend the binomial random graph model and get a general model on which the connected probability between each pair of vertices follows by geometric-like distribution. With the theory of stochastic analysis, we analyze the geometric properties of this model and derive analytical expressions for the distribution of the degree P(k) and the clustering coefficient of the extended model. The part of the work is an extension to the study of the static statistical characteristic of the classical random graph model. Furthermore, recently study appears that the weight is very important in anglicizing the characteristic of the networks. So in the second part, in order to explore mechanism responsible for scale-free phenomena in weighted networks, we present a generalized model of weighted networks in which the system growth incorporated eight operations: weights’growth, weights’decrease, intrinsic strength growth and decrease, the addition of new links between the existing nodes, the rewiring and deleting links. In particular, the model yields scale-free behaviors for the weight, strength and degree distributions, meanwhile we get the analytical expressions of the strength and degree distributions through analytical method. Furthermore, we investigate the strength and degree distributions of the uniformly selected model, and find the preferential attachment is necessary to the emergence of scale-free phenomena in weighted networks. Finally, we found the analytical results are consistent with the numerical simulations. Due to the biological network is an effective method to studying the phenomenon of biology from the system and the global perspective. In final, we firstly construct a biological network to reflect the interaction of the proteins in the cells. Then using the theory of the graph-valued Markov process and derived process of random network processes we get the recurrence equation of the node degree distribution in the model. Base on the equation, we obtain the conclusion that the degree distribution following the power law. Meanwhile,we verify the reasonable of the model by the numerical simulation.
In this paper, in order to explore further the mechanism responsible for complex networks, we extend the binomial random graph model and get a general model on which the connected probability between each pair of vertices follows by geometric-like distribution. With the theory of stochastic analysis, we analyze the geometric properties of this model and derive analytical expressions for the distribution of the degree P(k) and the clustering coefficient of the extended model. The part of the work is an extension to the study of the static statistical characteristic of the classical random graph model. Furthermore, recently study appears that the weight is very important in anglicizing the characteristic of the networks. So in the second part, in order to explore mechanism responsible for scale-free phenomena in weighted networks, we present a generalized model of weighted networks in which the system growth incorporated eight operations: weights’growth, weights’decrease, intrinsic strength growth and decrease, the addition of new links between the existing nodes, the rewiring and deleting links. In particular, the model yields scale-free behaviors for the weight, strength and degree distributions, meanwhile we get the analytical expressions of the strength and degree distributions through analytical method. Furthermore, we investigate the strength and degree distributions of the uniformly selected model, and find the preferential attachment is necessary to the emergence of scale-free phenomena in weighted networks. Finally, we found the analytical results are consistent with the numerical simulations. Due to the biological network is an effective method to studying the phenomenon of biology from the system and the global perspective. In final, we firstly construct a biological network to reflect the interaction of the proteins in the cells. Then using the theory of the graph-valued Markov process and derived process of random network processes we get the recurrence equation of the node degree distribution in the model. Base on the equation, we obtain the conclusion that the degree distribution following the power law. Meanwhile,we verify the reasonable of the model by the numerical simulation.
引文
[1] B.Bollobas,Random Graphs, Academic Press,1985,60-67
[2] P.Erdos, A.Renyi, Publ.Math, 1959, 6:290-310
[3] S.N.Dorogovtsev, J.F.F.Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW, Oxford University Press, Oxford, 2003, 130-131
[4] R.Pastor-Satorras, A.Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge University Press, Cambridge, 2004
[5] R.Albert, H.Jeong, A.-L.Barabási, Diameter of the world-wide web, Nature, 1999, 401:130-131
[6] S.Wasserman and K.Faust, Social Network Analysis, Cambridge University Press, Cambridge, 1994, 100-110
[7] Alexei Vayquez,Romualdo Pastor-Satorras,Alessandro Vespignani,Large-scale topological and dynamical properties of the Internet, Physical Review E, 2002,65:066130-066134
[8] S.Redner, Connectivity of growing random networks, Eur.Phys.J.B4. 1998, 131:4629-4623
[9] M.E.J.Newman, The structure and function of complex networks,SIAM Rev.,2003, 45:167-265
[10] E.Almass, A.L.Barabasi, Global organization of metabolic fluxes in the bacterium Escherichia coli, Nature, 2004, 427:839-846
[11] S.N.Dorogovtsev, J.F.F.Mendes, A.N.Samukhin, Structure of growing networks with preferential linking, Phys.Rev.Lett, 2000, 85:4633-4641
[12] A.Barrat, M. Barthélemy, R. Pastot-Satorras, A. Vespignani,Dynamical and Correlation Properties of the Internet, Proc. Natl.Acad.Sci.U.S.A. , 2004 , 101:3747-3752
[13]张革新,生物信息学教程,化学工业出版社, 2006
[14] R.Guimera, S. Mossa, A. Turtschi, and L.A.N. Amearal, Weighted evolving networks, Proc.Natl. Acad. Sci. U.S.A., 2005, 102, 7794-7780
[15] Bauer A, Kuster B. ,Powerful tools for the characterization of protein complexes,Eur. J .Biochemist, 2003, 270: 570-578
[16] Fields S, Song O K. A novel genetic system to detect protein-protein interactions, Nature, 1989, 340: 245-246
[17] Uetz P, Giot L, Cagney G, et al. A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae, Nature, 2000, 403: 623-627
[18] A. Barrat, M. Barthelemy, A. Vespignani, Evolution and Structure of the Internet, Phys. Rev. Lett, 2004, 92:22870-22879
[19] W. Wang, B. Wang, B. Hu, G. Yan, and Q. Ou,Gernal Dynamics of Topology and Traffic on Weighted Technological Networks, Phys. Rev. Lett, 2005,94: 188702-188704
[20] X.B. Lu, X.F. Wang, and J.Q. Fang, Networks of econophysicsta, Physica. A, 2006,371: 841-850
[21] M. Li, J. Wu, D. Wang, T. Zhou, Z. Di and Y. Fan, Weighted networks of scientific communication, Physica .A ,2007, 375:355-364
[22] Z.M.Ma, The 3rd China Meeting on Complex Networks, Beijing, 2005
[23] X.M. Geng,A Markov Graph Model of Scale-free,Networks Beijing, 2005
[24]张志勇,精通Matlab6.5,北京航空航天大学出版社, 2003
[25]汪晓帆,复杂网络理论及其应用,清华大学出版社, 2006
[26]郭雷,许晓鸣,复杂网络,上海科技教育出版社, 2006
[27]车宏安,复杂网络-系统结构研究文集,上海理工大学系统研究所, 2004
[28] Strogatz.S.H,Exploring complex networks, Nature2001, 410:268-276
[29]龚光鲁,钱敏平,应用随机过程教程,清华大学出版社, 2002
[30] Ito T, Chiba T, Ozawa R,A comprehensive two-hybrid analysis to explore the yeast protein interactive, Proc NatlAcad Sci USA, 2001, 98: 4569-4574
[31] Pastor-Satorras R, Smith E, Sole R, Evolving protein interaction networks through gene duplication.,Theor Boil, 2003, 222: 199-210
[32] Jeong H, Tombor B, Albert R, Oltvai Z N, Barabasi A-L, The large-scale organization of metabolic networks,Nature, 2000, 407: 651-654.
[33]徐克学,生物数学,科学出版社, 1999
[34]姜启源,数学模型,高等教育出版社, 1993
[35]钱敏平,龚光鲁,随机过程导论,北京大学出版社, 1997
[36]林元烈,应用随机过程,清华大学出版社, 2002
[37] A.-L.Barabási, R. Albert, Scale-free Networks ,Science , 1999, 286:509-513
[38] R. Albert, and A.-L. Barabási,Statistics mechanics of complex networks, Rev. Mod.Phys,2000 ,74:47-52
[39] X.M. Geng,Q .Li,Random Models of Scale-free Networks, Physica A ,2005, 365:554-562
[40] Rigaut G, Shevchenko A, Rutz B, et al,A generic protein purification method for protein complex characterization and proteome exploration. Nat Biotechnology, 1999, 17:1030-1032
[41] S.H. Yook, H. Jeong, A.-L. Barabási, and Y. Tu, Mean-field theory for scale free random networks,Phys. Rev. Lett. 86 (2001)5835.
[42] D.Zheng, S. Trimper, B. Zheng, and P.M. Hui, From Biological to the the Internet and WWW,Phys. Rev. E 2003,67: 040102-040108
[2] P.Erdos, A.Renyi, Publ.Math, 1959, 6:290-310
[3] S.N.Dorogovtsev, J.F.F.Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW, Oxford University Press, Oxford, 2003, 130-131
[4] R.Pastor-Satorras, A.Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge University Press, Cambridge, 2004
[5] R.Albert, H.Jeong, A.-L.Barabási, Diameter of the world-wide web, Nature, 1999, 401:130-131
[6] S.Wasserman and K.Faust, Social Network Analysis, Cambridge University Press, Cambridge, 1994, 100-110
[7] Alexei Vayquez,Romualdo Pastor-Satorras,Alessandro Vespignani,Large-scale topological and dynamical properties of the Internet, Physical Review E, 2002,65:066130-066134
[8] S.Redner, Connectivity of growing random networks, Eur.Phys.J.B4. 1998, 131:4629-4623
[9] M.E.J.Newman, The structure and function of complex networks,SIAM Rev.,2003, 45:167-265
[10] E.Almass, A.L.Barabasi, Global organization of metabolic fluxes in the bacterium Escherichia coli, Nature, 2004, 427:839-846
[11] S.N.Dorogovtsev, J.F.F.Mendes, A.N.Samukhin, Structure of growing networks with preferential linking, Phys.Rev.Lett, 2000, 85:4633-4641
[12] A.Barrat, M. Barthélemy, R. Pastot-Satorras, A. Vespignani,Dynamical and Correlation Properties of the Internet, Proc. Natl.Acad.Sci.U.S.A. , 2004 , 101:3747-3752
[13]张革新,生物信息学教程,化学工业出版社, 2006
[14] R.Guimera, S. Mossa, A. Turtschi, and L.A.N. Amearal, Weighted evolving networks, Proc.Natl. Acad. Sci. U.S.A., 2005, 102, 7794-7780
[15] Bauer A, Kuster B. ,Powerful tools for the characterization of protein complexes,Eur. J .Biochemist, 2003, 270: 570-578
[16] Fields S, Song O K. A novel genetic system to detect protein-protein interactions, Nature, 1989, 340: 245-246
[17] Uetz P, Giot L, Cagney G, et al. A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae, Nature, 2000, 403: 623-627
[18] A. Barrat, M. Barthelemy, A. Vespignani, Evolution and Structure of the Internet, Phys. Rev. Lett, 2004, 92:22870-22879
[19] W. Wang, B. Wang, B. Hu, G. Yan, and Q. Ou,Gernal Dynamics of Topology and Traffic on Weighted Technological Networks, Phys. Rev. Lett, 2005,94: 188702-188704
[20] X.B. Lu, X.F. Wang, and J.Q. Fang, Networks of econophysicsta, Physica. A, 2006,371: 841-850
[21] M. Li, J. Wu, D. Wang, T. Zhou, Z. Di and Y. Fan, Weighted networks of scientific communication, Physica .A ,2007, 375:355-364
[22] Z.M.Ma, The 3rd China Meeting on Complex Networks, Beijing, 2005
[23] X.M. Geng,A Markov Graph Model of Scale-free,Networks Beijing, 2005
[24]张志勇,精通Matlab6.5,北京航空航天大学出版社, 2003
[25]汪晓帆,复杂网络理论及其应用,清华大学出版社, 2006
[26]郭雷,许晓鸣,复杂网络,上海科技教育出版社, 2006
[27]车宏安,复杂网络-系统结构研究文集,上海理工大学系统研究所, 2004
[28] Strogatz.S.H,Exploring complex networks, Nature2001, 410:268-276
[29]龚光鲁,钱敏平,应用随机过程教程,清华大学出版社, 2002
[30] Ito T, Chiba T, Ozawa R,A comprehensive two-hybrid analysis to explore the yeast protein interactive, Proc NatlAcad Sci USA, 2001, 98: 4569-4574
[31] Pastor-Satorras R, Smith E, Sole R, Evolving protein interaction networks through gene duplication.,Theor Boil, 2003, 222: 199-210
[32] Jeong H, Tombor B, Albert R, Oltvai Z N, Barabasi A-L, The large-scale organization of metabolic networks,Nature, 2000, 407: 651-654.
[33]徐克学,生物数学,科学出版社, 1999
[34]姜启源,数学模型,高等教育出版社, 1993
[35]钱敏平,龚光鲁,随机过程导论,北京大学出版社, 1997
[36]林元烈,应用随机过程,清华大学出版社, 2002
[37] A.-L.Barabási, R. Albert, Scale-free Networks ,Science , 1999, 286:509-513
[38] R. Albert, and A.-L. Barabási,Statistics mechanics of complex networks, Rev. Mod.Phys,2000 ,74:47-52
[39] X.M. Geng,Q .Li,Random Models of Scale-free Networks, Physica A ,2005, 365:554-562
[40] Rigaut G, Shevchenko A, Rutz B, et al,A generic protein purification method for protein complex characterization and proteome exploration. Nat Biotechnology, 1999, 17:1030-1032
[41] S.H. Yook, H. Jeong, A.-L. Barabási, and Y. Tu, Mean-field theory for scale free random networks,Phys. Rev. Lett. 86 (2001)5835.
[42] D.Zheng, S. Trimper, B. Zheng, and P.M. Hui, From Biological to the the Internet and WWW,Phys. Rev. E 2003,67: 040102-040108