（计算机应用技术专业论文）internet宏观拓扑结构的生命特征研究.pdf

东北大学博士学位论文 摘要 i n t e m e t 宏观拓扑结构的生命特征研究 中文摘要 i n t e r n e t 是由人类建造的复杂网络，对其宏观拓扑结构演化的研究是目前研究的热 点问题，特别是近年来人类在复杂网络研究方面所取得的成果，使人们对i n t e r n e t 宏 观拓扑结构的研究取得了很大的进展。但是目前这些研究主要集中在分析节点之间的动 力学原理和行为的同步，揭示在其规模扩大时宏观拓扑结构演化的内在机制等方面。从 宏观上来看，i n t e r n e t 拓扑结构演化不是杂乱无章地进行的，而是呈现出明显的混沌特 征。揭示i n t e r n e t 宏观拓扑结构的演化规律，对于i n t e r n e t 宏观拓扑结构的建模以及 对i n t e r n e t 其它方面的研究，必然具有重要的意义。 本文首先建立了i n t e r n e t 宏观拓扑结构的演化适应模型，求出了影响i n t e r n e t 宏 观拓扑结构演化的序参量，通过对序参量的分析发现，当外力的作用趋近于0 或者无穷 大时，i n t e r a c t 宏观拓扑的演化主要由长期生存效用起作用，i n t e r a c t 向着规则网络的方 向演化：而当外力的作用恰好等于一个不稳定的拓扑演化变量的时候，i n t e m e t 受短期 生存效用的影响，向着星形网络的方向演化。由此发现i n t e r a c t 的宏观拓扑结构具有适 应性。 另外本文从i n t e r n e t 的信息代谢、自复制和突变这三个方面，对i n t e r n e t 的宏观 拓扑结构进行了研究。 代谢是生命的最基本特征之一，i n t e r n e t 的信息代谢过程，通过从外界获得负熵流 保持了i n t e r n e t 拓扑结构的存在。根据香农信息熵的基本原理，本文定义了i n t e r n e t 标准结构熵，利用c a i d as k i t t e r 项目提供的全球i n t e r n e t 监测数据，计算了i n t e r n e t 标准结构熵随时间变化的规律，其中利用r i e s l i n g 节点获得的i n t e m e t 监铡数据计算的 i n t e m c t 标准结构熵从2 0 0 0 年4 月的最大值0 3 7 9 下降至2 0 0 4 年5 月的0 3 1 8 ，月平均 下降幅度为0 1 2 ；a p a ni 节点的数据计算结果表明 标准结构熵从年pi n t e m e t2 0 0 0 4 月的最大值0 3 8 8 下降至2 0 0 4 年5 月的0 2 9 7 ，月平均下降幅度为0 1 8 。这表明i n t e r n e t 标准结构熵有降低的趋势，宏观拓扑结构的演化过程中存在着信息代谢。 自复制是生命的另一个重要特征，在信息代谢过程中，为了保持其宏观拓扑结构的 相对稳定性，i n t e r n e t 必须要保持其拓扑结构信息不会丢失，这个过程是通过其拓扑结 构的自复制过程实现的。对i n t e r n e t 节点的平均连接度的分形维数、最大l y a p u n o v 指 数和k o l m o l o g o r o v 熵的计算发现，分形维数为一个分数值( 2 7 ) 并且最大h y a p u n o v 指数和k o l m o l o g o r o v 熵值大于0 ，这表明i n t e r n e t 节点的平均连接度具有混沌和分形 的特征，另外对i n t e r n e t 节点和边演化的计算发现，节点的连接度越高，与其建立连 接的节点数和边数也越多，但新增的节点数和边数与该节点的初始度值并不具有正比关 东北大学博士学位论文 摘要 系。分析计算的结果可知，i n t e r n e t 的宏观拓扑结构在演化过程中存在着自复制。 自复制是在开放的环境下进行的，必然会受到“噪声”( 外界环境) 的干扰，因此 复制的结果不是也不可能是精确的。自复制过程所产生的复制误差，就是i n t e r n e t 拓 扑结构的突变。本文通过对i n t e r n e t 平均最短路径、幂指数等物理量的计算发现， i n t e r n e t 的平均最短路径随时间的增长而趋于降低，当前i n t e r n e t 的平均最短路径为 1 5 2 ；节点连接度分布的幂指数在2 5 至2 8 之间波动；i n t e r a c t 节点的平均连接度在缓 慢地增加。而如果i n t e r n e t 的拓扑结构进行精确复制，那么平均最短路径应该呈增长的 趋势，幂指数应该为一个常数，并且i n t e m m 节点的平均连接度应该保持稳定。由此分 析可知i n t e m e t 在其拓扑结构的自复制过程存在着突变。 根据现代生物学中认为代谢、自复制和突变是生命特征的基本属性的观点可知， i n t e r n e t 的宏观拓扑结构具有生命特征。 关键词：i n t e m e t 生命特征宏观拓扑信息代谢自复制突变演化适应分形连接度 i n t e r a c t 标准结构熵序参量 查! ! 苎兰堡主主堡垒墨一一一笪型! ! ! l r e s e a r c ho nt h el i f ec h a r a c t e r i s t i co f i n t e m e tm a c r o s c o p i ct o p o l o g y a b s t r a c t i n t e m e ti sac o m p l e xn e t w o r kw h i c hi sc o n s t r u c t e db yt h eh u m a n i t ya n dt h er e s e a r c ho n i t st o p o l o g ye v o l u t i o ni st h eh mt o p i ca tp r e s e n t e s p e c i a l l yi nr e c e n ty e a r st h ea c h i e v e m e n t o b t a i n e di n 也ec o m p l e xn e t w o r kr e s e a r c ha s p e c tc a u s e dt h ep e o p l et om a k et h ev e r yo b v i o u s p r o g r e s st oi n t e r n e tt o p o l o g y b u tt h e s ep r e s e n t r e s e a r c hm a i n l yc o n c e n t r a t e do nt h e a n a l y s i so nt h ep r i n c i p l eo fd y n a m i c sa n dt h eb e h a v i o ro fs y n c h r o n i z a t i o na m o n gn o d e s ， p r o m u l g a t e dt h e i n l r i n s i cm e c h a n i s mo fi t st o p o l o g yw h e ni t ss c a l ee x p a n d e d f r o m m a c r o s c o p i cv i e w , t h ee v o l u t i o no fi n t e r a c tt o p o l o g yc a r r i e do nn o tc h a o t i c a l l yb u to r d e r l l y t h ee v o l u t i o np r i n c i p l eo fi n t e r a c tm a c r o s c o p i ct o p o l o g yw a ss i g n i f i c a n tf o rc o n s t r u c t i n gt h e m o d u l eo f i n t e m e tt o p o l o g ya n do t h e rr e s e a r c ho ni n t e r n e t i nt h i sd i s s e r t a t i o na ne v o l u t i o na d a p t i o nm o d e lo f t h ei n t e r n e tm a c r o s c o p i ct o p o l o g yw a s e s t a b l i s h e da n dt h eo r d e rp a r a m e t e rw h i c ha f f e c t e dt h ee v o l u t i o no fi n t e r n e tm a c r o s c o p i c t o p o l o g yw a ss o l v e d b a s e do nt h ea n a l y s i so nt h eo r d e rp a r a m e t e r i tc o u l db ed i s c o v e r e dt h a t i ft h eo u t s i d ef o r e 聃郴e q u a lt o 珊oo ri n f i n i t y , t h ei n t c r n e tm a c r o s c o p i ct o p o l o g yw a s a f f e c t e db yt h el o n g - t e r ms u r v i v a le f f e c t i n t e r a c te v o l v e di n t oar e g u l a rn e t w o r k ；h o w e v e ri f t h eo u t s i d ef o r c ew a se q u a lt oa nu n s t a b l es t a t i ct o p o l o g ye v o l u t i o nv a r i a n t ，i n t e r n e tw a s a f f e c t e db yt h es h o r t - t e r ms u r v i v a le f f e c t i n t e m e tw o u l de v o l v ei n t oas t a rn e t w o r k a t p r e s e n ti n t e r a c tw a sa f f e c t e db yt h el o n g - t e r ms u r v i v a le f f e c ta n d s h o r t - t e r ms u r v i v a le f f e c t f u r t h e r m o r ei n t e r n e tm a c r o s c o p i ct o p o l o g yw a ss t u d i e di nt h e s et h e ea s p e c t s - t h e i n f o r m a t i o nm e t a b o l i s m ，t h es e l f - d u p l i c a t i o na n dt h ec a t a s t r o p h yo f i n t e r n e tt o p o l o g y t h em e t a b o l i s mi so n eo ft h eb a s i cl i r ec h a r a c t e r i s t i e s t h ei n f o r m a t i o nm e t a b o l i s mo f i n t e r n e tm a i n t a i n e dt h ee x i s t e n c eo fi n t e r a c tt o p o l o g yb yg e t t i n gn e g a t i v ee n t r o p yf l o wf r o m t h eo u t s i d e a c c o r d i n gt ot h et h e o r yo fs h a n n o ne n t r o p y , t h ei n t e r a c ts t a n d a r de n t r o p yw a s d e f i n e d b yu s i n gt h eg l o b a li n t e r n e tm o n i t o rd a t ap r o v i d e db yc a i d a s k i t t e rp r o j e c t ，t h e c h a n g e so ft h ei n t e r n e ts t a n d a r de n t r o p yw i t l lt i m ew c r cc o m p u t e d t h ec o m p u t i n gr e s u l t s u s i n gt h em o n i t o rd a t ag e tb yr i e s l i n gs h o w e dt h a tt h ei n t e r a c ts t a n d a r de n t r o p yr e d u c e df r o m t h em a x i m u m0 3 7 9i na p r i l2 0 0 0t oo 3 1 8i nm a y2 0 0 4 t h er e d u c t i o ne x t e n tp e rm o n t hw a s 0 12p e r c e n t o nt h eo t h e rh a n dt h ec o m p u t i n gr e s u l t su s i n gt h em o n i t o rd a t ag e tb ya p a nj p s h o w e dt h a tt h ei n t e r a c ts t a n d a r de n t r o p yr e d u c e df r o mt h em a x i m u m0 3 8 8i na p r i l2 0 0 0t o o 2 9 7i nm a y2 0 0 4 t h er e d u c t i o ne x t e n tp e rm o n t hw a so 1 8p e r c e n t t h o s es h o w e dt h a tt h e i n t e m e ts t a n d a r de n t r o p yt e n d e dt or e d u c e ，s ot h ei n f o r m a t i o nm e t a b o l i s me x i s t e di nt h e p r o c e s so f t h ee v o l u t i o no f i n t e r a c tm a c r o s c o p i ct o p o l o g y 东北大学博士学位论文 a b s t r a c t t h es e l f - d u p l i c a t i o ni sa n o t h e ri m p o r t a n tl i f ec h a r a c t e r i s t i c b u ti nt h ep r o c e s so ft h e i n f o r m a t i o nm e t a b o l i s m ，i no r d e rt om a i n t a i nt h er e l a t i v es t a b i l i t yo fi t sm a c r o s c o p i ct o p o l o g y , i n t e r n e tm u s th a v et om a i n t a i ni t st o p o l o g yi n f o r m a t i o n 协sp r o c e s sw a sr e a l i z e dt h r o u g ht h e s e l f - d u p l i c a t i o no fi n t e m e tt o p o l o g y b yc o m p u t i n gt h ef r a c t a ld i m e n s i o n 、t h em a x i m u m l y a p u n o vp a r a m e t e ra n dt h ek o l m o l o g o r o ve n t r o p yo fa v e r a g ed e g r e eo fi n t e m e tn o d e s ，i t w a sf o u n dt h a tt h et h ef r a c t a ld i m e n s i o nw a saf r a c t i o n ( 2 7 ) a n dt h em a x i m u nl y a p u n o v p a r a m e t e ra n dt h ek o l m o l o g o r o ve n t r o p yw e r eb o t hg r e a t e rt h a nz e r o t h o s er e s u l t ss h o w e d t h a tt h ec h a o t i ca n df r a c t a lc h a r a c t e r i s t i ce x i s t e di nt h ea v e r a g ed e g r e eo fi n t e m e tn o d e s f u r t h e r m o r ei tw a sd i s c o v e r e df r o mt h ec o m p u t i n gr e s u l tf o rt h ee v o l u t i o no fi n t e m e tn o d e s a n de d g e st h a tt h eg r e a t e rt h en o d e sd e g r e ew a s ，t h em o r et h en o d e sa n de d g e sw e r ec o n n e c t e d t ot h e m 1 1 1 en u m b e ro f t h en e w l ya d d e dn o d e sa n de d g e sw e r en o ti np r o p o r t i o nt oi t si n i t i a l d e g r e e s ot h ea n a l y s i so nt h o s er e s u l t si tc a nb ek n o w nt h a tt h es e l f - d u p l i c a t i o ne x i s t e di nt h e e v o l u f i o no f i n t e r n e tm a c r o s c 叩i ct o p o l o g y n l es e l f - d u p l i c a t i o np r o g r e s s e du n d e rt h eo p e ne n v i r o n m e n t s oi ti n e v i t a b l yc o u l db e d i s t u r b e db y ”t h en o i s e ”( e x t e r n a le n v i r o n m e n t ) t h e r e f o r e ，t h er e s u l t so ft h es e l f - d u p l i c a t i o n w e r en o ta n dc o u l dn o tb ep r e c i s e 1 1 1 es e l f - d u p l i c a t i o ne r r o rw a st h ec a t a s 订o p h yo fi n t e r n e t t o p o l o g y i nt h ed i s s e r t a t i o ni tw 踮d i s c o v e r e db yc o m p u t i n gt h ea v e r a g es h o r t e s tp a t ha n d p o w e rp a r a m e t e rt h a tt h ei n t e r n e ta v e r a g es h o r t e s tp a t ht e n d e dt or e d u c ew i t ht i m ei n c r e a s e ； t h ep o w e rp a r a m e t e rf l u c t u a t e di nt h er a n g eo f 2 5t o2 8 ：t h ea v e r a g ed e g r e eo f i n t e r a c tn o d e s i n c r e a s e ds l o w l y h o w e v e r , i f t h es e l f - d u p l i c a t i o no fi n t e r n e tt o p o l o g yi sp r e c i s e ，t h ea v e r a g e s h o r t e s tp a t hs h o u l di n c r e a s e ，t h ep o w e rp a r a m e t e rs h o u l db eac o n s t a n t ，a n dt h ea v e r a g e d e g r e eo fi n t e r a c tn o d e ss h o u l dr e t a i ns t a b i l i z a t i o n s ot h o s ec o m p u t i n gr e s u l t ss u g g e s t e dt h a t t h ec a t a s t r o p h y o f i n t e r n e t t o p o l o g ye x i s t e d i n t h e p r o c e s s o f s e l f - d u p l i c a t i o n a c c o r d i n gt ot h em o d e r nb i o l o g yt h e o r y , i ti sb e l i e v e dt h a tt h em e t a b o l i s m 、t h e s e l f - d u p l i c a t i o na n dt h ec a t a s t r o p h yi st h eb a s i cp r o p e r t yo f l i f ec h a r a c t e r i s t i c s ot h e r ea r cl i f e c h a r a c t e r i s t i c si nt h ei n t e r a c tm a c r o s c o p i ct o p o l o g y k e yw o r d s ： i n t e m e t , m a c r o s c o p i ct o p o l o g y , i n f o r m a t i o nm e t a b o l i s m ，s e l f - d u p l i c a t i o n ，m u t a t i o n ， f r a c t a l ，d e g r e e ，i n t e m e ts t a n d a r de n t r o p y , o r d e rp a r a m e t e r 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其它人己经发表或撰写过的 研究成果，也不包括本人为获得其它学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论本文作了明确的说明并表示谢 意。 学位论文作者签名：强岌波 日 期：土e o 饵1 日2 4 - 口 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 东北大学博士学位论文 第一章绪论 1 1i n t e m e t 研究现状 第一章绪论 从研究的角度看，相对于经济系统或生态系统【，i n t e m e t 中的统计数据的质量要高 得多。我们可以非常方便地从收集数据包或分析日志文件等中获得系统准确的运行记 录，毕竟i n t e m e t 是一个人工的而且数字的系统。 然而把i n t e m e t 看作一个计算机网络，甚至是一群相互连结的计算机网络都是不全 面的。计算机网络只是简单的传载信息的媒体，而i n t e m e t 的优越性和实用性则在于信 息本身。 i n t e r n e 不仅是一个计算机网络，更重要的是它是一个庞大的、实用的、可享受的信 息源；同样也可以把i n t e r n e t 当作一个面向芸芸众生的社会来理解，世界各地上亿的人 可以用i n t e m e t 通信和共享信息源。可以送出或接受电子邮件通信；可以与别人建立联 系并互相索取信息；可以在网上发布公告，宣传你的信息；可以参加各种专题小组讨论； 可以免费享用大量的信息源和软件资源。 因此，i n t e m e t 远非一个计算机网络或者一种信息服务所能比拟。i n t e m e t 证明，当 人们能自由、方便地通信时，他们将变得社会化，变得无私。 目前，i n t e m e t 的规模正以指数级增长，文献【2 像明，i n t e m e t ( 3 1 的节点数大约每两 年翻一番。各国在注重发展信息产业的同时，不断地完善i n t e m e t 基础设旖的建设，网 络带宽不断增加，服务质量不断提高，收费价格不断降低。i n t e m e t 所提供的服务种类 多样、方便快捷、安全可靠，世界上使用i n t e m e t 的人数不断增加。i n t e m e t 已经成为人 类生活不可分割的一部分。 对i n t e m e t 的研究自i n t e r n e t 的诞生开始f 4 】【5 】【6 】，一直是层出不穷，经久不衰。在早 期，人们更多关注的是i m e m e t 的体系结构、网络协议【7 】，计算机互联以及i n t e m e t 所提 供的服务等方面的研究。随着信息技术的飞速发展和人类对i n t e m e t 的依赖程度不断提 高，人们开始在i n t e m e t 所提供服务的安全性、q o s 、t c p 流量分析、拥塞处理、路由 算法以及拓扑建模 8 1 等方面开始了新的探索和研究，并取得了相应的研究成果。特别是 近几十年来人们在复杂性科学和复杂网络等领域取得的研究成果，使国内外的研究者认 识到i n t e m e t 也是复杂网络之一，由此人们开始了从复杂性和复杂网络的角度对i n t e r n e t 的研究。 目前，对i n t e m e t 的理论研究主要集中在拓扑建模【9 】【1 0 1 1 1 】、q o s 、流量分析、路由 东北大学博士学位论文第一主绪垒 算法、拓扑演化1 1 2 1 等热点问题上，哈尔滨工业大学的张宇博士等对i n t e m e t 拓扑建模“m 问题进行了比较系统的研究，提出了目前对i n t e m e t 研究的一些比较新颖的观点，复旦 大学的刘岩等人对i n t e r a c t 上t c p 流自相似性与网络性能关系【1 4 l 进行了较深入的研究， 使人们充分认识到了t c p 流的复杂性；清华大学的周晋博士设计了基于i n t e m e t 小世界 的效应的无组织p 2 p 系统的路由算法l ”j ，该方法充分考虑了i n t e m e t 所具有的小世界效 应；g e o r g o ss i g a n o s 等人对i n t e m e t 的演化【1 6 1 问题进行了研究，尤其是对i n t e m e t 路由 节点变化的研究，使人们深入地认识到了i n t e m e t 的变化；g k a n t s i d i s 等人对i n t e r n e t 的 宏观拓扑【1 7 结构也进行了相当深入的分析和研究。当然还有相当多的研究者，从不同的 角度开展了对i n t e r a c t 的研究【18 】【1 9 l 【2 0 】，如对i n t e m e t 的鲁棒性和脆弱性的研究，对i n t e m e t 提供的服务的q o s 的研究等等。 2 0 0 5 年初，东北大学嵌入式技术实验室成为c a i d a ( t h ec o o p e r a t i v ea s s o c i a t i o nf o r i n t e m e td a t a a n a l y s i s ，一个对全球范围i n t e r n e t 结构及数据进行研究的国际合作机构) 中 国第一个节点后，嵌入式技术实验室复杂网络1 2 1 研究小组已经分别对i n t e m e t 的分割度 的时间敏感性问题、i n t e m e t 的网络密度和i n t e m e t 节点平均连接度等问题进行了比较深 入的研究，并获得国内外同行的认可【2 ”。中国科学技术大学近代物理系汪秉宏教授领导 的复杂系统研究组通过研究，在国际上首次提出通讯网络目益增大的交通吞吐量需求是 驱动网络宏观拓扑结构演化的内在动力，他们所提出的模型在国际上首次再现了真实含 权网络具有幂律的连接度分布、度度负相关、簇度负相关和度权幂律相关的四大特征， 为理解i n t e m e t 的宏观拓扑结构具有非常重要的意义。 但纵观国内外众多的研究成果可以发现，对于i n t e m e t 这个既复杂又巨大的网络系 统而言，目前人类对它的研究还是非常肤浅的，所看到的只是冰山的一角而已，为此要 想充分地认识i n t e m e t ，让它为人类造福，还需要付出更多的金钱和智慧、努力和耐心， 用新的视角和新的思维去审视和研究。 1 2 问题的提出 i n t e r a e t 的宏观拓扑结构研究2 3 1 1 2 q 2 5 】【2 6 1 【2 7 】【2 8 1 是将i n t e r a c t 作为一个整体，利用统计 学的方法对其整个拓手 结构特性进行的研究。需要强调的是，本文所研究的i n t e m e t 宏 观拓扑结构，是对i n t e r n e t 拓扑结构的一种抽象，即忽略一些与i n t e m e t 拓扑结构无关的 属性，如网络协议、i n t e m e t 上的服务、网络带宽等，而重点考虑其拓扑结构的相关属 性，如节点的连接度、度分布等。 i n t e m e t 作为当今人类社会信息化的标志，其规模的增长非常迅速。但现在人类对 东北大学博士学位论文 第一章绪论 其宏观拓扑结构 2 9 1 的研究还处于初级阶段，在这个看似混沌的网络之中还蕴涵着一些不 为人知的规律有待进行深入的挖掘。对i n t e m e t 宏观拓扑结构演化及其内在机制的研究， 是在较高层次上开发利用i n t e m e t 的基础。虽然i n t e m e t 的形成被认为是无限定原则的， 但是它却展现了一些重要而且普适的宏观拓扑结构特征。因此，对i n t e m e t 宏观拓扑结 构的研究，是进一步认识i n t e m e t 规律，有效地发现并利用i n t e m e t 资源和高效开发 i n t e r a c t 应用的基石。 另外，对i n t e m e t 宏观拓扑的研究是计算机网络 3 0 1 1 3 1 1 | 3 2 】自身发展的要求。计算机网 络经过几十年的发展，传统的网络技术已经日趋成熟，人们已经不再关注网络的微观细 节，而更注重网络的宏观整体性能，而传统的计算机网络无论从网络协议还是从体系结 构上来说，已经成为束缚i n t e r a c t 未来发展的桎梏。人类对未来i n t e r e n t 所提供的服务提 出了更高的要求，因此，通过对i n t e m e t 宏观拓扑结构的研究，从中发现i n t e m e t 拓扑结 构演化的宏观规律，可为设计新一代i n t e m e t 的体系结构和网络协议栈等工作提供有价 值的参考。 i m e m e t 是一个复杂网络d 3 】1 3 4 】【3 5 1 1 3 6 1 ，对其进行定量研究具有很大的可操作性。目前， 国外有众多的大学和研究机构，提供了具有权威性的全球i n t e m e l 监测数据，为针对 i n t e r a c t 宏观拓扑结构的研究提供了数据基础。网络作为系统的抽象，虽然每一个系统 的网络都有其自身的特殊性质，有其紧密联系在一起的独特现象，有其自身的演化机制， 但是由于都可以使用网络分析的方法，所以有其共性。例如关于定点度值、介数的分析 方法以及大量不同网络中存在的相同的统计特征，再如随机去点与选择性攻击对网络拓 扑结构的影响及其分析方法。最新研究趋势表明，研究网络的几何性质、网络的形成机 制，网络演化的统计规律以及网络的结构稳定性，并把它的拓扑结构与具体系统结合起 来是复杂网络研究的中心内容f 3 7 1 1 3 8 ”】【艚】【4 l 】。因而，对i n t e m e t 宏观拓扑结构的研究可以 为其它类型复杂网络的相关研究提供一个有价值的原型基础。由此可见，对i n i e m e t 宏 观拓扑结构的研究具有重要而现实的意义。 虽然有研究者指出i n t e m e t 宏观拓扑结构的演化表现出生命特征，但这些研究都是 通过观察i n t e m e t 演化过程中所表现出的外在的现象所得到的结论，查阅大量的文献资 料发现对i n t e m e t 的宏观拓扑结构是否具有生命特征这个问题的研究，目前还没有文章 对此有明确的论述。那么i n t e m e t 的宏观拓扑结构是否具有生命特征呢? 根据现代生物 学的观点，生命必须具有三个基本特征：新陈代谢，自复制，突变。根据这个观点，要 证明i n t e m e t 的宏观拓扑结构具有生命特征，就需要证明其宏观拓扑的演化过程中存在 着代谢、自复制和突变。那么i n t e m e t 的宏观拓扑结构是否具有代谢、自复制和突变的 东北大学博士学位论文 第一章绪论 特性呢? 在时间和空间的有限结合中，i n t e m e t 拓扑结构的巨大重复性破坏了系统的平衡， 却要求平稳地选择生成新的拓扑结构。然而这个选择过程只对中间状态起作用，中间状 态是由高熵值结构向低熵值结构的拓扑状态演化。以此为目的，使i n t e m e t 拓扑结构有 序化的能力，本文称其为i n t e m e t 拓扑结构的信息代谢。 为了保证i n t e m e t 在拓扑结构的演化过程中不会导致拓扑结构信息丢失，在其拓扑 结构的信息代谢过程中，存在着一种自催化的作用，使其在宏观拓扑结构演化过程中呈 现出种自相似1 4 2 1 。i n t e r n e t 宏观拓扑结构的这种内在的自催化的能力，称为i n t e m e t 拓扑结构的自复制能力。 i n t e m e t 在其拓扑结构的自复制过程中必然要受到外界的影响( “噪声”) ，从而 其拓扑结构的自复制必然存在着复制误差。i n t e m e t 在其拓扑结构的自复制过程中所产 生的误差，称为i n t e m e t 拓扑结构的突变。 因此，本文将通过验证i n t e m e t 宏观拓扑结构中存在的信息代谢、自复制和突变【4 如 特性，来验证了i n t e m e t 的宏观拓扑结构具有生命特征。 1 3 论文的章节安排 根据论文研究的内容和方法，全文共分七章。 第一章首先分析了i n t e m e t 的研究现状，根据其现状提出了对i n t e m e t 宏观拓扑结构 生命特征进行研究的意义以及本文将要研究的重点问题，最后介绍了本文组织结构。 第二章根据网络理论和复杂网络理论，通过在路由器层将i n t e m e t 抽象成节点和边 的集合，分析了i n t e m e t 的复杂网络特征，同时针对i n t e r n e t 规模巨大，节点之间以及节 点和边之间相互作用复杂的问题，在对i n t e m e t 的统计特征进行了分析的基础上，提出 了运用统计学方法研究i n t e m e t 宏观拓扑结构的基本思想，并对本文所采用的统计数据 进行了分析。 第三章在对b a 模型以及演化适应原理分析的基础上，通过定义i n t e m e t 长期生存 效用和短期生存效用建立了i n t e m e t 宏观拓扑结构的演化适应模型，通过对该模型序参 量的求解和分析发现，i n t e r a c t 宏观拓扑结构的演化受到外界环境的影响，根据受到影 响的程度不同，长期生存效用和短期生存效用对i n t e m e t 宏观拓扑结构演化的贡献也不 同，从而使i n t e m e t 向着不同的拓扑结构方向演化，因此i n t e m e t 的宏观拓扑结构具有与 环境相适应的能力。 第四章首先论述了i n t e m e t 拓扑结构的稳定性，并且通过计算验证了i n t e m e t 的宏观 东北大学博士学位论文 第一章绪论 拓扑结构具有无尺度特征，对新增节点的出生和死亡规律的计算发现，i n t e m e t 上出生 和死亡的节点绝大多数都是连接度很低的节点，这样的节点占全部新出生节点或死亡节 点的9 7 以上。另外根据系统的代谢表现为熵值的变化的特点，本章通过定义i n t e m e t 标准结构熵，计算了i n t e m e t 近4 年来其标准结构熵随时间而变化的规律，并对i n t e m e t 宏观拓扑结构演化过程中存在的信息代谢进行了验证。 第五章在上章内容的基础上，对i n t e m e t 拓扑结构自复制的必要性进行了分析， 通过对i n t e m e t 节点平均连接度的关联维数、最大l y a p u n o v 指数和k o l m o l o g o r o v 熵的 计算发现i n t e r n e t 的宏观拓扑结构具有混沌和分形的特点，并由此验证了i n t e m e t 宏观拓 扑结构的演化过程中存在着自复制过程。而对i n t e r a c t 节点数和边数演化的计算发现， 节点的连接度越高，与其建立连接的节点数和边数也越多，呈现出马太效应的特点。 第六章通过对i n t e m e t 平均最短路径、度分布的幂指数和节点平均连接度这些 i n t e m e t 宏观拓扑结构的特征物理量的计算结果与在精确复制条件下这些特征量的理论 值的比较后发现，计算值和理论值存在着差异，分析它们之间的差异可知i n t e m e t 的宏 观拓扑结构在演化过程中存在着突变。 第七章总结了全文并对未来的工作进行了展望。 东北大学博士学位论文 第二章i n t e m e t 特征分析 第二章i n t e r n e t 特征分析 2 1i n t e m e t 的复杂网络特征 2 1 1 网络及其特征物理量 网络一词是社会学家斯梅尔( gs i m m e l ) 在1 9 2 2 年不经意创造的，这个词汇在自然 科学和社会科学领域中使用得如此频繁，以至于该词已成为社会网络f “】分析方法的主导 词汇；而且在今天的自然科学中，网络研究也成为重要课题。今天的社会已经成为网络 的社会，人们的日常生活已经无法离开网络，如电视网络、i n t e m e t 、电力网络等。网络 是一个由许多节点及连接节点的边组成的集合，其中节点用来代表真实系统中不同的个 体，而边则用来表示个体间的关系，如果两个节点之间具有某种特定的关系则认为有边 相连。 【定义2 1 】网络( n e t w o r k ) - 称n = ( 以丘z ，1 9 为一个网络，如果 ( 1 ) g = ( p ，e ) 是一个有向图； ( 2 ) c 是e 上正整数，称为容量函数，对于每条边e ，c m 称为边e 的容量； ( 3 ) x 与y 是矿的两个非空不相交子集，分别称为g 的发点集与收点集， ，= ( 工1 x u y ) 称为是e 的中间点集，x 的顶点称为发点( 源) ，y 的顶点称为收点( 汇) ， ，的顶点称为中间点。 在图论中网络g = ( y ，e ) 是指由点集嗍和边集e 同组成的图，且五矧中的每条边 e i 有w q 中的一对点( 地v ) 与之对应。记顶点数为n = l v i ，边数为工= i 剧。如果任意( 虬v ) 与 ( v ，。) 对应同一条边，则称为无向网络，否则为有向网络【4 5 】；如果任意蚓：1 则称为无权 网络，否则为加权网络。 在统计物理学中把网络看成包含大量个体以及个体之间相互作用的系统，是把某种 现象或某类关系抽象为个体( 节点) 以及个体之间相互作用抽象成边而形成的图。 网络可用来描述节点之间的相互关系，如人与人之间的社会关系【4 6 1 1 4 7 1 1 4 8 1 1 4 9 、物种