复杂网络的结构刻画与蛋白质作用网络的建模研究
|
摘要
随着互联网等信息技术的兴起,网络日渐渗入我们生活的方方面面。人们对网络与日俱增的依赖激发了研究者对网络科学这一新兴领域的研究热潮。除了常见的互联网、万维网和电网等人工网络,网络研究的对象还包括神经细胞网络、基因调控网络和蛋白质作用网络等自然网络。这些网络不仅规模巨大、结构复杂,而且还处于无时无刻的变化当中。面对这样一种复杂的对象,两个很自然的问题是：它究竟长什么样?它由是怎么来的?本文围绕着这两个基本问题,试图通过网络刻画方法描绘它的样子,通过建模理解来推测它的形成演化机制。这里先提出一个网络刻画方法,随后将其应用于网络比较和模型评估。以蛋白质作用网络为例,运用多种评估方法总结多个模型的优缺点,通过融合改进来获得更为真实的网络模型,最终推测网络的形成演化机制。本文的主要研究工作和创新点如下：
1.提出了一种曲线化的网络刻画方法。该方法通过广度优先遍历获取网络的多尺度结构信息,并将网络表达为可作定量分析的曲线形式。针对是否每个网络都拥有自己独特的曲线这一严格而困难的问题,这里先得到曲线的一个一般表达式,然后将其应用于随机网络和一类小世界网络。针对这两类网络的计算显示,当节点数趋近无穷大时,它们拥有自己独特的曲线,一种网络结构对应于一条网络曲线。接着,通过分析发现,该曲线不仅可以清晰地分辨不同结构的网络,反映甘关网络的多个结构属性,还可以解释网络中的一些特殊现象,例如一个均质的小世界网络会在路由跟踪采样下呈现出一副非均质的无标度表象。
2.基于上述的网络曲线提出了一个网络比较方法。该方法将网络曲线视为从大规模网络中提取的结构特征,运用这一特征定义了一个用于度量网络间结构差异的网络距离,并利用该距离进行了网络的比较与分类。网络比较可以帮助一个模型找到最符合实际数据的那组参数,而网络分类可以在一堆模型中为真实网络找到最相符的那个。通过对蛋白质作用网络模型的参数估计与模型评估,验证了该比较与分类方法的有效性和鲁棒性。此外,相比于基于小子图统计的网络比较方法,本文方法不仅更具计算可行性,而且还提供了小子图统计所缺失的结构信息,增强了比较的可靠性。
3.提出了一个综合考虑基因复制和边重连机制的蛋白质作用网络模型。在蛋白质作用网络的建模研究中,基因复制与边的重连过程被认为是塑造网络结构的主要机制。虽然这两种机制都非常重要,但限于前期模型评估方法的局限性,致使现有模型或偏重于基因复制,或偏重于边的重连。本文采用多种互补的模型评估方法,比较了三个有竞争力的网络模型,通过数值实验发现,互补变异的基因复制适合于重现果蝇蛋白质作用网络的局部结构,而倾向于连接关键节点的边重连机制则适合于增强网络的整体连通性。在总结它们各自优缺点的基础上,提出了一个综合考虑两种机制的改进模型,并得到了多种评估方法的好评。实验结果表明,在塑造果蝇网络的结构时,基因复制与边的重连机制起着同等重要的作用,弱化其中的任何一个都无法完好的重现果蝇网络。
With the rise of information technology, networks increasingly permeate many aspects of our daily life. The growing dependence of people on networks has attracted researchers from different disciplines to this emerging field:network science. In addition to the tech-nology networks, such as the Internet, World Wide Web and power grids, the networks studied also include many natural networks, such as the neuron networks, gene regulation networks and protein-protein interaction networks. These networks often involve thousands or millions of vertices and edges, and also keep changing. Faced with such a complex ob-ject, two questions arise:what a network looks like? How it was formed? This article focuses on these two basic questions and devotes to portray the topology of the network and build models to infer its underlying growth mechanisms. Here we first propose a net-work description method, and then apply it to network comparison and model assessment. We investigate the strengths and weaknesses of multiple protein-protein interaction net-work models, and obtain a more realistic model, which help infer the growth and evolution process of the network. The main results of this dissertation are as follows:
1. A curve shaped description of large networks is proposed. The description ex-plores multi-scales information of a network by the use of breadth-first traversal. It serves as a bridge linking networks of different structures with a set of particular curves. To in-vestigate the hard problem that whether every network has its own unique curve, here we apply this curve shaped description to both random graphs and a set of small world networks. The analytical results show that each of these networks has a unique curve ex-pression in the limit of large network size. The curve expression possesses a number of network properties in one bag, such as the size of the giant component and the local clus-tering. Interestingly, it shows that a network which is homogeneous and small-world-like appears to have a power-law degree distribution under traceroute sampling.
2. A network comparison method is proposed base on the curve mentioned above. This approach takes the curve as a feature extracted from large-scale networks and defines a graph distance to measure the structural differences between networks. The graph distance can then be used in network comparison and classification. Network comparison can help a network model find the parameters that best fit a real data, and the classification can help a real data find the best-fitting model among a pile of candidates. The effectiveness and the robustness of the comparison and classification method are validated through the numerical experiments on parameter estimation and model evaluation for a protein-protein interaction network. Additionally, compared to the network classification method based on subgraph census, the method proposed here is much faster and provides a complementary aspect of the network, which enhances the reliability of the comparison results.
3. A comprehensive model considering both gene duplication and link dynamics is proposed for protein-protein interaction networks. In the study of network modeling of protein-protein interaction networks, gene duplication and link dynamics are regarded as the major mechanisms shaping network structure. Although the two mechanisms are very important, the existing models emphasis heavily only on one of the two since the lack of good evaluation methods for network models. Here we use a variety of complemen-tary evaluation methods to assess three competitive network models. The numerical results show that the gene duplication is good that reproducing the local structure of Drosophila's protein network, and the link dynamics is good at enhancing the overall connectivity of the network. In summing up, a comprehensive model considering both the two mechanisms is proposed and obtains a high rank in the evaluation methods. Experimental results show that both the gene duplication and link dynamics are critical in shaping the topology of Drosophila's network, weakening any of the two cannot reproduce the intact network.
1.提出了一种曲线化的网络刻画方法。该方法通过广度优先遍历获取网络的多尺度结构信息,并将网络表达为可作定量分析的曲线形式。针对是否每个网络都拥有自己独特的曲线这一严格而困难的问题,这里先得到曲线的一个一般表达式,然后将其应用于随机网络和一类小世界网络。针对这两类网络的计算显示,当节点数趋近无穷大时,它们拥有自己独特的曲线,一种网络结构对应于一条网络曲线。接着,通过分析发现,该曲线不仅可以清晰地分辨不同结构的网络,反映甘关网络的多个结构属性,还可以解释网络中的一些特殊现象,例如一个均质的小世界网络会在路由跟踪采样下呈现出一副非均质的无标度表象。
2.基于上述的网络曲线提出了一个网络比较方法。该方法将网络曲线视为从大规模网络中提取的结构特征,运用这一特征定义了一个用于度量网络间结构差异的网络距离,并利用该距离进行了网络的比较与分类。网络比较可以帮助一个模型找到最符合实际数据的那组参数,而网络分类可以在一堆模型中为真实网络找到最相符的那个。通过对蛋白质作用网络模型的参数估计与模型评估,验证了该比较与分类方法的有效性和鲁棒性。此外,相比于基于小子图统计的网络比较方法,本文方法不仅更具计算可行性,而且还提供了小子图统计所缺失的结构信息,增强了比较的可靠性。
3.提出了一个综合考虑基因复制和边重连机制的蛋白质作用网络模型。在蛋白质作用网络的建模研究中,基因复制与边的重连过程被认为是塑造网络结构的主要机制。虽然这两种机制都非常重要,但限于前期模型评估方法的局限性,致使现有模型或偏重于基因复制,或偏重于边的重连。本文采用多种互补的模型评估方法,比较了三个有竞争力的网络模型,通过数值实验发现,互补变异的基因复制适合于重现果蝇蛋白质作用网络的局部结构,而倾向于连接关键节点的边重连机制则适合于增强网络的整体连通性。在总结它们各自优缺点的基础上,提出了一个综合考虑两种机制的改进模型,并得到了多种评估方法的好评。实验结果表明,在塑造果蝇网络的结构时,基因复制与边的重连机制起着同等重要的作用,弱化其中的任何一个都无法完好的重现果蝇网络。
With the rise of information technology, networks increasingly permeate many aspects of our daily life. The growing dependence of people on networks has attracted researchers from different disciplines to this emerging field:network science. In addition to the tech-nology networks, such as the Internet, World Wide Web and power grids, the networks studied also include many natural networks, such as the neuron networks, gene regulation networks and protein-protein interaction networks. These networks often involve thousands or millions of vertices and edges, and also keep changing. Faced with such a complex ob-ject, two questions arise:what a network looks like? How it was formed? This article focuses on these two basic questions and devotes to portray the topology of the network and build models to infer its underlying growth mechanisms. Here we first propose a net-work description method, and then apply it to network comparison and model assessment. We investigate the strengths and weaknesses of multiple protein-protein interaction net-work models, and obtain a more realistic model, which help infer the growth and evolution process of the network. The main results of this dissertation are as follows:
1. A curve shaped description of large networks is proposed. The description ex-plores multi-scales information of a network by the use of breadth-first traversal. It serves as a bridge linking networks of different structures with a set of particular curves. To in-vestigate the hard problem that whether every network has its own unique curve, here we apply this curve shaped description to both random graphs and a set of small world networks. The analytical results show that each of these networks has a unique curve ex-pression in the limit of large network size. The curve expression possesses a number of network properties in one bag, such as the size of the giant component and the local clus-tering. Interestingly, it shows that a network which is homogeneous and small-world-like appears to have a power-law degree distribution under traceroute sampling.
2. A network comparison method is proposed base on the curve mentioned above. This approach takes the curve as a feature extracted from large-scale networks and defines a graph distance to measure the structural differences between networks. The graph distance can then be used in network comparison and classification. Network comparison can help a network model find the parameters that best fit a real data, and the classification can help a real data find the best-fitting model among a pile of candidates. The effectiveness and the robustness of the comparison and classification method are validated through the numerical experiments on parameter estimation and model evaluation for a protein-protein interaction network. Additionally, compared to the network classification method based on subgraph census, the method proposed here is much faster and provides a complementary aspect of the network, which enhances the reliability of the comparison results.
3. A comprehensive model considering both gene duplication and link dynamics is proposed for protein-protein interaction networks. In the study of network modeling of protein-protein interaction networks, gene duplication and link dynamics are regarded as the major mechanisms shaping network structure. Although the two mechanisms are very important, the existing models emphasis heavily only on one of the two since the lack of good evaluation methods for network models. Here we use a variety of complemen-tary evaluation methods to assess three competitive network models. The numerical results show that the gene duplication is good that reproducing the local structure of Drosophila's protein network, and the link dynamics is good at enhancing the overall connectivity of the network. In summing up, a comprehensive model considering both the two mechanisms is proposed and obtains a high rank in the evaluation methods. Experimental results show that both the gene duplication and link dynamics are critical in shaping the topology of Drosophila's network, weakening any of the two cannot reproduce the intact network.
引文
[1]Albert R., Barabasi A.-L.. Statistical mechanics of complex networks[J]. Rev. Mod. Phys.,2002,74(1):47-97.
[2]Dorogovtsev S. N., Mendes J. F. F.. Evolution of networks[J]. Adv. Phys.,2002, 51(4):1079-1187.
[3]Newman M. E. J.. The structure and function of complex networks[J]. SIAM Rev., 2003,45(2):167-256.
[4]Wang X. F., Chen G.. Complex networks:Scale-free and beyond[J]. IEEE Circuits And Systems Magazine,2003,3(2):6-20.
[5]Boccaletti S., Latora V., Moreno Y., et al. Complex networks:Structure and dynamics[J]. Phys. Rep.,2006,424(4-5):175-308.
[6]方锦清,汪小帆,郑志刚等.一门崭新的交叉科学：网络科学(上)[J].物理学进展,2007,27：239-343.
[7]方锦清,汪小帆,郑志刚等.一门崭新的交叉科学：网络科学(下)[J].物理学进展,2007,27：361448.
[8]Bollobas B., Random Graphs[M]. Secondth ed. Cambridge, UK:Cambridge University Press,2001.
[9]Milgram S., The small-world problem[J]. Psychology Today,1967, 1(1):61-67.
[10]Travers J., Milgram S.. An experimental study of the small world problem[J]. Sociometry,1969,32(4):425-443.
[11]de Solla Price D. J.. Networks of Scientific Papers [J]. Science,1965, 149(3683):510-515.
[12]de S. Price D. J.. A general theory of bibliometric and other cumulative advantage processes[J]. J. Am. Soc. Inform. Sci.,1976,27(5):292-306.
[13]Merton R. K.. The matthew effect in science[J]. Science,1968,159(3810):56-63.
[14]Watts D. J., Strogatz S. H., Collective dynamics of "small-world" networks[J]. Nature (London),1998,393(6684):440-442.
[15]Barabasi A.-L., Albert R.. Emergence of scaling in random networks[J]. Science, 1999,286(5439):509-512.
[16]Albert R., Jeong H., Barabasi A.-L.,Internet:Diameter of the world-wide web[J]. Nature (London),1999,401(6749):130-131.
[17]Faloutsos M.,FaloutsosP., Faloutsos C., On power-law relationships of the internet topology[J]. ACM SIGCOMM Comput. Commun. Rev.,1999,29(4):251-262.
[18]Girvan M., Newman M. E. J.. Community structure in social and biological net-works[J]. Proc. Natl. Acad. Sci. USA,2002,99(12):7821-7826.
[19]Zhou H., Distance, dissimilarity index, and network community structure[J]. Phys. Rev. E,2003,67(6):061901.
[20]Fortunato S.. Community detection in graphs[J]. Phys. Rep.,2010,486(3-5):75-174.
[21]淦文燕,赫南,李德毅等.一种基于拓扑势的网络社区发现方法[J].软件学报,2009,20(8)：2241-2254.
[22]Alon U., Network motifs:Theory and experimental approaches[J]. Nat. Rev. Genet.,2007,8:450-461.
[23]Clauset A., Moore C., Newman M. E. J.. Hierarchical structure and the prediction of missing links in networks[J]. Nature (London),2008,453(7191):98-101.
[24]Giot L., Bader J. S., Brouwer C., et al. A Protein Interaction Map of Drosophila melanogaster[J]. Science,2003,302(5651):1727-1736.
[25]Anderson R. M., May R. M., Infectious Diseases of Humans[M]. Oxford University Press,1991.
[26]Pastor-Satorras R., Vespignani A., Epidemic spreading in scale-free networks[J]. Phys. Rev. Lett.,2001,86(14):3200-3203.
[27]Albert R., Jeong H., Barabasi A.-L.. Error and attack tolerance of complex net-works[J]. Nature,2000,406(6794):378-382.
[28]Xuan Q., Du F., Wu T.-J., et al. Emergence of heterogeneous structures in chemical reaction-diffusion networks[J]. Phys. Rev. E,2010,82(4):046116.
[29]周涛,傅忠谦,牛永伟等.复杂网络上传播动力学研究综述[J].自然科学进展,2005,15(5)：513-518.
[30]Toroczkai Z.. Complex networks:The challenge of interaction topology[J]. Los Alamos Sci.,2005,29:94-109.
[31]Dorogovtsev S. N., Goltsev A. V., Mendes J. F. F.. Critical phenomena in complex networks[J]. Rev. Mod. Phys.,2008,80(4):1275-1335.
[32]Ellison N. B., Steinfield C., Lampe C.. The benefits of facebook "friends:" so-cial capital and college students'use of online social network sites[J]. Journal of Computer-Mediated Communication,2007,12(4):1143-1168.
[33]Kwak H., Lee C., Park H., et al. What is twitter, a social network or a news media?[C]//Proceedings of the 19th international conference on World wide web. New York, NY, USA:ACM,2010:591-600.
[34]Colizza V., Barrat A., Barthelemy M., et al. The role of the airline transporta-tion network in the prediction and predictability of global epidemics[J]. Proceed-ings of the National Academy of Sciences of the United States of America,2006, 103(7):2015-2020.
[35]Smith J. M., Price G. R.. The logic of animal conflict[J]. Nature,1973, 246(5427):15-18.
[36]Nowak M. A.. Five rules for the evolution of cooperation[J]. Science,2006, 314(5805):1560-1563.
[37]Ohtsuki H., Hauert C., Lieberman E., et al. A simple rule for the evolution of cooperation on graphs and social networks[J]. Nature,2006,441(7092):502-505.
[38]Zhong L.-X., Zheng D.-F., Zheng B., et al. Networking effects on cooperation in evolutionary snowdrift game[J]. Europhysics Letters,2006,76(4):724.
[39]Zhou H., Lipowsky R., Dynamic pattern evolution on scale-free networks[J]. Pro-ceedings of the National Academy of Sciences of the United States of America, 2005,102(29):10052-10057.
[40]Kleinberg J. M.,Navigation in a small world[J]. Nature,2000,406(6798):845-845.
[41]车宏安,顾基发.无标度网络及其系统科学意义[J].系统工程理论与实践,2004,44(4)：11-16.
[42]吴金闪,狄增如.从统计物理学看复杂网络研究[J].物理学进展,2004,24：18-46.
[43]汪秉宏,周涛,何大韧.统计物理学与复杂系统研究最新发展趋势分析[J].中国基础科学,2005,3：37-43.
[44]周涛,柏文洁,汪秉宏等.复杂网络研究概述[J].物理,2005,34：31-36.
[45]王飞跃.社会计算的意义及其展望[J].中国计算机学会通讯,2006,(2).
[46]李国杰.关于网络社会宏观信息学研究的一些思考[J].中国计算机学会通讯,2006,(2).
[47]程学期,陈海强,韩战钢.社会信息的网络化分析初探[J].中国计算机学会通讯,2006,(2).
[48]汪秉宏,周涛,王文旭等.当前复杂系统研究的几个方向[J].复杂系统与复杂性科学,2008,5(4)：21-28.
[49]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社,2006.
[50]郭雷,许晓鸣.复杂网络[M].上海：上海科技教育出版社,2006.
[51]陈关荣,许晓鸣.复杂网络理论及应用[M].上海：上海系统科学出版社,2008.
[52]何大韧,刘宗华,汪秉宏.复杂系统与复杂网络[M].北京：高等教育出版社,2008.
[53]刘建香.复杂网络及其存国内研究进展的综述[J].系统科学学报,2009,17(4)：31-37.
[54]Newman M. E. J., Leicht E. A., Mixture models and exploratory analysis in net-works[J]. Proc. Natl. Acad. Sci. USA,2007,104(23):9564-9569.
[55]Eckmann J.-P., Moses E.. Curvature of co-links uncovers hidden thematic layers in the World Wide Web[J]. Proc. Natl. Acad. Sci. USA,2002,99(9):5825-5829.
[56]Guimera R., Amaral L. A. N.. Cartography of complex networks:modules and universal roles[J]. J. Stat. Mech.:Theor. Exp.,2005,2005(02):P02001.
[57]Spielman D. A.. Spectral graph theory and its applications[C]//FOCS'07:Proceed-ings of the 48th Annual IEEE Symposium on Foundations of Computer Science. Washington, DC, USA:IEEE Computer Society,2007:29-38.
[58]Middendorf M., Ziv E., Wiggins C. H.. Inferring network mechanisms:The Drosophila melanogaster protein interaction network[J]. Proc. Natl. Acad. Sci. U S A,2005,102(9):3192-3197.
[59]Przulj N., Corneil D. G., Jurisica I.. Modeling interactome:scale-free or geomet-ric?[J]. Bioinformatics,2004,20(18):3508-3515.
[60]Przulj N.. Biological network comparison using graphlet degree distribution[J]. Bioinformatics,2007,23(2):e177-e183.
[61]Memisevic V., Milenkovic T., Przulj N.. An integrative approach to modelling biological networks[J]. J. Integr. Bioinform.,2010,7(3):120.
[62]Stark C., Breitkreutz B.-J., Reguly T., et al. BioGRID:a general repository for interaction datasets[J]. Nucl. Acids Res.,2006,34:D535-539.
[63]Jeong H., Mason S. P., Barabasi A.-L., el al. Lethality and centrality in protein networks[J]. Nature,2001,411(6833):41-42.
[64]Barabasi A.-L., Oltvai Z. N.. Network biology:understanding the cell's functional organization [J]. Nat Rev Genet,2004,5(2):101-113.
[65]Milo R., Shen-Orr S., Itzkovitz S., etal. Network Motifs:Simple Building Blocks of Complex Networks[J]. Science,2002,298(5594):824-827.
[66]Sole R. V., Pastor-Satorras R., Smith E., et al. A model of large-scale proteome evolution[J]. Adv. Complex Syst.,2002,5(1):43-54.
[67]Vazquez A., Flammini A., Maritan A., et al. Modeling of protein interaction networks[J]. ComPlexUs,2003, 1(1):38-44.
[68]Berg J., Lassig M., Wagner A., Structure and evolution of protein interaction networks:a statistical model for link dynamics and gene duplications[J]. BMC Evol.Biol.,2004,4(1):51.
[69]Ohno S., Evolution by gene duplication[M]. Germany:Springer-Verlag Heidelberg: Springer,1970.
[70]Wagner A., How the global structure of protein interaction networks evolves[J]. Proc. R. Soc. Lond. B Biol. Sci.,2003,270(1514):457-466.
[71]Thorelli H. B., Networks:Between markets and hierarchies[J]. Strategic Manage-ment Journal,1986,7(1):37-51.
[72]Rauch J. E., Business and social networks in international trade[J]. Journal of Economic Literature,2001,39(4):1177-1203.
[73]Liljeros F., Amaral L. A. N., Stanley H. E., et al. The web of human sexual contacts[J]. Nature,2001,411:907-908.
[74]Schena M., Shalon D., Davis R. W., et al. Quantitative monitoring of gene expression patterns with a complementary dna microarray[J]. Science,1995, 270(5235):467-470.
[75]Fields S., Song O.-k.. A novel genetic system to detect protein-protein interac-tions[J]. Nature,1989,340:245-246.
[76]Lockhart D. J., Winzeler E. A.. Genomics, gene expression and dna arrays[J]. Nature,2000,405:827-836.
[77]P. U.. Systematic and large-scale two-hybrid screens[J]. Current Opinion in Micro-biology,2000,3:303-308.
[78]Barabasi A.-L.. Network medicine—from obesity to the "diseasome"[J]. New England Journal of Medicine,2007,357(4):404-407.
[79]Albert R.. Scale-free networks in cell biology[J]. Journal of Cell Science,2005, 118(21):4947-4957.
[80]Oltvai Z. N., Barabasi A.-L.. Life's complexity pyramid[J]. Science,2002, 298(5594):763-764.
[81]Paine R. T.. Food webs:Linkage, interaction strength and community infrastruc-ture [J]. Journal of Animal Ecology,1980,49(3):666-685.
[82]Newman M. E. J., Strogatz S. H., Watts D. J.. Random graphs with arbitrary degree distributions and their applications[J]. Phys. Rev. E,2001,64(2):026118.
[83]Garfield E.. It's a small world after all [J]. Current Contents,1979,43:5-10.
[84]Watts D. J., Dodds P. S., Newman M. E. J.. Identity and search in social net-works[J]. Science,2002,296(5571):1302-1305.
[85]Clauset A., Shalizi C. R., Newman M. E. J.. Power-law distributions in empirical data[J]. SIAM Rev.,2009,51:661-703.
[86]Jeong H., Tombor B., Albert R., et al. The large-scale organization of metabolic networks[J]. Nature,2000,407(6804):651-654.
[87]Flake G. W., Lawrence S., Giles C. L., et al. Self-organization and identification of web communities[J]. IEEE Computer,2002,35(3):66-71.
[88]Guimera R., Amaral L. A. N.. Functional cartography of complex metabolic net-works[J]. Nature,2005,433(7028):895-900.
[89]Palla G., Derenyi I., Farkas I., et al. Uncovering the overlapping community struc-ture of complex networks in nature and society[J]. Nature,2005,435(7043):814-818.
[90]Lancichinetti A., Kivela M., Saramaki J., et al. Characterizing the community structure of complex networks[J]. PLoS ONE,2010,5(8):e11976.
[91]Newman M., Detecting community structure in networks[J]. The European Physi-cal Journal B-Condensed Matter and Complex Systems,2004,38:321-330.
[92]Rosvall M., Bergstrom C. T.. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences,2008, 105(4):1118-1123.
[93]Vespignani A., Evolution thinks modular[J]. Nat Genet,2003,35(2):118-119.
[94]Wuchty S., Oltvai Z. N., Barabasi A.-L.. Evolutionary conservation of motif constituents in the yeast protein interaction network[J]. Nat Genet,2003,35(2):176-179.
[95]Heath A. P., Kavraki L. E.. Computational challenges in systems biology[J]. Com-puter Science Review,2009,3(1):1-17.
[96]Wormald N. C., Models of random regular graphs[G]//Lamb J. D., Preece D. A. . Surveys in Combinatorics,1999. vol 267. Cambridge, UK:Cambridge University Press,1999:239-298.
[97]Hu Y., Wang Y., Li D., et al. Possible origin of efficient navigation in small worlds[J]. Phys. Rev. Lett.,2011,106(10):108701.
[98]Korniss G., Novotny M. A., Guclu H., et al. Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations [J]. Science,2003,299(5607):677-679.'
[99]Guclu H., Korniss G., Novotny M. A., et al. Synchronization landscapes in small-world-connected computer networks[J]. Phys. Rev. E,2006,73(6):066115.
[100]Li W., Kurata H.. Visualizing global properties of large complex networks[J]. PLoS ONE,2008,3(7):e2541.
[101]Knuth D.E.. The Art Of Computer Programming[M]. thirdth ed. Boston:Addison-Wesley:,1997.
[102]Chandler D., Introduction to modern statistical mechanics[M]. Oxford University Press,1987.
[103]Molloy M., Reed B., The size of the giant component of a random graph with a given degree sequence[J]. Combin. Probab. Comput.,1998,7(3):295-305.
[104]Isaacson E., Keller H. B., Numerical Analysis[M]. New York:John Wiley& Sons, 1966.
[105]Richard L. Burden J. D. F., Numerical Analysis[M]. Eighthth ed.:Brooks Cole, 2004.
[106]Lakhina A., Byers J. W., Crovella M., et al. Sampling biases in ip topology measurements[C]//INFOCOM 2003:Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ, USA:IEEE Press,2003:332-341.
[107]Petermann T., De Los Rios P.. Exploration of scale-free networks:Do we measure the real exponents?[J]. Eur. Phys. J. B,2004,38(2):201-204.
[108]Clauset A., Moore C.. Accuracy and scaling phenomena in internet mapping[J]. Phys. Rev. Lett.,2005,94(1):018701.
[109]Achlioptas D., Clauset A., Kempe D., et al. On the bias of traceroute sampling: or, power-law degree distributions in regular graphs[C]//STOC'05:Proceedings of the 37th ACM Symposium on Theory of Computing. New York, NY, USA:ACM Press,2005:694-703.
[110]Dall'Asta L., Alvarez-Hamelin I., Barrat A., et al. Exploring networks with traceroute-like probes:Theory and simulations[J]. Theor. Comput. Sci.,2006, 355(1):6-24.
[111]Toroczkai Z., Bassler K. E.. Network dynamics:Jamming is limited in scale-free systems[J]. Nature (London),2004,428:716-716.
[112]Toroczkai Z., Kozma B., Bassler K. E., et al. Gradient networks[J]. J. Phys. A: Math. Theor.,2008,41(15):155103.
[113]Kalisky T., Sreenivasan S., Braunstein L. A., et al. Scale-free networks emerging from weighted random graphs[J]. Phys. Rev. E,2006,73(2):025103(R).
[114]Chklovskii D. B., Schikorski T., Stevens C. F., Wiring optimization in cortical circuits[J]. Neuron,2002,34:341-347.
[115]Onnela J.-P., Fenn D. J., Reid S., el al. A taxonomy of networks. http://arxiv.org/abs/1006.5731vl[J].2010.
[116]Ispolatov I., Krapivsky P. L., Yuryev A.. Duplication-divergence model of protein interaction network[J]. Phys. Rev. E,2005,71(6):061911.
[117]Li S., Armstrong C. M., Bertin N., el al. A map of the interactome network of the metazoan c. elegans[J]. Science,2004,303(5657):540-543.
[118]Costa L. d. F., Rodrigues F. A., Travieso G., et al. Characterization of complex networks:A survey of measurements [J]. Advances in Physics,2007,56(1):167-242.
[119]Filkov V., Saul Z. M., Roy S., et al. Modeling and verifying a broad array of network properties[J]. Europhysics Letters,2009,86(2):28003.
[120]Wiuf C., Brameier M., Hagberg O., et al. A likelihood approach to analysis of network data[J]. Proc. Natl. Acad. Sci. USA,2006,103(20):7566-7570.
[121]Leskovec J., Chakrabarti D., Kleinberg J., et al. Kronecker graphs:An approach to modeling networks[J]. J. Mach. Learn. Res.,2010,11:985-1042.
[122]Yu J., Pacifico S., Liu G., et al. Droid:the drosophila interactions database, a com-prehensive resource for annotated gene and protein interactions [J]. BMC Genomics, 2008,9(1):461.
[123]Rain J. C., et. al. The protein-protein interaction map of helicobacter pylori[J]. Nature,2001,409(6817):211-215.
[124]Xiong A.-S., Peng R.-H., Zhuang J., et al. Gene duplication, transfer, and evolution in the chloroplast genome[J]. Biotech. Adv.,2009,27(4):340-347.
[125]Cvetkovic D. M., Rowlinson P., Simic S.. Eigenspaces of graphs[M]. Cambridge University Press,1997.
[126]Bishop C. M., Pattern recognition and machine learning[M]. Springer,2006.
[2]Dorogovtsev S. N., Mendes J. F. F.. Evolution of networks[J]. Adv. Phys.,2002, 51(4):1079-1187.
[3]Newman M. E. J.. The structure and function of complex networks[J]. SIAM Rev., 2003,45(2):167-256.
[4]Wang X. F., Chen G.. Complex networks:Scale-free and beyond[J]. IEEE Circuits And Systems Magazine,2003,3(2):6-20.
[5]Boccaletti S., Latora V., Moreno Y., et al. Complex networks:Structure and dynamics[J]. Phys. Rep.,2006,424(4-5):175-308.
[6]方锦清,汪小帆,郑志刚等.一门崭新的交叉科学：网络科学(上)[J].物理学进展,2007,27：239-343.
[7]方锦清,汪小帆,郑志刚等.一门崭新的交叉科学：网络科学(下)[J].物理学进展,2007,27：361448.
[8]Bollobas B., Random Graphs[M]. Secondth ed. Cambridge, UK:Cambridge University Press,2001.
[9]Milgram S., The small-world problem[J]. Psychology Today,1967, 1(1):61-67.
[10]Travers J., Milgram S.. An experimental study of the small world problem[J]. Sociometry,1969,32(4):425-443.
[11]de Solla Price D. J.. Networks of Scientific Papers [J]. Science,1965, 149(3683):510-515.
[12]de S. Price D. J.. A general theory of bibliometric and other cumulative advantage processes[J]. J. Am. Soc. Inform. Sci.,1976,27(5):292-306.
[13]Merton R. K.. The matthew effect in science[J]. Science,1968,159(3810):56-63.
[14]Watts D. J., Strogatz S. H., Collective dynamics of "small-world" networks[J]. Nature (London),1998,393(6684):440-442.
[15]Barabasi A.-L., Albert R.. Emergence of scaling in random networks[J]. Science, 1999,286(5439):509-512.
[16]Albert R., Jeong H., Barabasi A.-L.,Internet:Diameter of the world-wide web[J]. Nature (London),1999,401(6749):130-131.
[17]Faloutsos M.,FaloutsosP., Faloutsos C., On power-law relationships of the internet topology[J]. ACM SIGCOMM Comput. Commun. Rev.,1999,29(4):251-262.
[18]Girvan M., Newman M. E. J.. Community structure in social and biological net-works[J]. Proc. Natl. Acad. Sci. USA,2002,99(12):7821-7826.
[19]Zhou H., Distance, dissimilarity index, and network community structure[J]. Phys. Rev. E,2003,67(6):061901.
[20]Fortunato S.. Community detection in graphs[J]. Phys. Rep.,2010,486(3-5):75-174.
[21]淦文燕,赫南,李德毅等.一种基于拓扑势的网络社区发现方法[J].软件学报,2009,20(8)：2241-2254.
[22]Alon U., Network motifs:Theory and experimental approaches[J]. Nat. Rev. Genet.,2007,8:450-461.
[23]Clauset A., Moore C., Newman M. E. J.. Hierarchical structure and the prediction of missing links in networks[J]. Nature (London),2008,453(7191):98-101.
[24]Giot L., Bader J. S., Brouwer C., et al. A Protein Interaction Map of Drosophila melanogaster[J]. Science,2003,302(5651):1727-1736.
[25]Anderson R. M., May R. M., Infectious Diseases of Humans[M]. Oxford University Press,1991.
[26]Pastor-Satorras R., Vespignani A., Epidemic spreading in scale-free networks[J]. Phys. Rev. Lett.,2001,86(14):3200-3203.
[27]Albert R., Jeong H., Barabasi A.-L.. Error and attack tolerance of complex net-works[J]. Nature,2000,406(6794):378-382.
[28]Xuan Q., Du F., Wu T.-J., et al. Emergence of heterogeneous structures in chemical reaction-diffusion networks[J]. Phys. Rev. E,2010,82(4):046116.
[29]周涛,傅忠谦,牛永伟等.复杂网络上传播动力学研究综述[J].自然科学进展,2005,15(5)：513-518.
[30]Toroczkai Z.. Complex networks:The challenge of interaction topology[J]. Los Alamos Sci.,2005,29:94-109.
[31]Dorogovtsev S. N., Goltsev A. V., Mendes J. F. F.. Critical phenomena in complex networks[J]. Rev. Mod. Phys.,2008,80(4):1275-1335.
[32]Ellison N. B., Steinfield C., Lampe C.. The benefits of facebook "friends:" so-cial capital and college students'use of online social network sites[J]. Journal of Computer-Mediated Communication,2007,12(4):1143-1168.
[33]Kwak H., Lee C., Park H., et al. What is twitter, a social network or a news media?[C]//Proceedings of the 19th international conference on World wide web. New York, NY, USA:ACM,2010:591-600.
[34]Colizza V., Barrat A., Barthelemy M., et al. The role of the airline transporta-tion network in the prediction and predictability of global epidemics[J]. Proceed-ings of the National Academy of Sciences of the United States of America,2006, 103(7):2015-2020.
[35]Smith J. M., Price G. R.. The logic of animal conflict[J]. Nature,1973, 246(5427):15-18.
[36]Nowak M. A.. Five rules for the evolution of cooperation[J]. Science,2006, 314(5805):1560-1563.
[37]Ohtsuki H., Hauert C., Lieberman E., et al. A simple rule for the evolution of cooperation on graphs and social networks[J]. Nature,2006,441(7092):502-505.
[38]Zhong L.-X., Zheng D.-F., Zheng B., et al. Networking effects on cooperation in evolutionary snowdrift game[J]. Europhysics Letters,2006,76(4):724.
[39]Zhou H., Lipowsky R., Dynamic pattern evolution on scale-free networks[J]. Pro-ceedings of the National Academy of Sciences of the United States of America, 2005,102(29):10052-10057.
[40]Kleinberg J. M.,Navigation in a small world[J]. Nature,2000,406(6798):845-845.
[41]车宏安,顾基发.无标度网络及其系统科学意义[J].系统工程理论与实践,2004,44(4)：11-16.
[42]吴金闪,狄增如.从统计物理学看复杂网络研究[J].物理学进展,2004,24：18-46.
[43]汪秉宏,周涛,何大韧.统计物理学与复杂系统研究最新发展趋势分析[J].中国基础科学,2005,3：37-43.
[44]周涛,柏文洁,汪秉宏等.复杂网络研究概述[J].物理,2005,34：31-36.
[45]王飞跃.社会计算的意义及其展望[J].中国计算机学会通讯,2006,(2).
[46]李国杰.关于网络社会宏观信息学研究的一些思考[J].中国计算机学会通讯,2006,(2).
[47]程学期,陈海强,韩战钢.社会信息的网络化分析初探[J].中国计算机学会通讯,2006,(2).
[48]汪秉宏,周涛,王文旭等.当前复杂系统研究的几个方向[J].复杂系统与复杂性科学,2008,5(4)：21-28.
[49]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社,2006.
[50]郭雷,许晓鸣.复杂网络[M].上海：上海科技教育出版社,2006.
[51]陈关荣,许晓鸣.复杂网络理论及应用[M].上海：上海系统科学出版社,2008.
[52]何大韧,刘宗华,汪秉宏.复杂系统与复杂网络[M].北京：高等教育出版社,2008.
[53]刘建香.复杂网络及其存国内研究进展的综述[J].系统科学学报,2009,17(4)：31-37.
[54]Newman M. E. J., Leicht E. A., Mixture models and exploratory analysis in net-works[J]. Proc. Natl. Acad. Sci. USA,2007,104(23):9564-9569.
[55]Eckmann J.-P., Moses E.. Curvature of co-links uncovers hidden thematic layers in the World Wide Web[J]. Proc. Natl. Acad. Sci. USA,2002,99(9):5825-5829.
[56]Guimera R., Amaral L. A. N.. Cartography of complex networks:modules and universal roles[J]. J. Stat. Mech.:Theor. Exp.,2005,2005(02):P02001.
[57]Spielman D. A.. Spectral graph theory and its applications[C]//FOCS'07:Proceed-ings of the 48th Annual IEEE Symposium on Foundations of Computer Science. Washington, DC, USA:IEEE Computer Society,2007:29-38.
[58]Middendorf M., Ziv E., Wiggins C. H.. Inferring network mechanisms:The Drosophila melanogaster protein interaction network[J]. Proc. Natl. Acad. Sci. U S A,2005,102(9):3192-3197.
[59]Przulj N., Corneil D. G., Jurisica I.. Modeling interactome:scale-free or geomet-ric?[J]. Bioinformatics,2004,20(18):3508-3515.
[60]Przulj N.. Biological network comparison using graphlet degree distribution[J]. Bioinformatics,2007,23(2):e177-e183.
[61]Memisevic V., Milenkovic T., Przulj N.. An integrative approach to modelling biological networks[J]. J. Integr. Bioinform.,2010,7(3):120.
[62]Stark C., Breitkreutz B.-J., Reguly T., et al. BioGRID:a general repository for interaction datasets[J]. Nucl. Acids Res.,2006,34:D535-539.
[63]Jeong H., Mason S. P., Barabasi A.-L., el al. Lethality and centrality in protein networks[J]. Nature,2001,411(6833):41-42.
[64]Barabasi A.-L., Oltvai Z. N.. Network biology:understanding the cell's functional organization [J]. Nat Rev Genet,2004,5(2):101-113.
[65]Milo R., Shen-Orr S., Itzkovitz S., etal. Network Motifs:Simple Building Blocks of Complex Networks[J]. Science,2002,298(5594):824-827.
[66]Sole R. V., Pastor-Satorras R., Smith E., et al. A model of large-scale proteome evolution[J]. Adv. Complex Syst.,2002,5(1):43-54.
[67]Vazquez A., Flammini A., Maritan A., et al. Modeling of protein interaction networks[J]. ComPlexUs,2003, 1(1):38-44.
[68]Berg J., Lassig M., Wagner A., Structure and evolution of protein interaction networks:a statistical model for link dynamics and gene duplications[J]. BMC Evol.Biol.,2004,4(1):51.
[69]Ohno S., Evolution by gene duplication[M]. Germany:Springer-Verlag Heidelberg: Springer,1970.
[70]Wagner A., How the global structure of protein interaction networks evolves[J]. Proc. R. Soc. Lond. B Biol. Sci.,2003,270(1514):457-466.
[71]Thorelli H. B., Networks:Between markets and hierarchies[J]. Strategic Manage-ment Journal,1986,7(1):37-51.
[72]Rauch J. E., Business and social networks in international trade[J]. Journal of Economic Literature,2001,39(4):1177-1203.
[73]Liljeros F., Amaral L. A. N., Stanley H. E., et al. The web of human sexual contacts[J]. Nature,2001,411:907-908.
[74]Schena M., Shalon D., Davis R. W., et al. Quantitative monitoring of gene expression patterns with a complementary dna microarray[J]. Science,1995, 270(5235):467-470.
[75]Fields S., Song O.-k.. A novel genetic system to detect protein-protein interac-tions[J]. Nature,1989,340:245-246.
[76]Lockhart D. J., Winzeler E. A.. Genomics, gene expression and dna arrays[J]. Nature,2000,405:827-836.
[77]P. U.. Systematic and large-scale two-hybrid screens[J]. Current Opinion in Micro-biology,2000,3:303-308.
[78]Barabasi A.-L.. Network medicine—from obesity to the "diseasome"[J]. New England Journal of Medicine,2007,357(4):404-407.
[79]Albert R.. Scale-free networks in cell biology[J]. Journal of Cell Science,2005, 118(21):4947-4957.
[80]Oltvai Z. N., Barabasi A.-L.. Life's complexity pyramid[J]. Science,2002, 298(5594):763-764.
[81]Paine R. T.. Food webs:Linkage, interaction strength and community infrastruc-ture [J]. Journal of Animal Ecology,1980,49(3):666-685.
[82]Newman M. E. J., Strogatz S. H., Watts D. J.. Random graphs with arbitrary degree distributions and their applications[J]. Phys. Rev. E,2001,64(2):026118.
[83]Garfield E.. It's a small world after all [J]. Current Contents,1979,43:5-10.
[84]Watts D. J., Dodds P. S., Newman M. E. J.. Identity and search in social net-works[J]. Science,2002,296(5571):1302-1305.
[85]Clauset A., Shalizi C. R., Newman M. E. J.. Power-law distributions in empirical data[J]. SIAM Rev.,2009,51:661-703.
[86]Jeong H., Tombor B., Albert R., et al. The large-scale organization of metabolic networks[J]. Nature,2000,407(6804):651-654.
[87]Flake G. W., Lawrence S., Giles C. L., et al. Self-organization and identification of web communities[J]. IEEE Computer,2002,35(3):66-71.
[88]Guimera R., Amaral L. A. N.. Functional cartography of complex metabolic net-works[J]. Nature,2005,433(7028):895-900.
[89]Palla G., Derenyi I., Farkas I., et al. Uncovering the overlapping community struc-ture of complex networks in nature and society[J]. Nature,2005,435(7043):814-818.
[90]Lancichinetti A., Kivela M., Saramaki J., et al. Characterizing the community structure of complex networks[J]. PLoS ONE,2010,5(8):e11976.
[91]Newman M., Detecting community structure in networks[J]. The European Physi-cal Journal B-Condensed Matter and Complex Systems,2004,38:321-330.
[92]Rosvall M., Bergstrom C. T.. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences,2008, 105(4):1118-1123.
[93]Vespignani A., Evolution thinks modular[J]. Nat Genet,2003,35(2):118-119.
[94]Wuchty S., Oltvai Z. N., Barabasi A.-L.. Evolutionary conservation of motif constituents in the yeast protein interaction network[J]. Nat Genet,2003,35(2):176-179.
[95]Heath A. P., Kavraki L. E.. Computational challenges in systems biology[J]. Com-puter Science Review,2009,3(1):1-17.
[96]Wormald N. C., Models of random regular graphs[G]//Lamb J. D., Preece D. A. . Surveys in Combinatorics,1999. vol 267. Cambridge, UK:Cambridge University Press,1999:239-298.
[97]Hu Y., Wang Y., Li D., et al. Possible origin of efficient navigation in small worlds[J]. Phys. Rev. Lett.,2011,106(10):108701.
[98]Korniss G., Novotny M. A., Guclu H., et al. Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations [J]. Science,2003,299(5607):677-679.'
[99]Guclu H., Korniss G., Novotny M. A., et al. Synchronization landscapes in small-world-connected computer networks[J]. Phys. Rev. E,2006,73(6):066115.
[100]Li W., Kurata H.. Visualizing global properties of large complex networks[J]. PLoS ONE,2008,3(7):e2541.
[101]Knuth D.E.. The Art Of Computer Programming[M]. thirdth ed. Boston:Addison-Wesley:,1997.
[102]Chandler D., Introduction to modern statistical mechanics[M]. Oxford University Press,1987.
[103]Molloy M., Reed B., The size of the giant component of a random graph with a given degree sequence[J]. Combin. Probab. Comput.,1998,7(3):295-305.
[104]Isaacson E., Keller H. B., Numerical Analysis[M]. New York:John Wiley& Sons, 1966.
[105]Richard L. Burden J. D. F., Numerical Analysis[M]. Eighthth ed.:Brooks Cole, 2004.
[106]Lakhina A., Byers J. W., Crovella M., et al. Sampling biases in ip topology measurements[C]//INFOCOM 2003:Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ, USA:IEEE Press,2003:332-341.
[107]Petermann T., De Los Rios P.. Exploration of scale-free networks:Do we measure the real exponents?[J]. Eur. Phys. J. B,2004,38(2):201-204.
[108]Clauset A., Moore C.. Accuracy and scaling phenomena in internet mapping[J]. Phys. Rev. Lett.,2005,94(1):018701.
[109]Achlioptas D., Clauset A., Kempe D., et al. On the bias of traceroute sampling: or, power-law degree distributions in regular graphs[C]//STOC'05:Proceedings of the 37th ACM Symposium on Theory of Computing. New York, NY, USA:ACM Press,2005:694-703.
[110]Dall'Asta L., Alvarez-Hamelin I., Barrat A., et al. Exploring networks with traceroute-like probes:Theory and simulations[J]. Theor. Comput. Sci.,2006, 355(1):6-24.
[111]Toroczkai Z., Bassler K. E.. Network dynamics:Jamming is limited in scale-free systems[J]. Nature (London),2004,428:716-716.
[112]Toroczkai Z., Kozma B., Bassler K. E., et al. Gradient networks[J]. J. Phys. A: Math. Theor.,2008,41(15):155103.
[113]Kalisky T., Sreenivasan S., Braunstein L. A., et al. Scale-free networks emerging from weighted random graphs[J]. Phys. Rev. E,2006,73(2):025103(R).
[114]Chklovskii D. B., Schikorski T., Stevens C. F., Wiring optimization in cortical circuits[J]. Neuron,2002,34:341-347.
[115]Onnela J.-P., Fenn D. J., Reid S., el al. A taxonomy of networks. http://arxiv.org/abs/1006.5731vl[J].2010.
[116]Ispolatov I., Krapivsky P. L., Yuryev A.. Duplication-divergence model of protein interaction network[J]. Phys. Rev. E,2005,71(6):061911.
[117]Li S., Armstrong C. M., Bertin N., el al. A map of the interactome network of the metazoan c. elegans[J]. Science,2004,303(5657):540-543.
[118]Costa L. d. F., Rodrigues F. A., Travieso G., et al. Characterization of complex networks:A survey of measurements [J]. Advances in Physics,2007,56(1):167-242.
[119]Filkov V., Saul Z. M., Roy S., et al. Modeling and verifying a broad array of network properties[J]. Europhysics Letters,2009,86(2):28003.
[120]Wiuf C., Brameier M., Hagberg O., et al. A likelihood approach to analysis of network data[J]. Proc. Natl. Acad. Sci. USA,2006,103(20):7566-7570.
[121]Leskovec J., Chakrabarti D., Kleinberg J., et al. Kronecker graphs:An approach to modeling networks[J]. J. Mach. Learn. Res.,2010,11:985-1042.
[122]Yu J., Pacifico S., Liu G., et al. Droid:the drosophila interactions database, a com-prehensive resource for annotated gene and protein interactions [J]. BMC Genomics, 2008,9(1):461.
[123]Rain J. C., et. al. The protein-protein interaction map of helicobacter pylori[J]. Nature,2001,409(6817):211-215.
[124]Xiong A.-S., Peng R.-H., Zhuang J., et al. Gene duplication, transfer, and evolution in the chloroplast genome[J]. Biotech. Adv.,2009,27(4):340-347.
[125]Cvetkovic D. M., Rowlinson P., Simic S.. Eigenspaces of graphs[M]. Cambridge University Press,1997.
[126]Bishop C. M., Pattern recognition and machine learning[M]. Springer,2006.