（应用数学专业论文）生物网络的dd模型构建.pdf

原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除了文中特别 加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果参与 同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意 娣诌被悸啉川，w i 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即t 学校有权保留论 文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容 ( 保密的论文在解密后应遵守此规定) 躲7 气积洚獬；纠耀萋啉蹴沙 上海大学理学硕士学位论文 生物网络的d d 模型构建 作者：许醇穗 导师：刘曾荣教授 专业：应用数学 上海大学理学院 二零一零年三月 ad i s s e r t a t i o ns u b m i t t e dt os h a n g h a iu n i v e r s i t y f o rt h ed e g r e eo fm a s t e ri ns c i e n c e ddm od e l si nb i o l o g i c a ln e t w o r k s m d c a n d i d a t e ：x uc h u n s u i s u p e r v i s o r ：p r o f e s s o rl i uz e n g r o n g m a j o r ：a p p l i e dm a t h e m a t i c s c o l l e g eo fs c i e n c e s ，s h a n g h a iu n i v e r s i w m a r c h ，2 0 1 0 摘要 本文主要从生物学进化论基本原则复制和变异出发来构建生物 网络模型，并对其拓扑性质尤其是度的负关联性进行研究在第一章引言 部分对系统生物学、复杂网络以及生物网络作了介绍，着重介绍了描述复 杂网络的拓扑量以及现有实测结果表明的生物网络的性质在第二章中， 我们着重和讨论了生物网络的个重要拓扑性质度的负关联性为了 弄清楚负关联性与这两个基本准则的相互关系和研究生物网络中度关联的 起因，我们分别讨论了复制和各种变异对度负关联性产生影响，在前人得 到复制对于度负关联的产生是有较大影响基础上，研究各种变异行为对度 负关联性的影响，这种影响有正面的也有负面的在第三章中，结合现有 生物上测得的真实数据，构造了四种不同类型的d d 模型方案从模拟结 果来看，我们发现第一种方案与现有的实例生物网络的统计数据量更为接 近对此模型，按照最新的研究结果，我们作了修改，得出了更为理想的混 合d d 模型，该模型很好地给出了生物网络的各种实测性质第四章则是 对本文的一个扼要总结，并对进一步的研究做了一些展望 关键词s系统生物学，复杂网络，生物网络，复制，变异，度的负关联 性，d d 模型 a b s t r a c t t h i st h e s i si sd e n o t e dt od e v e l o p i n gt h eb i o l o g i c a ln e t w o r km o d e l sb a s e d o nd u p l i c a t i o na n d d i v e r g e n c ea p p l y i n gt h et h e o r yo fd a r w i ne v o l u t i o n i s m a n ds t u d y i n gt h e i rt o p o g i c a lp e r p c r t i e se s p e c i a l l yt h ed i s a s s o r t a t i v em i x i n g p r o p e r t y i nc h a p t e r1 ，w em a i n l yi n t r o d u c e8 0 m eb a c k g r o u n dk n o w l e d g e o fs y s t e m sb i o l o g ya n dc o m p l e x n e t w o r k s ，e s p c c i a l l yt h et o p o l o g i c a lp a r a m - e t e r sw h i c hd e c r i b ec o m p l e xn e t w o r k sa n dt h et o p o l o g i c a lc h a r a c t e r i s t i c s o fb i o l o g i c a ln e t w o r k sp r o v e db ye x p e r i m e n t a lo b s e r v a t i o n s i nc h a p t e r 2 ，w ef o c u so na n dd i s c u s sa x li m p o r t a n tt o p o l o g i c a lp r o p e r t yo ft h eb i o - l o g i c a ln e t w o r k s - 。t h ed i s a s s o r t a t i v em i x i n gp r o p e r t y i no r d e rt om a k e c l e a rt h er e l a t i o n s h i pb e t w e e nt h ed i s a s s o r t a t i v em i x i n gp r o p e r t ya n dt h e t w ob a s i cb i o l o g i c a lp r i n c i p a l sa n dt os t u d yt h ec a u s eo ft h ed i s a s s o r t a t i v e m i x i n gp r o p e r t yi nb i o l o g i c a ln e t w o r k s ，w ed i s c u s sh o wd u p l i c a t i o na n dv a r - i o u sd i v e r g e n c ei n f l u e n c et h ed i s a s s o r t a t i v em i x i n gp r o p e r t y o nt h eb a s i s t h a td u p l i c a t i o nh a v eg r e a ti m p a c to nt h ed i s a s s o r t a t i v em i x i n gp r o p e r t y , w ed i s c u s sh o wt h ed i v e r g e n c em e c h a n i s mi n f l u e n c e st h ed i s a s s o r t a t i v em i x - i n gp r o p e r t y , w h i c hh a v ep o s i t i v eo rn e g a t i v ei m p a c t i nc h a p t e r3 ，w e p r o p o s ef o u rt h e m eo fd dm o d e l sb a s e do fd u p l i c a t i o na n dd i v e r g e n c ee x - p e r i m e n tr e s u l t s o u rn u m e r i c a lr e s u l t sh a v es h o w nt h a tt h ef i r s tt h e m eo f d dm o d e lr e p r o d u c em a n yo ft h er e g u l a r i t i e so b s e r v e di nt h er e a lp r o t e o m e d a t a w em o d i f i e dt h em o d e lw i t hr e c e n t l yr e p o r tf u r t h e r w eb c h e v et h a t o u rr e s e a r c hr e s u l t sw i l lh a v eac e r t a i ni n s p i r a t i o nt ob u i l d i n gt h eb i o l o g i c a l n e t w o r k so ft h el i f ep r o c e s s e sr e s e a r c h l a s t l y , i nc h a p t e r4 ，w em a k ea b r i e fs u m m a r yo nt h i st h e s i sa n dp r o s p e c tf o rf u r t h e rr e s e a r c ho nr i d d e d p r o p e r t y k e yw o r d s ：s y s t e mb i o l o g y , c o m p l e xn e t w o r kt h e o r y , b i o l o g i c a ln e t w o r k s ，d u p l i c a t i o n ，d i v e r g e n c e ，d i s a s s o r t a t i v em i x i n gp r o p e r t y , d dm o d e l 目录 第一章引言 1 1 1 系统生物学的兴起与生物研究的新方式网络 1 1 1 1 生物学的发展进入系统水甲 1 1 1 2 数学建模方法， 3 1 1 3 生物研究的新方式复杂网络4 1 。2 复杂网络简介及基本理论 5 1 2 1 复杂网络简介 5 1 2 2 复杂网络的基本理论 8 1 3 生物网络的基本特征和构建方法1 2 1 3 1 生物网络的基本特征1 2 1 3 2 生物网络的构建方法1 5 1 4 本文研究的主要内容1 6 第二章从生物进化论探讨生物网络的度负关联性 1 8 2 1 问题的提出及研究现状1 8 2 2 复制模型 5 8 】1 9 2 2 1 随机复制模型1 9 2 2 2 偏爱复制模型2 1 2 2 3 小结。2 2 2 3 变异模型2 3 2 3 1 节点删除变异模型2 3 2 3 2 删边变异模型2 5 2 3 3 加边变异模型2 7 2 3 4 重组边变异模型3 0 2 3 5 小结3 1 第三章 从进化论构建一般生物网络 3 3 3 1 复制与变异的有关生物数据3 3 3 2 我们的模型3 5 3 2 1 第一种方案3 5 3 2 2 第二种方案。3 6 3 2 3 第三种方案3 7 3 2 4 第四种方案3 9 3 3 数值结果与分析4 0 3 4 小结4 5 第四章总结与展望 4 6 4 1 本文的总结4 6 4 2 本文的展望4 6 参考文献49 作者在攻读硕士学位期间公开发表和已投稿的学术论文5 6 致谢5 7 第一章引言 1 1系统生物学的兴起与生物研究的新方式网络 1 1 1 生物学的发展进人系统水平 2 0 世纪分子生物学的诞生使传统生物学研究转变为现代实验科学生物学经 历了由宏观到微观的发展过程，由形态、表型的描述逐步分解、细化到生物体的各 种分子及其功能的研究，进入了对生命现象进行定量描述的阶段1 9 5 3 年w a t s o n 和c r i c k 提出d n a 双螺旋结构模型，成为生物学发展史上的一个里程碑，使得对 生物学的认识进入到分子水平，生物学开始进入了分子生物学时代1 9 9 0 年启动 的人类基因组计划是生命科学史上第一个大科学工程，开始了对生物全面、系统研 究的探索；1 9 9 4 年澳大利亚m a c q u a r i c 大学的w i l k i n 和w i l l i a m s 首先提出了蛋 白质组( p r o t e o m e ) 的概念2 0 0 3 年已完成了人和各种模式生物体基因组的测序， 第一次揭示了生命起源的密码基因组计划的成功使我们了解了包括大肠杆菌、酵 母、线虫、果蝇、小鼠等模式生物和人类的所有遗传信息的组成，大规模的基因和 这些基因产物的功能基因表达图谱蛋白质组学的发展使得我们对生物系统所有蛋 白质的组成和相互作用关系有了更深入的了解，基因组学和蛋白质组学中的高通量 测量方法为系统生物学的发展提供了大量的数据计算生物学通过数据处理、模型 构建和理论分析，成为系统生物学发展的一个必不可缺、强有力的工具分子生物 学的发展历经了半个世纪，随着人类基因组计划等的进展，如今生命科学步入了功 能基因组时代其特点是，生物学的研究从分解到整合，从整体水甲或系统水平上 去认识生物体的结构和功能，由此生物学在基因组学、蛋自质组学等新型大科学发 展的基础上孕育了系统生物学【1 】 传统分子生物学研究的对象一般局限子生物个体分子，通过纵深解析系统的特 定基因或者蛋白质，从而推演生命现象的物质基础和生命过程的基本活动规律【2 】 随着分子生物学的诸多发展引人注目，对生物个体的研究进展到一定深度之后，由 于未考虑到生物体内部成分之间的作用和层次性关联，以及生物体与外部环境的相 互影响，因此在进一步探讨生物系统的整体性质和功能时，分子生物学便显得力不 从心实际上，作为复合体的生物系统具有相当的复杂性在个生物系统哪怕是 生物体的最小基本结构单位细胞内部般包含了大量的个体，而且生物体系 】 2 生物网络的d d 模型构建 统具有很明显的层次性，例如生物体一器官一组织一细胞一细胞器，多个体、多 层次之间具有非线性的相互作用另外，生物体系统作为开放的复杂系统，其行为要 受到外界环境条件的约束，体现的生命现象不是个静态的过程，而是一直处于动 态的发展演化之中例如，生物体系统的免疫行为就不是某个机体或基因一开始就 控制好的结果，而是源于系统的多个基因、蛋白质和机体的相互作用，以及受到系 统外界环境的影响，在这些因素的协同作用下，生物体才在特定的时间和场合，产 生出应对于某项传染和疾病的免疫生物体在系统内部的个体相互作用以及系统外 部的环境变化的双重影响下，整体上会涌现出大量新的非线性性质，诸如分岔、滞 后、适应等研究这些多个体的复杂系统，讨论从局部到整体所涌现出来的各类非 线性性质，在分子生物学的理论背景下，科学家们很自然地提出采用系统科学相关 的方法和技术手段，对生物体系统进行全面的深入研究这样，基于复杂性理论的思 想和成果，在系统科学与生物科学的交叉领域内，一种应用系统科学的思想和方法 来探讨各种生命现象的、理论和实验相结合的学科系统生物学应运而生【3 】3 系统生物学研究的重要内容是对各种组学( 基因、转录、蛋白质、代谢、相互作 用、表型的组学) 的研究系统生物学是在整体水平上研究生命现象的科学【4 】以 系统的观点，研究生物系统中所有组成成分( 基因、m r n a 、蛋白质等) 的构成， 以及特定条件下这些组分间的相互关系的学科，从分子、细胞、器官到机体和从个 体、群体到生态系统的不同层次上生物信息的整合和定量化在分子水平上，系统 生物学利用各种基因组学和蛋白质组学的技术，来研究生物种属问分子影响差异， 从而外推环境化学在种属问作用过程，建立数学模式评估m r n a 、蛋白质、代谢 水平的变化或差异，阐明整体生物学效应系统生物学将生物学由描述式的科学转 变为定量描述和能预测的科学，从系统层次对生物系统的模拟、控制和设计将为系 统水平的治疗手段提供基础它在优良种质资源培育、预防医学、疾病防治、新药 研发、促进健康、提高生命质量和延长寿命等方面有着广阔的应用前景不仅推动 生命科学和生物技术的发展，而且对整个国民经济、社会和人类本身产生重大和深 远的影响f 1 】 系统生物学的另一个重要特点在于，它是一门交叉学科，需要综合生命科学、 信息科学、数学及计算机科学等多门学科的知识和技能系统生物学的研究必须依 赖于分子生物学所提供的反应各种生命活动的大量资料和数据，通过计算机技术编 码成数字信息来理解，而信息的传导过程和反馈调节、输人输出的变量控制等，都对 2 0 1 0 年上海大学硕士学位论文 3 应了生物体特定的响应机制，系统生物学就要依据信息科学的理论方法对这些机制 加以功能上的识别在这些过程中，数学上的抽象贯穿始末，通过数学建模方法。 对生物体系统的各种动力学行为进行计算机模型模拟和理论分析，则是系统生物学 不可或缺的研究手段【3 1 从系统生物学研究机构和几次国际学术会议看，系统生物学的研究内容涉及到 生物学的各个方面，我们阅读到有：蛋白质组学、转录组学、遗传网络、代谢网络、 发育、空间、结构系统生物学、硅细胞、超细胞系统生物学、计算生物学、软件构 架、系统生物学研究的软件平台、系统分析、模式识别、动力系统理论和代谢控制 分析采用的模式生物和模式细胞有。嗜盐菌、酵母、海胆、果蝇、鼠干细胞等；生 物体系有。过氧化酶、半乳糖利用、发育，免疫、核一质转移等；联系的疾病有。 传染病如艾滋病、自身免疫性疾病和炎症、糖尿病、心脏病、肿瘤等【5 】 作为人类基因组计划的发起人之一，美国科学家莱诺伊胡德( i c r o yh o o d ) 也 是系统生物学的创始人之一胡德认为“系统生物学将是2 1 世纪医学和生物学的 核心驱动力”基于这一信念，胡德在1 9 9 9 年年底辞去了美国西雅图市华盛顿大学 的职务，创立了世界上第一个系统生物学研究所( i n s t i t u t cf o rs y s t e m sb i o l o g y ) 系统生物学开始引起了广泛的关注美国加州理工学院、麻省理工学院和哈佛大学 等纷纷成立了系统生物学研究机构我国学者也注意到这一趋势，相继成立了系统 生物学研究机构，如中国科学院生物物理研究所于2 0 0 3 年成立了系统生物学研究 中心，上海交通大学、中国科技大学也相继成立了系统生物学研究中心或系【5 】5 上海大学系统生物技术研究所也于2 0 0 6 年1 1 月成立 1 1 2 数学建模方法 在系统科学分析实际问题时，数学模型方法一向是运用得比较多的采用模型 方法来解释生物现象，可以描述和预测生物系统响应外界环境变化和内在遗传结构 变化时的动态行为，以获得对于生物体系统更加全面的认识例如蛋白质在一定条 件下发生结构变化时，通过测量我们只能获得变化前后两个稳态的数据，而建立相 应的模型可以了解到变化中间状态的全过程对生物体建立模型进行模拟，通常需 要考虑到生物体的复杂性、生物的环境适应能力和生物的进化作用等几个方面生 物系统中的模型一样可以分为定性模型和定量模型定性模型一般是在假设驱动的 基础上，对系统的定性性质进行模拟，比如基因的信号转导通路模型建立定量模型 4 生物网络的d d 模型构建 则要基于高通量的测量技术，要求实验室提供精确的数据来源定量模型可以记录 某一生物系统或生物反应的量变过程，有助于研究多因素作用下的生物反应过程， 在应用到疾病研究时，能极大地提高新药开发及诊治疾病的效力目前的系统生物 学研究，还只是刚开始接触使用动力学建模方法来定量地表现生物体系统的动态演 化情况，建模中常用到的数学方法有权重矩阵、非线性微分方程、随机动力学分析 等而把生物体作为复杂适应性系统，应用复杂网络理论、遗传算法等，可对生物 体系统的定量行为提供更多的描述和解释【3 】 1 1 3 生物研究的新方式复杂网络 存在多个体、多层次的之间的非线性的相互作用的生物系统必定具有相当的复 杂性生物系统是一种复杂系统，复杂系统的一个显著特点是，多个参与者相互作 用复杂网络由点和连线( 边) 组成，“点”可代表系统中的参与者，“连线”( 边) 代表相互作用因此，可用复杂网络描述复杂系统，特别是能够揭示复杂系统的拓 扑结构对于多个体的相互作用，我们通常采用关注众多变量的关键部分和统计性 质，约化模型降低复杂性但是这种方法具有局限性，它忽略了系统层次结构对系 统整体的影响最近兴起的复杂网络理论为我们探索各类复杂系统提供了个全新 的视角【3 】3 复杂网络理论利用构建网络的方法，将复杂网络的成分关系以及分布和 集团特性来获得对现实系统更多的认识通常，我们研究的复杂网络有以下几种t 社会网络、信息网络、科技网络和生物网络复杂网络理论在生物方面的应用可以 视为系统生物学的一个新的理论分支 网络和系统之间存在着一种相互对应的关系一个网络可以看做是一个系统 ( 网络的节点是子系统或元素，网络的边是其相互关系) ，可以用系统科学的思想和 理论去处理；同时，一个系统也可以抽象成一个网络( 系统包含的个体作为节点， 个体问的相互作用确定为边) ，可以借助网络的概念、属性和复杂网络研究的各种 方法来理解系统的演化和行为对生物系统而言，使用。节点边“的语言很容 易将分子间生理上的相互作用加以抽象，形成各种网络来探讨其生理行为现在经 常讨论的生物网络主要有。蛋白质相互作用网络、基因调控网络、新陈代谢网络、 食物网、神经网络、血管( 脉管) 网络等等在代谢途径网络中，如将小分子的酶解 物看作是个代谢网络的结点，而将酶催化反应作为边，由于代谢过程中的许多反 应是不可逆的，还可以给边定义相应的方向，这样就构建了个有向的代谢网络； 2 0 1 0 年上海大学硕士学位论文 5 如果考虑结点或边的异质性，可以给不同结点或边赋予一定的权重值，从而构建出 加权网络【3 1 在蛋白质相互作用网络中，节点和边分别代表蛋白质和它们之间的 相互作用，它是一个无向网络 当前，复杂网络的研究正在蓬勃发展，并取得了许多重要成果，其中与生物学 相交叉的生物网络已经是复杂网络研究的一个重要方面复杂网络与生物学交叉， 为生物学的研究提供了一个新的视野，一种新的研究途径把生物系统抽象为生物 网络，然后用复杂网络理论和方法进行研究，已成为系统生物学研究的主要方法之 一随着探索复杂网络理论热潮的兴起，关于生物网络的研究近两年来的发展也相 当迅速，特别集中于探索活细胞中所有分子的行为和它们之间的相互作用，以及从 局部到整体，生物体如何形成了极其复杂的动力学机制 1 2 复杂网络简介及基本理论 1 2 1 复杂网络简介 自然界和人类社会中存在的大量复杂系统可以通过形形色色的复杂网络加以描 述个典型复杂网络( c o m p l e xn e t w o r k s ) 由许多节点与连接节点之间的边组成， 其中节点用来代表真实系统中不同的个体，边代表各个个体之间的相互作用，每个 节点都有自身的动力学行为英特网、万维网、超文本传输协议、食物链网络、基 因网络、蛋白质网络、无线通讯网络、高速公路网、航空线路网、电力网络、神经网 络、超大规模集成电路、人体细胞代谢网络、流行病传播网络等都是复杂网络近 几年来，复杂网络引起了许多相关领域研究人员的关注当前，我们还在继续建立 和扩展各种复杂网络，如能源供应网络、交通网、信息网，金融网等这些网络与我 们的日常生活密切相关，这就需要我们深入研究和理解这些复杂网络的拓扑结构、 运行机制、动力学行为、抗干扰能力等，以便更好的设计和管理这些实际的复杂网 络复杂网络的研究正渗透到从物理学到生物学的众多不同的学科深入探索和科 学理解复杂网络的定性特征、定量规律、动力学行为以及其上的信息传输，已成为 网络时代复杂性科学研究中一个极其重要的挑战性课题因此，复杂网络将是今后 若干年内涉及到的许多研究领域发展的一个主流方向正如当代最富有影响之一的 科学家史蒂芬霍金( s t c p h e nh a w k i n g s ) 在2 0 0 0 年所指出的t 。我认为，2 1 世纪 将是复杂性的世界( it h i n kt h en e x tc e n t u r yw i l lb et h ec e n t u r yo fc o m p l e x i t y ) ” 6 生物网络的d d 模型构建 复杂网络的研究大致可以描述为三个密切相关但又依次深入的方面：首先是大 量的真实网络的实证研究，分析真实网络的统计特性；其次是研究真实网络的形成 机制和内在机理，从而提出构建网络的演化法则，并用此法则构造出符合真实网络 统计性质的复杂网络；第三点是研究网络上的动力学行为，如网络的鲁棒性和同步 能力，网络的拥塞及网络上的传播行为等 当把一个系统描述为网络的形式后，就可以用图论的理论分析网络的统计性 质，如用网络的平均路径长度、度分布、聚类系数、相关系数、介数等来描述网络 【6 - 1 1 】大量网络的统计性质的实证研究表明许多真实世界的网络具有两个基本性 质l 小世界特性( s m a l l - w o r l dc h a r a c t e r ) 【1 2 1 和无标度特性( s c a l e - f r e ec h a r a c t e r ) 【13 】 小世界特性是指与相同规模的随机网络相比，该网络具有较小的平均路径长度 和较大的聚类系数1 9 6 7 年，美国哈佛大学社会心理学家s t a n l e ym i l g a m 做了一 个实验，在美国将一封信通过熟人找熟人的方式传递到目标者，发现平均最多经过 6 人就可到达，这就是著名的“六度分离( s i xd e g r e eo fs e p a r a t i o n ) ”现象，它揭 示了社会网络的小世界特性而在互联网( w w w ) 中，平均只需点击1 9 次超级链 接，就可以从任意个网页到达其它网页【1 4 1 大量的小世界网络的普遍存在，促使人们探讨形成这种网络的内在机理1 9 9 8 年，w a t t s 和s t r o g a t z 通过以某个很小的概率切断规则网络中原始的边，并随机选 择新的端点重新连接，构造出了一种介于规则网络和随机网络之间的网络( w s 网 络) ，它同时具有大的聚类系数和小的平均路径长度，因此既不能当作规则网络处 理，也不能被看作是随机网络【l2 】随后，n e w m a n 和w a t t s 给出了一种新的网 络的构造方法，在他们的网络( n w 网络) 中，原有的规则连边并不会被破坏，平均 路径长度的缩短源于以个很小的概率在原来的规则网络上添加新的连边1 1 2 】后 来物理学家把大的聚类系数和小的乎均路径长度两个统计特征合在一起称为小世界 效应，具有这种效应的网络就是小世界网络( s m a l l - w o r l dn e t w o r k s ) 除了大量的网络都具有小世界效应特性外f 1 2 ，1 6 - 2 0 】，科学家还发现大量真实 网络的节点度分布服从幂率分布【1 6 ，1 8 ，2 0 - 2 2 】，这里某节点的度是指该节点拥有相 邻节点的数目，或者说与该节点关联的边的数目节点度服从幂律分布就是说具有 某个特定度的节点数目与这个特定的度之间的关系可以用个幂函数近似地表示 幂函数曲线比起指数函数曲线来说，是一条下降相对缓慢的曲线，这使得度很大的 2 0 1 0 年上海大学硕士学位论文 7 节点可以在网络中存在对于随机网络和规则网络，度分布区间非常狭窄，几乎找 不到偏离节点度均值较大的点。故其甲均度可以被看作其节点度的一个特征标度 从这个意义上讲，这些网络度分布为均匀，而具有幂律分布的网络显然不具有这种 性质，它的度分布有明显的非均匀性在这个意义上，我们把节点度分布服从幂律 分布的网络叫做无标度网络( s c a l e - 行e en c t w o r k s ) ，并称这种节点度的幂律分布为 网络的无标度特性 1 9 9 9 年，b a r a b h s i 和a l b e r t 给出了构造无标度网络的演化模型【1 3 ，2 3 】，把 系统通过自组织生成无标度的网络归功于两个主要因素：生长和优先连接，而他们 的网络模型( b a 网络) 正是模拟这两个关键机制设计的b a 模型具有以下两个重 要性质。 ( 1 ) 增长性。考虑开始有m o 个节点，随着时间的演化新的节点不断的加入网 络，同时这个新节点连接到网络中仇m o 个已经存在的节点上； ( 2 ) 偏爱性选择s 一个新的节点选择连接节点时有偏好的，它选择某个节点i 的 概率正比于这个节点i 的度，即p i = f 如 b a r a b d s i 和a l b c r t 的研究表明，网络最终会演化成一个标度不变的状态，网络 的度分布服从幂律，少数节点有大量的连接，而大多数节点只有很少的连接b a 模型不仅是人们构造出的第个具有无标度性质的网络，更精彩的是把很多实际复 杂网络的无标度特性，归结为增长和偏爱选择这两个简单的机制，很好的体现了科 学研究中从复杂现象中提取简单本质的特点之后的研究表明，许多社会网络如科 学家合作网络、生物网络中的新陈代谢网络【2 0 】、技术网络中的i n t c r n e t 网络等都 是无标度网络这些来自不同领域的大规模系统呈现了共同的普适规律，促使人们 去探索隐藏在这些表象后的内在演化机制，从此掀起了研究复杂网络的热潮 随着近年来大型数据库的建立和计算机存储与运算能力的迅速提高，复杂网络 的研究进程大大加快人们对社会系统、大型基础性设 沲和生物系统中大量的真实 网络数据库进行了系统的分析，寻找呈现表象的内在机制和模式，试图发现支配和 影响这些复杂系统的动力学和演化规律的内在本质复杂网络的理论及实证研究的 发展将会对网络安全、网络控制、疾病传播的控制与防御、社会中人的行为动力学 的研究、生物网络的演化机制的研究等产生重要影响 8 生物网络的d d 模型构建 1 2 2 复杂网络的基本理论 在图论中，一个具体的网络可以抽象为由点集y 和边集e 组成的图g = ( ke ) ，其中节点数记为n = i v l ，边数记为m = i e l ，边集e ( g ) 中的每条边 都有点集v ( g ) 的一对点与之对应若点对( ，j ) 与( j ，i ) 对应同一条边，则为无 向网络( u n d i r e c t e dn e t w o r k ) ，否则为有向网络( d i r e c t e dn e t w o r k ) ；若每条边都有 各自相应的权值即为加权网络( w e i g h t e dn e t w o r k ) ，否则为无权网络( u n w c i g h t e d n e t w o r k ) 同时，个网络中还可能包含不同类型的节点，如有不同类型的节点有不 同的动力学，即不同节点存在动力学上本质的差异我们把没有重边和环的图称为 简单图，下面以无向无权图为例，分别介绍描述网络拓扑性质的几个基本参数：平均 路径长度( a v e r a g ep a t hl e n g t h ) 、聚类系数( c l u s t e r i n gc o e f f i c i e n t ) 、度分布( d e g r e e d i s t r i b u t i o n ) 、相关系数( a s s o r t a t i v ec o e f f i c i e n t ) 和介数( b e t w e e n n e s sc e n t r a l i t y ) 1 2 2 1 平均路径长度( a v e r a g ep a t hl e n g t h ) 网络中任意两个节点i 和j 之间的距离，定义为连接这两个节点的最短路径上的 边数，记为奶网络中任意两节点问的距离之最大值称为网络的直径( d i a m e t e r ) ， 记为d 网络的平均路径长度定义为网络中任意两个节点之间的距离的平均值， 即 扛莉与奶， ( 1 2 1 ) 它描述了网络中节点问的平均分离程度，即网络任意两个节点之间平均可以通过l 条边连接起来如果网络中包含互不连通的子图，那么1 2 1 的定义则存在问题， 因为这种情况下有些节点对之间不存在通路另外一种比较好的方法是定义1 2 1 中所有节点对之间的“调和平均距离”，即为倒数的平均的倒数 一2 丽蛎1 ， ( 1 2 2 ) 这样无穷大的也t 对求和就不存在影响了 平均路径长度描述了网络中各个节点问的分离程度通过对真实网络甲均路径 长度的研究，人们揭示了复杂网络的“小世界( s m a l l w o r l d ) ”特性，比如，对于具 有十几亿个节点的万维网，平均路径长度不到2 0 1 2 2 2 聚类系数( c l u s t e r i n gc o e f f i c i e n t ) 2 0 1 0 年上海大学硕士学位论文 9 所谓聚类系数是指与第三个节点连接的一对节点被连接的概率，有时也称为簇 系数，用c 来表示它描述了网络中点与点集结成群的趋势比如在社会网络中， 你朋友的朋友可能也是你的朋友或你的两个朋友彼此可能也是朋友一般来说，假 设网络的一个节点i 有条边将它和其他节点相连，所连接的乜个节点称为节点 i 的邻居，这个节点问实际存在的边数最和可能的总边数( 一1 ) 2 之比为 节点i 的聚类系数g ，即 g = 2 e j ( k d k l 一1 ) ) ，( 1 2 3 ) 整个网络的聚类系数c 是所有节点i 的聚类系数g 的平均值，即 。 c2 j i z c , ， ( 1 2 4 ) 显然，0 c 1 c = 0 当且仅当网络中没有任意三个节点是相互连接的，比 如甲均度为2 的环形网络；当网络为全局耦合时c = 1 ，即网络中任意两个节点 都直接连接；对于一个具有个节点的随机网络，当很大时，c d ( 1 ) 但许多大规模实际网络的c 通常比o ( 1 n ) 要大的多，具有明显的聚类效应正如 常言道“物以类聚，人以群分”，社会经济网络的一个典型的特征就是小集团集群 的形态 1 2 2 3 度分布( d e g r e ed i s t r i b u t i o n ) 度是个描述节点特征的最简单的也是研究最多的概念，它是描述网络局部特 性的基本参数网络中节点i 的度觑被定义为与该节点连接的其它节点的数目， 因此个节点的度越大就意味着这个节点就越重要网络中所有节点的度的平均值 为网络的平均度，记为( 七) 由于每一条边对度的贡献为2 ，所以网络的平均度为 = 斋= 警 ( 1 2 5 ) 其中，m 和分别表示网络的边数和节点数对于有向网络，需把度的概念推广 为入度( i n - d e g r e e ) 和出度( o u t d e g r e e ) ，节点的入度指从其它节点指向该节点的边 的数目，节点的出度指从该节点指向其它节点的边的数目 个网络中节点度的分布情况可以用一个分布函数p ( k ) 来描述，其表示一个 随机选定的节点的度恰好为k 的概率，其直观地反映了网络中度数为k 的节点在整 1 0 生物网络的d d 模型构建 个网络中所占的比例根据不同类型的度分布，可以把网络分为均匀网络( h o m o g e - n e o n sn e t w o r k ) 和非均匀网络( i n h o m o g e n e o u sn e t w o r k ) 或异质网络( h e t e r o g e n e o u s n e t w o r k ) 规则的格子具有简单的度序列，因为其所有节点具有相同的度，而随机网 络度分布近似于泊松分布，其形状在远离峰值处呈指数下降这类网络称为均匀网 络，包括规则网络、完全随机网络、w s ( 或n w ) 小世界网络等近几年的大量研究 表明，许多实际网络的度分布明显不同于泊松分布，许多网络的度分布都遵从幂律 形式tp ( k ) 一k 一，其中r 般介于2 到3 幂律分布曲线比指数分布曲线下降趋 势要缓慢得多研究发现具有幂律度分布的网络没有明显的特征标度，所以这类网 络称为无标度网络( s c a l e - f r e en e t w o r k ) 也就是说，在个大规模的无标度网络中 绝大部分的节点度相对很低，但也存在少量的度相对很高的节点，因此无标度网络 是非均匀的，而那些少量的度相对很高的节点则称为网络的。中一1 、5 结点”( h u b ) 另外一种表示度数据的方法是绘制累积度分布函数 只( k 七) = ：最， ( 1 2 6 ) 知 k 它表示度大于k 的概率，该方法的好处是可用来表示所有的原始数据从大量真实 网络数据的分析表明，小世界和无标度特性在真实网络中是广泛存在的 1 2 2 4 相关系数( a s s o r t a t i v ec o e f f i c i e n t ) 经发现，在真实世界网络中，网络中一条边两端节点的度数并不是相互独立的， 它们之间存在着某种关系，或为正关系，或为负关系这种性质决定于是否度大的 节点会偏向于连接同样度大的节点? 或者它们会选择与度小的节点相连接? 目前， 这两种现象都在现实网络中找到了在复杂网络中，我们用度的正负关联性描述这 两种不同连接倾向 度的正负关联性是一个网络重要的拓扑性质，一个网络被称为正关联的网络， 是指它具有度的正关联性，即它的度大的节点倾向于和度大的节点连接；一个网络 被称为负关联的网络，是指它具有度的负关联性，即度大的节点趋向于和度小的节 点连接可以用相关系数给出网络这一属性的定量描述n e w m a n 2 4 】在给出的 p e a r s o n 相关系数定义如下： 忙横1 m 象1 糍2k；尝)ao需1m黼kj)ao 2 j t 孙n i + 一【 ， t ；( + 2 ”“ 2 0 1 0 年上海大学硕士学位论文 1 1 其中m 是所有的边数；盂和是第i 条边两个端点的度，i = 1 ，2 ，m 如 果r 0 ，网络是正关联的，即它具有度的正关联性；如果r 0 ，网络是负关联 的，即它具有度的负关联性；如果r = 0 ，网络是中性的，即它既不具有度的正关 联性也不具有度的负关联性 通俗地，我们能把度关联性这样理解在一个由人为节点、人和人之间的关系 为边组成的网络中，如果人们喜欢选择与自己习性相近的人交往，那么这个网络为 正关联网络，反之，若人们喜欢选择那些习性与自己大不相同的人交往，则这个网 络呈现负关联性度关联性可以用来刻画网络，并可以验证网络模型描绘真实网络 的能力科学家们通过计算发现，几乎所有实证的社会网络都是正关联，而其他的 实证网络诸如信息网络、科技网络、生物网络却往往为负关联究竟什么原因导致 现实网络在相配性上的这种巨大差异，科学家门正在积极的探索过程中我们也将 在本文的第二章中给出我们研究的一些结果 1 2 2 5 介数( b e t w e e n n e s sc e n t r a l i t y ) 介数分为节点介数和边介数节点的介数是指网络中所有的最短路径中经过该 节点的数量比例，它反映了某节点在通过网络进行信息传输中的重要性网络中不 相邻的节点i 和节点歹之间的通讯主要依赖于连接节点i 和节点j 的最短路径如 果个节点被许多最短路径经过，则表明该节点在网络中很重要在个网络中， 个节点可的介数是指网络中所有最短路径中，经过节点可的数量所占的比例，数 学定义为t ( 1 2 8 ) 其中，s i j 是节点i 和节点j 之间的最短路径数目，( 郇) 是指节点i 和节点j f 之 间经过节点秽的最短路径数目 某个节点的介数越大说明在信息传播过程中通过该节点的信息量也会越多，于 是也越容易发生信息拥塞所谓的交通要道、战略要地等都是介数比较大的节点例 如在中文网站中，百度、搜狐等显然是介数比较大的网站在社会关系网络或技术 网络中，介数的分布特征反映了不同人员、技术和资源在相应生产关系中的地位， 这对于在网络中发现和保护关键资源和技术具有重要意义 同样，我们也可以定义边的介数。它反映边的重要性和影