（应用数学专业论文）ba无标度网络模型的应用及扩展.pdf

摘要 近几年随着人们对复杂巨系统认识的深入，对它不同层次上相对独立个体 的属性和结构的研究，以及在分析工作中遇到的困难，越来越多地的发现其子系 统之间存在着密切相互作用，种种依存关系，而且这些相互作用对于构成系统整 体是很重要的。所以在计算机的高效计算能力的辅助下，在对于生态系统、 i n t e r n e t 、社会系统、生命系统等系统及其子系统这类开放复杂巨系统的观测 基础上，人们开始重视系统部件之间的相互作用关系和整体性，在不同的领域进 行了从整体出发的复杂网络理论研究。复杂网络理论是对不同领域的相对简单 的网络拓扑结构进行观测的结果，而且，近几年的研究发现很多复杂系统均拥有 无标度特性，即大部分节点只有少数几个连结，而某些节点却拥有与其他节点 的大量连结。所以为了深入了解复杂系统，研究无标度网络成为一个必要。 无标度特性的发现突破了随机网络模型的束缚，使我们认识到各种复杂系 统的网络结构，都遵从某些基本的法则，使我们看到了研究系统网络结构的普 适规律的可能。它也使我们可能以复杂网络的拓扑特性研究为切入点，深入开 展系统结构的研究。本文即着重从以下几个方面对无标度网络的代表模型 b a 模型进行了概述和研究拓展： 一、无标度网络是一项最新兴起的系统分析工具。其普及性还不是很好。 因此，有必要对其生成背景、生成机制、适用范围、统计特性及应用价值进行 概述。这也是对其进行实际应用的理论基础。 二、蛋白质折叠结构预测是一项世界性的难题，面对能量函数的准确运用、 构象空间中的上亿构象数必须要求有能处理大规模问题能力的工具来高效解 决。但是，迄今为止的各种方法其预测精确度都还不是很理想。本文开拓性的 运用新型的复杂网络理论于蛋白质结构预测研究中，并得到了一种粗粒化模型 的较为精确的结果。 三、现有的无标度网络模型的典型代表b a 无标度网络模型是从现实网 络中抽象而来的。但是，应用发现它对于指导现实有很大的局限性，所以为了 使其满足更多现实系统的拓扑结构，本文对其算法进行了扩展。并依据二者静 态统计量性质进行性态比较，证实了扩展后的模型的拓扑结构和发展状况更接 近于现实网络，并且扩展模型生成网络的鲁棒性也更好一些。 关键词：复杂系统，复杂网络，无标度网络，蛋白质二级结构预测，扩展 a b s t r a c t r e c e n ty e a r s ，a l o n gw i t ht h em o r ea n dm o r ed e e p e ra c q u a i n t a n c eo fc o m p l e x s y s t e m sa sw e l la st h er e s e a r c ho fr e l a t i v e l yi n d e p e n d e n ti n d i v i d u a l sp r o p e r t i e sa n d s t r u c t u r eo nd i f f e r e n tl a y e r so ft h e ma n dd i f f i c u l t i e sm e e t i n gw h e na n a l y z i n gt h e m ， p e o p l em o r ea n dm o r ef o u n dt h ec l o s e dr e l a t i o n se x i s t i n gi nt h e i rs u b s y s t e m sa sw e l l a sa l ls o r t so fi m m a n e n tc l o s e dr e l a t i o n s h i p si nw h i c ha n dt h ei m p o r t a n c er i s e nb y w h i c ht ot h ec o n s t i t u t i n go ft h ew h o l es y s t e m s o ，a s s i s t e db yt h eh i g hc o m p u t i n g c a p a b i l i t yo f t h ec o m p u t e r , t h r o u g ho b s e r v i n gs o m ec o m p l e xh u g es y s t e m sa n dt h e i r s u b s y s t e m ss u c ha se c o l o g i c a ls y s t e m ，i n t e m e ts y s t e m ，s o c i a ls y s t e m ，v i t a ls y s t e m a n ds oo n ，p e o p l eb e g i nt oa t t a c hi m p o r t a n c et oi n t e r a c t i o na n du n i t yo ft h e m f u r t h e r m o r e ，t h ea l la b o v ef o m e n tt h ec o m p l e xn e t w o r k sr e s e a r c hi nl o t so fd i f f e r e n t s c i e n t i f i cd o m a i n s c o m p l e xn e t w o r k st h e o r yi ss u c har e s u l t t h a ti s s u ef r o mt h e o b s e r v a t i o nt or e l a t i v es i m p l et o p o l o g ys t r u c t u r eo fn e t w o r k si nd i f f e r e n td o m a i n s a n d ，r e c e n ts e v e r a ly e a r s ，m a n yr e s e a r c hs h o wt h a tm a n yc o m p l e xs y s t e m sp o s s e s s t h es c a l e f r e ep r o p e r t y ，t h a ti s ，t h em a s so fn o d e sh a v eo n l yaf e wc o n n e c t i o n sb u t a b u n d a n tc o n n e c t i o n sa r ep o s s e s s e db ym i n o r i t yn o d e s s o ，t od e e p l yk n o wa b o u t c o m p l e xs y s t e m s ，i ti sv e r ye s s e n t i a lt os t u d yt h es c a l e f r e en e t w o r k s t h ed i s c o v e r yo fs c a l e f r e ep r o p e r t yb r e a k st h r o w 【g ht h er e s t r i c t i o no fr a n d o m n e t w o r km o d e la n dw h i c hm a k e su sk n o w 。a b o u tm a n yd i f f e r e n tk i n d so fs t r u c t u r eo f c o m p l e xs y s t e m sa l lo b e ys o m es a m ef u n d a m e n t a ll a w s ，a n da l s om a k e su sk n o w a b o u ti ti si m p o s s i b l et os t u d yt h ec u r r e n tr u l e so fs y s t e mn e t w o r k s s t r u c t u r e i n a d d i t i o n ，s c a l e f r e ep r o p e r t ya l s om a k e su s c a l lh o l dad e e p e rs t u d yt os y s t e m s t r u c t u r eb a s eo nt o p o l o g i c a lp r o p e r t i e so fc o r n p l e xn e t w o r k s t h ep a p e rd o e sa s u m m a r ya n db r o a d e nr e s e a r c ht ot h eb am o d e lw h i c hj st h et y p i c a lr e p r e s e n t a t i o n o fs c a l e f r e en e t w o r k sf r o mt h ef o l l o w i n gs e v e r a la s p e c t s ： 1 s c a l e f r e en e t w o r ki san e w e s tr i s e ni m p l e m e n tf o rs y s t e ma n a l y z i n g ，s oi t h a s n tb ek n o w na b o u tv e r yw e l l j u s tf o rt h i sr e a s o n ，i ti sv e r yn e c e s s a r yt op r e s e n ta l l s u m m a r yo fw h o s ef o r m i n gb a c k g r o u n d ，f o r m i n gm e c h a n i s m ，r a n g eo fa p p l i c a t i o n ， s t a t i s t i c a l p r o p e r t i e s a n da p p l i e dv a l u e w h a ti sm o r e ，i ti sa l s ot h et h e o r y f u n d a m e n t a lt ob eo np r a c t i c a la p p l y i n g 2 p r o t e i nf o l d i n gs t r u c t u r ep r e d i c t i o ni sac o s m o p o l i t a nt i c k l e r h o wt o a c c u r a t e l ya p p l ye n e r g yf u n c t i o na n dh o w t oc h o o s et h em o s tp r o p e rc o n f o r m a t i o n f r o mh u n d r e d so f m i l l i o n so fc o n f o r m a t i o n sa r ea l ln e e d e dt ob es e t t l e db ya i m p l e m e n tw h i c hc a nd e a lw i t hl a r g e s c a l ep r o b l e mh i 曲e f f i c i e n t l y b u t ，s of a r , t h e r ei s n te v e no n em c t h o dw h o s ep r e d i c t i o ni se n o u g hp r e c i s e i nt h i sp a p e r , w ep u t f o r w a r dat r a i l b l a z i n gs t u d y _ c x e nc o m p l e xn e t w o r k st h e o r yt op r o t e i nf o l d i n g s t r u c t u r ep r e d i c t i o na n df r o mw h i c hw eh a v eg o tam o r ep r e c i s er e s u ro fc o a r s e g r a n u l a t e dm o d e l 3 。t h ee x i t i n gt y p i c a lr e p r e s e n t a t i o no fs c a l e - f r e en e 船o r k s - 出eb am o d e li s a b s t r a c t e df r o mm a n yr e a ln e t w o r k s b u t ，a f t e rs o m ea p p l i c a t i o n ，i ti sf o u n dt h e m o d e lh a sm o r es e v e r ed e f e c t s s o t om a k ei ts a t i s f yt o p o l o g i c a ls t r u c t u r e so fm o r e r e a ls y s t e m s ，t h ep a p e rd o e ss o m ee x t e n d i n gt ob as c a l e f r e en e t w o r km o d e l s a l g o r i t h m a n da f t e rac o m p a r i s o no ft h e i rb e h a v i o rb a s eo nt h ec h a r a c t e r so ft h e s t a t i cs t a t i s t i c s ，i tc a nb ee a s i l yf o u n dt h a tt h et o p o l o g i c a ls t r u c t u r ea n dd e v e l o p m e n t o ft h ee x t e n d i n gm o d e li sm o r ed o s e dt or e a ln e t w o r k s b e s i d e s ，i tc a ni m p r o v e 1 1 e t w o r k s r o b u s t n e s s ， k e y w o r d s ：c o m p l e xs y s t e m s ，c o m p l e xn e t w o r k s ，s c a l e - f r e en e t w o r k s ，2 dp r o t e i n s t r u c t u r e p r e d i c t i o n ，e x t e n d i n g l i i 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：刻塞型日期：巫土! 生z 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部 内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：i ：= f 差超导师签名：盈生盈 日期：五之上：z ! ： 武汉理工大学硕士学位论文 第1 章绪论 1 1 研究背景复杂系统科学简介 复杂系统科学是用以研究复杂系统和复杂性的- - t 7 方兴未艾的交叉学科。 虽然它还处于萌芽时期，但已被有些科学家誉为是“2 1 世纪的科学”。它主要 研究的是复杂系统由微观层次上各子系统之间的相互作用所导致的宏观层次上 的系统结构与行为。它创始于8 0 年代初，以1 9 8 5 年在美国新墨西哥州成立 的圣菲研究所( s a n t af ei n s t i t u t e ，简称s f i ) 为标志。复杂系统科学研究涉及 的范围很广，包括自然、工程、生物、经济、管理、政治与社会等各个方面： 它探索的复杂现象从一个细胞呈现出来的生命现象，到股票市场的涨落、城市 交通的管理、自然灾害的预测，乃至社会的兴衰等等，目前，关于复杂性的研 究受到了世界各国科学家们的广泛关注。1 9 9 9 年，美国科学杂志出版了一 期以“复杂系统”为主题的专辑，这个专辑分别就化学、生物学、神经学、动 物学、自然地理、气候学、经济学等学科领域中的复杂性研究进行了报道。 复杂系统科学研究很重要的一个特点就是复杂性，但复杂性是有层次的。基 于复杂性层次的不同，钱学森提出了新的系统分类。将系统分为简单系统、简单 巨系统、复杂巨系统。w w w i n t e r n e t 系统、生物系统、人体系统、人脑系统、 ( 人文) 地理系统、社会系统、星系系统等都是复杂巨系统。这些系统又是开放 的，和外部环境有物质、能量和信息的交换，所以又称为开放的复杂巨系统。从 方法论来说，对简单系统、简单巨系统，都有了相应的方法论和方法，也有了相应 的理论并在继续发展之中，如协同学、耗散结构理论等。但对于开放的复杂巨系 统，从以上列举的实例可以看到，它涉及到生物学、思维科学、医学、生命科学、 地理科学、天文学以及社会科学等领域，不是还原论方法或其它已有方法所能处 理的，需要新的方法和方法论。而开放复杂巨系统概念的提出及其理论研究，不 仅必将推动这些不同学科的理论发展，而且会提供这些理论沟通的桥梁，提供入 文与科技的沟通，促进理性与非理性的结合。经过多年的研究，在对社会系统、 人体系统和地理系统等3 个丌放复杂巨系统研究实践的基础h ，经过提炼、概括 武汉理工大学硕士学位论文 和抽象，我国学者于1 9 9 0 年提出了开放的复杂巨系统( o c g s ) 与处理这类系统的 方法论综合集成法( m e t a s y n t h e - - i s ) l 2 - s j 。1 9 9 2 年，钱学森总结了国内外科技 发展的成功经验，进一步把从定性到定量的综合集成法加阻拓广，提出了实现 综合集成法的理论框架从定性到定量综合集成研讨体系，并且指出综合集 成法与综合集成研讨厅体系是思维科学的一项应用技术。 目前，对于开放的复杂巨系统的研究还没有形成从微观到宏观的理论，要建 立开放的复杂巨系统的一般理论，必须从一个一个具体的开放复杂巨系统入手。 不太复杂的系统能够设计而成，但是开放的复杂系统却娶靠“机会”生成，或者 说有赖于几百万年的演化。开放的复杂巨系统( o c g s ) 的特性概括如下”1 ： 1 ) 系统与外部环境，以及子系统之间存在能量、信息或物质的交换，就系 统与环境的关系而言，开放表现为最复杂与常见的不可访问性的、不确定的、动 态连续的环境类型。 2 ) 从已经认识的比较清楚的子系统到可以宏观观测的整个系统之间层次 很多，甚至有几个层次也不清楚；系统子系统或者组件的组成模式多种多样，有 的甚至不清楚具体模式，或是一些基本模式的组合或变异体。 3 ) 系统是由时空交叠或分布的组件构成的：肩负不同角色的组件问通过多 种交互模式、按局部或者全局的行为法则( 如社会理性原则) 等平等交互，涌现 出宏观与整体形态。 4 ) 系统的组成、组件类型与状态、组件之间的交互，以及系统行为随时间 不断改变；系统中子系统或基本单元之间的局部交互，经过一定的生命周期之 后在拯体上演化出一些独特的、新的性质，形成某些模式。 5 ) 基本单元或子系统的数目极其巨大，从成千上万到数以亿计。 此外，许多开放的复杂巨系统根据其属性的不同还有其自身的不同特点。 1 2 研究基础及技术路线 12 1 复杂网络的提出及发展现状 近几年随着人们对复杂巨系统认识的深入，对它不同层次上相对独立个体 的结构的研究，以及分析工作遇到的困难，越来越多的发现其子系统之间的密切 相甄作用，以及种种依存关系和整体的重要性。所以在计算机的高效计算能力的 武汉理工大学硕士学位论文 辅助下，在对于生态系统、i n t e r n e t 、社会系统、生愈系统等系统及其子系统这 类开放复杂臣系统的观测基础上，人们开始重视系统部件之间的相互作用关系 和整体性，在不同的领域进行了从整体出发的复杂网络理论研究“1 1 。复杂网络理 论是对不同领域的相对简单的网络拓扑结构进行观测的结果，发现这些网络不 同于以前的网络系统，它们是动态开放的，不断成长演化具有生命的特点，在局 部层次上杂乱无序，而在整体层次上都呈现出小世界、高度聚类和s c a l e - - f r e e 的特点。为了研究这类网络，兴起了复杂网络理论研究来捕捉复杂网络的拓扑结 构特点，理解复杂网络韵动态演化过程，人们试图运用随机图，s c a l e - - f r e e 网 络，小世界模型，演化网络等数学模型对它们建模，研究它们的统计特性、成长 原因以及成长规律“。从复杂网络理论的起源可以明显看出，这类问题涉及 社会学、生物学、生命科学、物理、化学、地理科学等诸多学科。尤其是和人、 人的行为、人的思维、人的心理有密切关系，用纯粹的数学模型建模是不可能 的，必须融合各个相关的不同学科领域的知识，将理性知识与非理性知识相结 合。 从复杂网络的构建过程可以看出，复杂网络所研究的只是系统部件之间非 常简单的交互关系所导致的网络拓扑结构。它是对复杂系统非常一般的抽象和 描述方式，它突出强调了系统结构的拓扑特征。原则上说，任何包含大量组成 单元( 或子系统) 的复杂系统，当我们把构成单元抽象成节点，单元之间的相 互作用抽象为边时，都可以当作复杂网络来研究”。复杂网络可以用来描述物种 之间的捕食关系、人与人之间的社会关系、词与词之间的语义联系、计算机之 间的网络链接、神经元之间的通讯反馈作用、蛋白质之间的相互关系等等。复 杂网络为研究复杂系统提供了一种新的描述方式，可以加深我们对系统结构的 深入了解，反过来，复杂网络的研究成果对探索复杂性又具有一定的启发和借 鉴意义。自从1 9 9 8 年w a t t s 和s t r o g a t z 提出小世界网络模型( w s 模型) 以来，复 杂网络的研究在过去几年得到了迅速发展。原因有以下几个方面：( 1 ) 计算机 技术的迅猛发展使我们有可能获得各种大规模网络的统计性质；( 2 ) 实证分析 表明，从万维网到新陈代谢网，许多领域的各种复杂网络展现了某些共同的统 计性质，如幂律度分布，表明其中可能存在一些普适性的概念和规律；( 3 ) 理 论研究也有了突破。w a t t s 和s t r o g a t z 给出了小世界网络的构造方式，b a r a b a s i 和a l e r t 则指出，增长和偏好连接是形成无标度网络的根本原因，统计物理学的 研究方法在复杂网络研究中得到广泛应用。理论研究和实证分析的相互促进在 武汉理工大学硕士学位论文 复杂网络的研究中得到了充分体现。 目前，复杂网络的研究工作主要集中在以下几个方面：( 1 ) 复杂网络拓扑 结构的静态统计分析，包括更广泛的实证研究和更深入的理论刻画，如给定度 分布基础之上的匹配模式、各种相关关系、加权网络的统计性质和描述方式以 及网络的聚类等； ( 2 ) 复杂网络的演化和机制模型，实证上可以研究实际网络 演化的统计规律，检验b a 模型的偏好连接假设，理论上则可以发展更完善的具 有形成特定几何性质的网络机制模型； ( 3 ) 复杂网络上的动力学研究，包括网 络容错性和攻击鲁棒性，以及网络上的传播、同步与共振等各种动力学过程。 根据拓扑结构的不同，复杂网络可以分为规则网络，随机网络，小世界网 络，无标度网络等。规则网络是指我们常见的具有规则拓扑结构的网络，如完 全连接图，星状网络，邻近节点连接图等。关于规则网络的研究，已经建立了 比较完善的理论框架。随机网络( 其代表模型是e r d o s 和r e n y i 于1 9 5 9 年提出的 e r 模型) 是由一些节点通过随机布置的连接而组成的复杂网络，如美国的高速 公路网。随机网络的节点连接的分布为钟形曲线分布。小世界网络是一类特殊 的复杂网络，它具有大的集聚系数和小的平均最短距离。无标度网络是节点与 节点之间的连接分布遵循幂律分布的网络，如美国的航空网。此类网络的大部 分节点只有少数连接，而少数节点则拥有大量的连接“”“。 1 2 2 无标度网络简介 很多复杂系统拥有共同的重要特性：大部分节点只有少数几个连结，而某些 节点却拥有与其他节点的大量连结。这些具有大量连结的节点称为“集散节 点”，所拥有的连结可能高达数百、数千甚至数百万。过去的几年中，不同领 域的研究者发现，很多网络都是由少数一些具有众多连结的节点，即“集散节 点”，所支配的，包括万维网，细胞代谢系统，以及好莱坞的演员网络。包含这 种重要节点( 或称集散节点) 的网络，我们通常称之为“无标度”( s c a l e f r e e ) 网络“。在无标度网络中，有些集散节点甚至具有数不清的连结，而且不存在 代表性的节点。这种网络还具有可预期的行为特性：例如对意外故障具有惊人 的承受力，但诬对协同式攻击时则很脆弱“。 这些发现极大地改变了我们对复杂外部世界的认识。集散节点的存在，让 我们认识到了以前的网络理论尚未涉及的问题：各种复杂系统具有相同的严格 4 武汉理工大学硕士学位论文 结构，都受制于某些基本的法则，这些法则似乎可同等地适用于细胞、计算机、 语言和社会。更进一步，认识这些法则，会帮助我们解决一系列重要问题，包 括开发更好的药物、防止黑客侵入互联网、阻止致命流行病的传播，等等。 无标度特性的发现突破了随机网络模型的束缚，使我们认识到各种复杂系 统的网络结构，都遵从某些基本的法则，使我们看到了研究系统网络结构的普 适规律的可能，使我们可能以复杂网络的拓扑特性研究为切入点，深入开展系统 结构的研究。系统结构是系统科学的基本概念，是客观事物的基本属性，也是 各学科领域的基本阀题，如物质科学研究物质的结构和性质，生命科学和社会 科学研究生物和社会的结构和功能。可以说，每门学科对其研究对象的结构， 都有非常丰富的具体成果；但从系统学的高度，横跨物质系统、生物系统和社 会经济系统的具体研究成果，也就是系统学层面的成果还不多。无标度网络的 发现，为我们打开了新视野。近几年，无标度网络的研究成果反映了大多数复 杂系统的这些基本特性，使得对这些系统的研究取得了实质性的突破。 1 3 本文的研究内容 本文的研究内容主要有以下几个方面： ( 1 ) b a 无标度网络模型的生成机制及存在意义 从复杂系统研究的高度来阐述无标度网络模型生成的极大必要性和相当有 效性。 ( 2 ) b a 无标度网络模型在蛋白质二级结构预测中的应用 1 ) 蛋白质二级结构构象的生成 本文着重研究蛋白质二级结构预测。而理论研究的目的都是要得到合理的 几何构象体，本文即运用模拟退火算法对蛋白质二维连续模型进行优化计算得 到大量能量级大致相同的较优构象。 2 ) 构象网络的生成 由于各种优化算法本身的极大局限性，我们用模拟退火算法得不到最优构 象，只能得到大量能量级较低的较优构象，而为了从这些大量的较优构象中得 到合理构象，本文将这些构象作为节点构成一个复杂网络，计算网络节点介数 来确定最为合理的构象。 武汉理工大学硕士学位论文 3 ) 最合理构象的获取及结果分析 在1 ) 、2 ) 的基础上利用复杂网络的静态几何量特征，主要是节点介数的 计算，从大量节点构象中得到最合理的构象。对此构象进行理论分析，从理论 上支持得到的结果。 ( 3 ) b a 无标度网络模型的适当扩展 鉴于原始b a 模型在某些现实领域应用的局限性，将其做了适当的算法扩 展。 1 4 本文的组织结构 本文公分五章内容来对b a 无标度网络模型进行阐述。分别从其生成原理、 生成机制、适用性、实例应用、算法扩展方面来进行： 第一章：介绍了课题的提出背景和意义，主要是复杂系统科学及其重要分 支复杂网络的应用范围和重要应用价值。 第二章：对b a 无标度网络模型从生成原理、应用价值方面进行了全面阐述。 第三章：用模拟退火算法对已有的蛋白质结构预n - - - 维连续模型计算得到 大量能量级大致相同的构象。然后利用复杂系统科学的前瞻性及应用的广泛性 和有效性，特别是复杂网络处理抽象概念的强有效性，将蛋白质二级构象抽象 为节点生成构象网，并利用无标度网络的特性计算得出最优构象。 第四章：针对原始b a 无标度网络模型的局限性进行算法的扩展。 第五章：总结和展望。总结全文的创新点，指出存在的不足，并指出今后 的发展方向和后续价值。 1 5 小结 本章对本文内容做了概述。简单介绍了b a 无标度网络模型的生成原理、利 用价值、发展现状以及存在的不足，介绍了复杂系统科学的应用价值，并基于 此提出了本文的预测方法。 武汉理工大学硕士学位论文 第2 章b a 无标度网络模型 2 。1 无标度网络的提出背景 在过去4 0 多年里，科学家们惯于将所有复杂网络看作是随机网络。随机 网络理论有一项重要预测：尽管连结是随机安置的，但由此形成的网络却是高 度民主的，也就是说，绝大部分节点的连结数目会大致相同。实际上，随机网 络中节点的度数分布方式将遵循钟形的泊松分布。连接数日比平均数高许多或 低许多的节点，都十分罕见。有时随机网络也称作指数网络，因为一个节点连 接k 个其他节点的概率，会随着k 值的增大而呈指数递减”1 。因此在1 9 9 8 年， b a r a l a s i 和a l b e r t 等合作进行一个描绘万维网的项目时，是以随机网络为基础模 型体进行研究的“”“1 。但是，随着实验的展开，实测结果却推翻了这个预测。 实验结果显示：基本上，万维网是由少数高连结性的页面串连起来的，8 0 以 上页面的连结数不到4 个。然而只占节点总数不到万分之一的极少数节点，却 有1 0 0 0 个以上的连结。他们在计算恰好拥有k 个连结的万维网页面的数目时， 发现网页的连结分布遵循所谓的“幂次定律”：任何节点与其他k 个节点相连结 的概率，与1 瓜成正比。对于流入的连结而言，n 值接近于2 ，这也就是说，流 入连接数只有某站点一半的站点，在网中的数量却有该站点的4 倍之多。幂次 定律和表征随机网络的钟形分布大相径庭。具体来说，幂次定律不像钟形曲 线那样具有一个峰值，而是由连续递减的函数来描述。如果用双对数坐标系来 描述幂次定律，得到的是一条直线 见下图2 - 1 ，2 - 2 ：随机网络v s 无标度网络 。 与随机网络中连结的民主分布不同，幂次定律所描述的，是由少数集散节点( 如 y a h o o 和g o o g l e 网) 所主控的系统。 b a r a l a s i 和a l b e r t 进一步分析了无标度网络遵循幂次定律的原因，分析了为 什么随机网络理论不能解释集散节点的存在。他们认为随机模型( 如e r 模型) 未能反映现实网络的两个重要特征：1 增长性。即现实网络是由持续不断地向 网络加入新的节点演化而成。2 择优连接性。现实网络中，并非所有的节点都 是平等的“。例如，万维网，在选择将网页连接到何处时，人们可以从数十亿 7 武汉理工大学硕士学位论文 个网站中进行选择。我们大部分人只熟悉整个万维网的一小部分( 如s o h u 网) ， 这一小部分中往往包含那些拥有较多连接的网站，只要连接到这些站点，就等 于造就或加强了对它们的偏好。这种“择优连接”的过程，也发生在其它网络。 如，因特网、新陈代谢网、电话呼叫网、科学家引文网等。 图2 1随机网络 无标度网络 图2 2 随机网络度分布图无标度网络度分布图 武汉理工大学硕士学位论文 2 。2b a 无标度网络模型的生成机制 增长和择优连接这两种要素激励了b a r a l a s i - - a l b e r t 模型。“1 的提出，该模 型首次导出具有幂律度分布的网络。模型的算法如下： ( 1 ) 增长：开始于少量节点，在每个时间问隔添加一个具有脚g ) 条边 的新节点( 连结到已存在于系统中的m 个节点上) 。 ( 2 ) 择优连结：当选择与新节点连结时，假设新节点连结到节点f 的概率石 ， 取决于该节点的连通度t ，即万代) 一： 七 。 三“ 在t 个时间间隔后，模型产生一有n = m 。+ f 个节点和m t 条边的随机网络， 随着t 的增大，该网络演化进入标度不变状态。其度分布p ( 硒女。其中 y = 2 9 0 1 。标度指数y 与模型中唯一的参数m 无关，即系统自组织进入无标 度静止状态。 无疑，b a 模型较之随机网络图比较准确地把握了现实世界中网络的最基本 的特点，抽象建立了复杂网络，其算法较好地解释了无标度网络的形成机制。 对于指导现实现象有较高的应用价值。 2 3b a 无标度网络模型的特性分析 2 3 1 b a 模型的限制条件 b a 模型中幂律标度表明了增长和择优连接在网络演化过程中发挥了重要作 用。但是，它们对幂律标度的出现却并不是必要的。下面我们考虑b a 模型的演 化在只考虑两种算法机制中的一种时的情况“”1 ”。 ( i ) 模型只考虑网络的增长特性，不考虑优先连接。开始有少量节点( m 。) ， 在每个时间间隔加一个有m 沏t m 。) 条边的新节点。假设新节点以等概率方式连 接到已存在于系统中的节点上，即玎以) = 1 ( m 。+ f 一1 ) ，于龟无关。 由连续域理论。2 5 。得出，女，o ) 服从对数时间相关，且当f o o 时，度分布呈 指数衰减，服从( 如图1 ) 口 p ( k 1 = 2 - - e x p ( 一二1 ( 2 1 ) 武汉理工大学硕士学位论文 度分布的指数特性表明：缺乏择优连接，就取消了该网络的无标度特性。 ( “) 模型没有节点的增长。开始有个节点，且没有连接边，在每个时间间 隔任选一个节点并以概率石 ) 4 夕每j ；连接到系统中的节点f 。因此，节点数 ，l 量在网络进化过程中保持不变。数量模拟表明，在早期模型显示出幂律标度， p ( k ) 不稳定( 如图2 3 ) ，由于为常数，边数随时间增加。在经过r 一2 时 刻后，系统达到所有节点都连接的状态。 图2 3两个模型的连通度分布：( a ) 模型( i ) 的连通度分布：o ： = m l ；口：= 拱一3 ；：m o = 臃一5 ；：m o 一拼一7 ，啜络规馍为= 8 0 0 0 0 。 插图：在= 5 及f ：；9 7 时，添加到系统的两个节点连通度的时间演化。肌。= 历；3 短划线服j z k , ( t ) ；鹏l i i ( m 。+ f 一1 ) ；( b ) 模型( i i ) 的连通度分布，n ：1 0 0 0 0 ：o ： t ：n ；口：t = 5 n ；：t ：4 0 n 。插图：两节点连通度的时间相关性。系统规模 ；1 0 0 0 0 。 单个节点度的时间演化可用连续域理论解析计算，给出 鼻o ) 2 亩( 2 - - 2 ) 设，1 与数量模拟结果相一致。 由于连续域理论预测经过一瞬态阶段后，所有节点的平均度应具有由式 ( 2 - - 2 ) 给出的相同值。图2 3 表明p 辑) 的形状从最初的幂律分布变为了高斯 分布。 1 0 ” 心 武汉理工大学硕士学位论文 模型i ) “) 不能产生无标度度分布，表明增长和择优连接对于从客观 世界观察到的稳定的幂律分布是同时需要的。 2 ，3 2b a 模型的静态统计量特性 我们一般研究复杂网络的静态统计量来获取其属性。这些统计量通常包括： 度分布、平均最短路径、集聚系数、及介数等等。具体定义如下艟”： 如果一个网络中有个节点，则 1 节点度分布定义为：一个节点n 的所有边数为其度数屯：而度分布e ( k ) 为任意选择的节点正好有条边的概率； 2 网络的平均最短路径定义为： 定义网络中任意两节点氇，n ，间的距离d 伽，n ，) 为它们之阊边数的最小值。 d ，n j ) 网络的平均最短路径：l = 受：t f 。 l v 3 网络集聚系数定义为： 对于节点n ，它可能连接到n 一1 个节点上，则最大可能边数为m m ) ： ( 一1 ) + ( 一2 1 髟，则节点n 的集聚系数定义为c o ) 。a o ) 加o ) ，其中口o ) 为实 际存在的边数。整个网络的集聚系数定义为c ；罗c 0 ) 。 箱 4 介数定义为： 节点n 的介数盯伽) ；经过它的最短路径的条数。 下面给出b a 模型的这些统计量待往。 1 度分布 无标度模型的动态特性可以用各种方法给出。b a r a b a s i 和a l b e r t 于1 9 9 9 年提出的连续域理论致力于节点度的动态特性研究，并进而得出了无标度网络 模型度分布服从幂律分布跗) 女一7 的经典结论。随后d o r o g o v t e v ，m e n d e s 和 s a m u k h i n 的主方程法，k r a p i v s k y ，r e d n e r 及l e y v r a z 提出的变化率方程法，都 相继得出了相同的结论”。 2 平均最短路径 武汉理工大学硕士学位论文 图2 4 为网络规模为，平均度数t 女 薯4 的b a 模型的平均路径长度与同 样规模相同平均度的随机图的平均最短路径的比较图。从图可以看出，b a 模型 的平均最短路径长度远小于任意个节点的随机图。说明非均匀的无标度拓扑 结构比随机图的均匀拓扑结构在使节点靠近方面更为有效。b a 模型的平均路径 长度随增加而近似呈对数增长，符合下述广义对数形式： ，一, 4 1 n 0 、r 一口) + c ( 2 3 ) 最新的解析结果表明，对于对数相关存在一双对数修正，即： i n ( , v ) l l nl n ( ) 。 图2 4b a 模型在c 七”4 时平均最短路径长度与同等规模的随机网络 的变化比较。短划线服从公式( 2 3 ) ，实线表示公式( $ ) ( 随机图的平均最 短路径公式) 。0 ：为b a 模型的平均最短路径长；口：为随机网络的平均最短 路径长。 ( 木) 式为? 一言墨铬“，其中q 而分别为网络中某个节点的最邻近和次邻近 节点数。 从图2 4 可以看出用公式( ) 不能正确的刻画b a 模型的平均最短路径长， 而公式( 2 3 ) 确实呈现出了实际网络的平均最短路径长度。 3 集聚系数 图2 5 给出了平均度c 七 邕4 ，且规模不同的b a 模型的集聚系数，与随机 图的集聚系数相比较，我们发现无标度网络的集聚系数比随机图高五倍，该参 数随节点数量缓慢增长。但是，b a 模型的集聚系数随网络规模变化而下降，大 约服从幂函数规律c 4 ”，比随机图观测到的c = 缓慢衰减，它不同 1 2 武汉理工大学硕士学位论文 于小世界模型特性，其c 与无关。 图2 5c k 4 的b a 模型的集聚系数与随机图集聚系数c = c k ) n 随机网络规模变化比较。 4 介数 由b a 模型的节点连接方式，及以上统计量的特性，其介数分布不同于随机 图的较均匀分布，图2 6 为规模n = 1 0 0 0 0 的b a 模型的点介数及边介数分布图： 1 0 1 0 0 1 0 0 0 r a n k o f v e r t e x 图2 6 点介数分布图边介数分布图 妒 u 武汉理工大学硕士学位论文 2 4 小结 本章对b a 无标度网络模型的生成背景、生成机制、应用价值及统计特性方 面进行了详尽的阐述，为我们下一步进行的蛋白质二级结构预测提供了坚实的 理论基础。 1 4 武汉理工大学硕士学位论文 第3 章b a 无标度网络模型在蛋白质折叠二级结构 预测中的应用 8 1 蛋白质结构预测的意义和现状 蛋白质是重要的生物大分子，参与生命体系几乎所有的过程。血红蛋白在 红血球中载氧，胶原蛋白组成皮肤的大部分，各种酶催化生命活动中众多的反 应。具有如此繁多功能的蛋白质，在组成和结构上有一些规律，使得人们可以 着手对它进行研究和改造。蛋白质都是由一类口q 作氨基酸的小分子化合物构成， 这些氨基酸按特定的排列顺序首尾相连，形成特定长度的肽链。在生理条件下， 由于肽链内部相邻氨基酸残基之间的相互作用，以及在顺序上相隔较远，但在 空间上相互接近的氨基酸残基之间的相互作用，使得肤链总是倾向于采取一种 能量最低的空间结构，来达到稳定存在的形式。这样的特定的空间结构，与蛋 白质特有的功能密切相关。所以蛋白质的空间结构是由其氨基酸的组成和排列 顺序决定的。有了这样一个规律，就可以通过改变蛋白质的氨基酸组成和排列 顺序来改变其空间结构，进而影响蛋白质的功能“”“! 。 目前，已知蛋白质序列数与已知的结构数严重不平衡，蛋白质序列数据库 中的数据量大大超过结构数据库中的数据量。虽然蛋白质结构测定方法有所改 进，但仍不能满足实际的需要，需要发展理论预测的方法。蛋白质变性及重折 叠实验，为从蛋白质的氨基酸序列预测蛋白质的三维空间结构提供了实验基础。 直接从蛋白质序列预测蛋白质结构对研究蛋白质结构与功能的关系十分有用， 这也将促进蛋白质工程和蛋白质设计的发展。从原理上讲，蛋白质序列隐含了 蛋白质折叠后的空间结构，理论上可以从氨基酸序列计算出自然折叠的蛋白质 结构。但是，由于蛋白质多肽链可能的构象是个天文数字，现有的计算能力不 可能搜索整个构象空间，需采用一定的启发式方法来寻找自由能最优或接近于 最优的构象“。 本史主要研究蛋白质二级折叠结构的预测。关于二级结构的预测方面，人 们已经提出了许多方法，如立体化学方法、图论方法、统计方法、最邻近决策 武汉理工大学硕士学位论文 方法、基于规则的