（生物医学工程专业论文）无尺度网络结构化成因研究.pdf

国防科学技术大学研究生院硕士学位论文 a bs t r a c t as c a l e - f r e en e t w o r ki sac l a s so fc o m p l e xn e t w o r kw h o s ed e g r e ed i s t r i b u t i o n f o l l o w sap o w e rl a w a n a l y z i n gt h ee v o l u t i o no fas c a l e - f r e en e t w o r ka n dg i v i n ga p r o p e rf o r m a ld e s c r i p t i o na r eh o ti s s u e si nt h er e s e a r c ho fc o m p l e xn e t w o r k b am o d e l i sc u r r e n t l ym o s ta c c e p t e dm o d e le x p l a i n i n gt h ef o r m a t i o no fs c a l e f r e en e t w o r k s i n s h o r t ，t h em o d e ls i m u l a t e st h ee v o l u t i o no fn e t w o r ks t r u c t u r e sa sad i r e c t e ds e l e c t i o n p r o c e s s t h i sc o n f l i c t sw i t ht h ef a c tt h a tt h es t r u c t u r a lf o r m a t i o no fan e t w o r ki sa c o m p l e xp r o c e s sa f f e c t e db ym a n yf a c t o r sw i t h o u ta n ye x p l i c i td i r e c t i o n s i nt h i sp a p e r ， w et r yt od e v e l o pa na l t e r n a t i v em o d e lc o m b i n i n gg r a p ht h e o r ya n dg a m et h e o r y ，a n d c o n c l u d et h a tf o r m a t i o no fc o m p l e xn e t w o r k sa r et h er e s u l t so fb o t hc o m p e t i t i v ea n d c o o p e r a t i v ef a c t o r s t h em a i nw o r ka n dc o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： i ) n e w a l g o r i t h m sa r ed e s i g n e da n di m p l e m e n t e db a s e do n an o v e lp e r s p e c t i v eo f a n a l y z i n gt h ee v o l u t i o np r o c e s so fas c a l e - f r e en e t w o r k u s i n ge s s e n t i a l l yt h e c o r ec o n c e p t si nt h et h e o r yo fg a m e so i lg r a p h ，m o r et h a nf i v ef a c t o r ss u c ha s k i n s e l e c t i o n ， d i r e c t r e c i p r o c i t y ， i n d i r e c t r e c i p r o c i t y ， n e t w o r k r e c i p r o c i t y ，g r o u ps e l e c t i o n a r ec o m b i n e dt o g e t h e rt om o d e lt h en e t w o r k e v o l u t i o n b a s e do nt h ea n a l y s i s ，t h eg a m ea l g o r i t h mb a s e do ne v o l u t i o n a r y r u l e si sd e s i g n e da n di m p l e m e n t e du s i n gc + + l a n g u a g e i i ) c o m p e t i t i o na n dc o o p e r a t i o na r et h ei n t e r n a lr e a s o n sf o rt h ef o r r f l a t i o no fa s c a l e f r e en e t w o r kb a s e do n o u ra n a l y s i sa n ds i m u l a t i o n f i r s t l y ，s e v e r a l e x p e r i m e n t sa r ed e s i g n e db yc h o o s i n gd i f f e r e n tg a m es t r a t e g i e sa n ds e r i n g p r o p e rp a r a m e t e r st o v a l i d a t et h er a t i o n a l i t yo fo u ra l g o r i t h m s t h em a i n c o n c l u s i o ni s ：i ti st h ec o m p e t i t i o na n dc o o p e r a t i o na n dt h e i rc o m p l e x i n t e r a c t i o n st h a tw o u l dr e s u l ti nt h es c a l e f r e es t r u c t u r eo fan e t w o r k w e d e f i n ee x t e r n a lf i t n e s sa st h ea b i l i t yt ob e c o m es u c c e s s f u lw h e r e a si n t e r n a l f i t n e s sw o u l db et h eq u a l i t yr e l a t e dt oo n e sr e p u t a t i o na n ds k i l lt oi n t e r a c tw i t h o t h e r s o u rr e s u l t st h u ss h e dl i g h to nt h ee x p l a n a t i o n so ft h r e ei n t r i g u i n gd e t a i l s o fn e t w o r kf o r m a t i o n s ：1 ) t h ep l a y e rw h ob e c o m e sf i t t e re x t e r n a l l yw o u l d a p p e a rt oa l s on e e dt oh a v eh i g h e ri n t e r n a lf i t n e s s ；2 1t h eo n ew h oc o o p e r a t e s w i mo t h e r sw h i l en o ta f f e c t i n gi t so w ni n t e r e s t sc o u l di nf a c ta c q u i r eb o t h h i g h e re x t e r n a la n di n t e r n a lf i t n e s s ；3 ) i ft h eo n ew h o h a sl i t t l ee x t e r n a lf i t n e s s t ob e g i nw i t h , h ec o u l ds t i l lb e c o m es u c c e s s f u li fh eo w n sh i g hu n d e t e r m i n i s t i c t h e s eo b s e r v a t i o n ss u g g e s tt h a tn e a r l ya l lo ft h es c a l e - f r e en e t w o r k sm i g h t s h a r es i m i l a ru n d e r l i n gm e c h a n i s m s k e yw o r d s ：c o m p l e xn e t w o r k , e v o l u t i o n ，s c a l e f r e e ，g a m e so ng r a p h ，c o m p e t i t i o n ， c o o p e r a t i o n 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表1 1 无尺度网络示例一7 表2 1 两两博弈矩阵1 4 表2 2 重复囚徒困境策略选择示例1 6 表2 3 以牙还牙一一直合作1 7 表2 4 以牙还牙一一直不合作1 7 表3 1 囚徒困境付出值矩阵2 l 表3 2 五种机制矩阵列表2 1 表3 3p a y o f f 转移矩阵：2 3 表3 4 博弈者关系图表示2 4 表4 1 用户设置参数列表2 8 表4 2 “改变比较标准网络评价参数列表2 9 表4 3 “政变对待对方态度 网络评价参数列表3 0 表4 4 “改变同源性系数设置标准 网络评价参数列表3 1 表4 5 “改变协同性系数设置标准 网络评价参数列表3 1 表4 6 “改变c b 比率”网络评价参数列表3 2 表4 7 “改变分组个数 网络评价参数列表3 2 表5 1 个体适应值分布情况列表3 9 表5 2 两部分个体 合作 行为统计列表3 9 第1 v 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1 随机网络和无尺度网络分布比较。4 图1 2 互联网络结构5 图1 4b a 模型示例9 图3 1 算法流程图2 5 图4 2 网络结构变化过程3 5 图4 31 0 0 个结点网络度分布情况3 6 图4 41 0 0 0 个结点网络度分布情况3 7 图4 51 0 0 0 0 个结点网络度分布情况3 8 + 图5 1 两部分个体形成网络子图分析结果4 0 图5 2 原始个体“外在适应值 分布4 2 图5 3 “不确定性 与“外在适应值的关系4 3 图5 4 观察个体“同源性 系数分布情况4 4 图5 5 “外在适应值 和“内在适应值”的变化情况4 5 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：垂屋廑圜终箜控焦盛固珏究 学位论文作者签名：筮握藕兰 日期： 碱年j ) 月j 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：玉屋廑圆签缱掐焦盛圈煎究 学位论文作者签名：熬捆螽兰 日期： 埘年i 月f 日 作者指导教师签名：薹包i 照日期：渐年f 工月哆日 国防科学技术大学研究生院硕士学位论文 1 1 1 复杂网络概述 第一章绪论 1 1 课题背景 1 1 1 1 什么是复杂网络 复杂网络一直是全球学者研究的热门课题。早在1 9 2 2 年，社会学家斯梅尔就 在不经意间创造了这个词汇。但他没有想到这个词汇会在社会学领域使用如此频 繁，并成为社会网络分析方法的主导词汇，而且现在已经广泛渗透到自然科学研 究的各个领域。计算机技术的快速发展使得对复杂网络的研究从量上和质上都达 到一个新的高度，进而出现了对复杂网络的研究热潮。 众所周知，点和边共同构成网络的两要素。其中点表示网络中的研究对象，研 究对象之间的联系构成连接它们的边，而复杂网络则是点与点之间连接关系较复 杂的一类网络的总称。可以说，我们每天都生活在自然界和人类自身编织的一张 张“网中：互联网、电力网、航空网、人类社会网络、新陈代谢网络、蛋白质 相互作用网络复杂网络无处不在，它们的影响显而易见。 1 1 1 2 复杂网络研究模型 现实世晃中的复杂网络结构一般可分为规则网络( r e g u l a rn e t w o r k ) 、随机网 络( r a n d o mn e t w o r k ) 以及无尺度网络等三类，针对不同的网络，人们提出了相应 的网络模型：随机网络模型、小世界网络模型和无尺度网络模型。 在2 0 世纪5 0 年代匈牙利数学家p a u le r d o s 和a l f r e dr e n y i 将具有随意连接关 系的网络描述为随机网络。这是最简单也是最为众人熟知的复杂网络。在图论中， 随机网络的构成可以理解为：给定n 个顶点，从c 2 n 条边中任意选择k 条边( k c 2 n 。 k = c 2 n 为全连通网络) 形成的网络即为随机网络【1 1 。由于随机网络的结点度遵循泊 松分布，大多数结点度分布相似，因此人们直觉上认为现实世界的许多网络均为 随机网络。但随着对复杂系统研究的深入，许多科学家开始重新思考这个模型范 例并提出：隐藏在这些不同复杂系统后面的网络结构真是随机的吗? 直觉告诉我 们，这些复杂系统必定遵循着某些组织原则，这些原则应该在某种程度上决定着 它们的拓扑结构。但如果这些复杂网络的拓扑结构的确背离了随机图，则我们需 要发展新的工具和准则去量化潜在的组织原则【。 小世界模型是w a t t s 和s t r o g a t z 在1 9 9 8 年提出的网络模型，这篇文章发表在 n a t u r e 杂志上，当时引起了不小的轰动。它具有与规则网络结构类似的聚类性质， 也具有与随机网络类似的较小平均路径长度。因此，可以说，它将完全规则网络 第1 页 国防科学技术大学研究生院硕士学位论文 和完全随机网络联系了起来。 无尺度模型是由b a r a b a s i 和a l b e r t 在1 9 9 9 年发表在s c i e n c e 上的一篇文章中提 出的网络模型。他们发现许多实际网络中大多数结点只与其他少数几个结点连接， 仅有少数几个结点具有很高的度分布值。因为该分布没有明显特征长度，因此这 类网络又被称为无尺度网络( s c a l e f r e e n e t w o r k ) 6 1 。 1 1 1 2 复杂网络研究理论 由以上论述可以总结出在复杂网络研究领域主要存在三种理论： ( 1 ) 小世界理论。广为人知的六度分割理论是小世界理论的一个形象描述【7 】。 这是上世纪6 0 年代，美国哈佛大学的社会心理学家米尔格伦提出的理论。他指出， 无论人类社会规模多么大、人类关系多么复杂，2 个陌生人之间最多通过6 个人就 可以将彼此联系起来。看似难以置信的结论其实反映了世界具有小世界特性：无 论网络规模如何，任意两个结点之间总存在一条长度非常短的最短路径。 ( 2 ) 集群理论。集群理论是社会学中的一个基本观点，在1 9 9 4 年w a t t s 和 s t r o g a t z 将该观点命名为“三倍传递比 ( f r a c t i o no ft r a n s i t i v et r i p l e s ) 。它描述了 社会网络中的一个普通现象：朋友圈中的每个成员都认识彼此。这种现象也被称 为集团模式。 集群系数是描述集团模式的一个重要参数，它实际上从理论上定量反映了网络 的聚集程度。对于网络中的一个结点来说，我们将该结点与其邻居结点形成的子 网络中实际存在的边数，除以这些结点构成的全连通图所拥有的边数，就可以得 到这个结点的集群系数。经研究发现，在大多数真实网络中，其集群系数比与之 相对应的随机网络( 比如将对应随机网络定义为与真实网络具有相同结点数和边 数的网络) 的集群系数大很多。 ( 3 ) 度分布理论。网络中一个结点的度定义为与该结点相连的边的数量。在 无向图中，与该结点连接的边数就是这个结点的度；在有向图中，度分为出度和 入度，其中出度表示由本结点指向另外结点的边数量的总和，入度表示由其他结 点指向本结点的边数量的总和。按照结点的度分布，我们可以将网络分为随机网 络和无尺度网络。随机网络的度分布是一个泊松分布，在网络平均度处取得最大 值。无尺度网络是指度分布具有幂指数分布特性的网络，它背离了随机网络的泊 松分布特性。有趣的是，现实世界中很多网络均具有这样一种无尺度特性。 科学家发现绝大多数现实世界中的复杂网络都具有如下几个基本特征【8 1 ： ( 1 ) 网络行为的统计性：网络结点数可以有成百上千万，甚至更多，从而使 得大规模性的网络行为具有统计特性。 ( 2 ) 结点动力学行为的复杂性：各个结点本身可以是各非线性系统具有分岔和 混沌等非线性动力学行为。 第2 页 国防科学技术大学研究生院硕士学位论文 ( 3 ) 网络连接的稀疏性：一个n 个结点的具有全局耦合结构的网络的连接数目 为o ( n 2 ) ，而实际大型网络的连接数目通常为o ( n ) 。 ( 4 ) 连接结构的复杂性：网络连接结构既非完全规则也非完全随机。( 5 ) 网络的 时空演化复杂性：复杂网络具有空间和时间的演化复杂性，展示出丰富的复杂行 为，特别是网络结点之间的不同类型的同步化运动( 包括出现周期、非周期 混 沌 和阵发行为等运动) 。 目前，复杂网络研究的内容主要包括：网络的几何性质，网络的形成机制，网 络演化的统计规律，网络上的模型性质，以及网络的结构稳定性，网络的演化动 力学机制等问题【9 j 。 复杂网络的研究，为研究人员提供了一种复杂性研究的新视角、新方法，并且 提供了一种比较的视野。我们可以在复杂网络现有研究理论的指导下，对各种复 杂网络进行比较、分析和综合概括。 综上所述，由于网络的现象涵盖极其广泛，因此对网络的研究很有意义。如果 我们发现一种概括它们的共同特性的观点和方法，则能够抓取这类网络的关键， 形成深入的认识，从而更好的指导人们的生产生活。 1 1 2 无尺度网络概述 1 1 1 2 无尺度网络的发现 在1 9 5 9 年，两位匈牙利科学家e r d s 和其合作者r e n y i 提出通信和生命科学中 的网络可以通过在网络结点之间随机布置连接的边来进行模拟实现。 随机网络的分布呈现的是钟形泊松分布形式，这就意味着它在直观上具有“两 头小，中间大 的感觉：大多数结点的度都集中在平均度附近，只有少数结点拥 有很小或很大的度分布。在数学上，随机网络被描述为指数网络，也就是说，随 机网络具有指数特性：一个结点连接其他k 个结点的概率，会随着k 值的增大而 呈指数级递减。 因为随机网络分布的直观合理性，科学家们相信随机网络理论可以用来解释世 界上所有网络的分布情形。 1 9 9 8 年，b a r a b a s i 与美国圣母大学的郑夏雄和a l b e r t 合作对万维网进行研究， 他们主观认为人们会根据兴趣浏览网页，而每个人的兴趣几乎都不一样，因此选 择的网页类型和数量也会多种多样，因此万维网实际上也会是一个随机网络，呈 现钟形的泊松分布。为了验证之前所想，研究人员专门设计了一个软件，它可以 从一个网页跳转到另一个网页，尽可能多的搜集网上所有的连接，并计算每个网 页的总体连接数。 然而出乎人意料之外的是，实验结果和他们所预想的大相径庭：少数几个结点 第3 页 国防科学技术大学研究生院硕士学位论文 具有很高的连接度( 大概1 0 0 0 个左右) ，由它们串成了整个万维网。与之相反， 8 0 的页面连接数不超过4 个。更加惊人的事实是：在进行的后续网络调查显示中 发现一份文件的网页链接数超过了2 0 0 万个。 1 1 2 2 无尺度网络特性 这个发现颠覆了科学家们关于“世界上所有网络均为随机网络”这一猜想。在 b a r a b a s i 等人的后续理论研究中，他们指出万维网网页的连接数遵循“幂次定律 ： 任何结点与其他k 个结点相连的概率与1 k 成j 下比。因为这样的度分布没有明显的 特征度分布，因此具有幂次定律的网络也被称为无尺度网络。 从直观图上我们可以感觉到幂次定律和随机网络理论的截然不同。如图1 1 所 示，随机网络遵循泊松分布，这种分布有一个峰值；而无尺度网络遵循幂次定律， 呈幂指数递减分布，在对数坐标上为一条斜向下的直线形式。 节 点 数 度分布 节 点 数 度分布 随机网络钟形泊松分布曲线 无尺度网络幂次定律分布曲线 图1 1 随机网络和无尺度网络分布比较 1 1 2 3 无尺度网络示例 我们在现实生活中可以找到很多随机网络和无尺度网络的例子。据研究表明， 美国高速公路系统可以描述为随机网络，其大部分的高速公路连接数目都相差无 几；相反，美国航空网则可以模拟为无尺度网络，结点之间的分布遵循幂次定律， 少数结点拥有绝大多数连接，大部分结点只有少数连接。 互联网络的结构图如图1 2 所示，该图有助于对无尺度网络的直观理解。 第4 页 国防科学技术大学研究生院硕士学位论文 图l2 互联网络结构 注：图i2 引自参考文献 5 0 1 仔细观察该幅图我们会发现有许多呈星状散布的结点，它们称为集散结点。从 字面上理解，集散结点的含义就是该结点的入度和出度都很高，它“负责”和其 他许多结点进行连接，从而实现整个互联网的正常运作。从另一个角度来说，我 们能够从浩若烟渺的网络结点中轻易找到这些集散结点，说明它们的数量比起整 个互联网中的结点而言，简直屈指可数。 自从b a r a b a m 等人发现万维网具有无尺度特性之后，许多研究人员对很多现 实网络进行了一系列后续研究。值得注意的是，他们发现许多不同的系统中部具 有无尺度特性“”。 在实体网络研究方面，美国加州大学河滨分校的f a l o u t s o s 、加拿大多伦多大 学的f a l o u t s o s 以及美国卡耐基梅隆大学的f a l o u t s o s 这三位电脑科学家兄弟发 现以光纤或其他通信线路连接的路由器拓扑结构其有无尺度特性f l q 。 在社会网络研究方面，美国波士顿大学和瑞典斯德哥尔摩大学的科学家的共同 研究显示，瑞典民众的性关系网络也遵循幂次定律：尽管大部分人终其一生只有少 第5 页 国防科学技术大学研究生院硕士学位论文 数几个性伴侣，但有少数人( 集散结点) 的性伴侣多达数百人。德国基尔大学的 b o r n h o l d t 所做的研究表明，电子邮件所连结的人际网络，也可能具有无尺度特性 i l o 】。渡士顿大学的r e d n e r 证实，由科学论文之间引用关系所连结的网络，同样也 可视为无尺度网络【l 。7 1 。美国密歇根大学安娜堡分校的n e w m a n 研究了包括物理和计 算机等一些学科的科学家之间合作关系网络，他发现这些网络也同样具有无尺度 特性，这也印证了之前研究人员专门针对数学家和神经科学家所做的研究【l 引。 在商业合作网络研究方面，美国斯坦福大学的w p o w e l l 、加州大学i r v i n e 分校的r w h i t e 、亚利桑那大学的w k o p u t 以及密歇根大学的s m i t h 共同对美国 生物技术产业联盟网络的形成进行了研究。他们发现在这个产业联盟网络中存在 特定的集散结点：g e r l z y m e 、c h i r o n 和g e n e n t e c h 等公司。这几个公司与其他公司 相比，拥有的合作关系数量数不胜数。意大利的研究者利用意大利锡耶纳大学的” 制药工业数据库”所提供的数据( 据报道，该数据库目前包括超过7 2 0 0 个组织之间 所签定的约2 0 1 0 0 个研发协议) 发现，p o w e l l 等人所发现的那些属于集散结点的公 司事实上也属于某个无尺度网络【l 圳。 在生物网络研究方面，美国西北大学的细胞生物学家o l t v a i 等人发现在古菌 域、细菌域和真核生物三大生物领域的4 3 种不同生物里，都存在有无尺度的细胞 代谢网络结构。在这些细胞代谢网络中，细胞通过分解复杂分子燃烧食物并释放 能量。其中每个分子就是一个结点，而生化反应组成连接结点之间的边。研究人 员发现，大部分分子只参加一两种生化反应，但有极少数分子( 会参与绝大部分的 反应，例如水和三磷酸腺苷。同时研究人员还发现，细胞中蛋白质的交互网络也 是无尺度的( 如图1 3 所示) 。在这种网络中，蛋白质构成网络中的结点，它们 之间若存在相互反应则将这两种蛋白质连接起来，构成网络的边。另外，研究人 员在研究酵母时发现，存在于这种最简单的真核细胞体内的数千个蛋白质所构成 的相互作用网络也存在无尺度特性：绝大多数蛋白质只与除自己之外的两三种蛋 白质进行相互作用，而只有极少数蛋白质与其他数个蛋白质进行作用。研究人员 在幽门螺杆菌中也发现了与酵母蛋白质交互作用类似的蛋白质作用网络。值得一 提的是，幽门螺杆菌是一种与酵母截然不同的简单细菌【2 刚。 另外一个有趣的现象来源于好莱坞演员网络。这个网络因“六度凯文贝肯 的 游戏而变得出名。游戏规则是出题人首先给出一个电影明星的名字，然后让答题 人用这个电影明星与其他演员共同出演的电影名称与凯文贝肯联系起来。结构研 究发现在好莱坞中任何一个演员至多通过另外6 个演员就能够和凯文贝肯扯上联 系，且大部分演员只与少数几个其他演员有联系，而只有极少部分演员与其他数 千个演员有过合作关系。顺便提一下，这些“集散”演员包括r o ds t e i g e r 和d o n a l d p l e a s e n c e ，而凯文贝肯自己只排到8 0 0 多位。 第6 页 国防科学技术凡学研究士院碗 学忙睦文 豳】3 酵母体内蛋白质交互作用图 注：图i3 引白参考文献 2 0 1 表l _ l 对上述网络类型进行了总结归纳。 表i l 无尺度阿络示例 网络示例结点构成边构成 万维网网页网页中的连接地址 因特网路由器光纤及其他物理连接 社会关系网络人人与人之间具有关系 科学研究合作网络 科学家合作撰写论文 商业合作网络 商业公司参与合作 细胞分子代谢网络对食物进行消化参与相同的生化反应 从而释放能量的分子 好莱坞演员网络 演员 出演同一部电影 1 i 2 4 无尺度网络结构化成因研究意义 蔓茎圭：型堂窒堕茎堕旦垫墼兰：垄里堕垂垦星堕塑垫塑至：婆些垄型! ! 垄i 第7 页 国防科学技术大学研究生院硕士学位论文 一个重要的问题：为什么像细胞和因特网这样本质上不同的系统，却具有相同的结 构并遵从相同的规律? 弄清无尺度网络结构化的成因可以更好的指导人们的生产 生活，从而在最大程度上提高国力。 就拿与人类日常生活密切相关的因特网、万维网来说，这样的无尺度网络具有 极强的承受能力，因为大多数结点的连接数极其少，所以就算这些结点绝大部分 出现了故障，对整个网络的影响也微乎其微。与此同时，如果集散结点出现了故 障，整个网络就会陷入瘫痪境地。因此说，因特网和万维网承受不住蓄意的攻击 和破坏。对计算机网络有了这样的认识后，我们就可以采取对集散结点进行保护 等措施加强因特网和万维网的性能。 作为生活在人类社会中的一员，大家都知道传染疾病的防御始终是关系国计民 生的大事，而控制传染源就显得尤为重要。因为知道人类社会关系网络实际上也 是一个无尺度网络，则只要我们找到了传染源并对其接种疫苗就能够在短时内有 效控制疾病的传播( 当然对群体内每个人接种疫苗是最安全可靠的办法) 。 在商业宣传中，已经有很多市场营销人员发现有一些消费者在推广新品方面具 有其他大多数消费者无法比拟的优势。因此利用这种无尺度特性，可以使营销人 员集中精力去找“集散”消费者，从而提高销售效率，最大程度增长销售业绩。 综上所述，对无尺度网络结构化成因的研究具有重大应用前景。研究无尺度网 络的意义用一个成语概括就是“庖丁解牛 。只有了解了无尺度网络的结构特性、 演化机制等内在属性，人们才能够对它有深入的认识，才可以解决在实际无尺度 网络中存在的问题。 1 2 研究现状 传统研究复杂网络的方法都存在于图论这个领域中。自从匈牙利数学家p a u l e r d o s 和a l f r e dr e n y i 在1 9 5 0 年代首次用图论对随机网络展开研究之后，当把图论 应用到规则图的研究中时，它就被认为是对一个复杂网络最简单也最直接的认识。 e r d o s r e n y i 模型的建立过程是：给定n 个结点，以概率p 连接每对结点，形 成一个大约有p n ( n 1 ) 2 条边随机分布的图。数年来这个模型一直是科学家们研究 复杂网络的指导思想。 随着研究工具的改进和研究方法的深入，我们认识到现实生活中的网络大体可 以分为两类：小世界网络和无尺度网络。前者服从泊松分布，后者服从幂指数分 布。 幂指数度分布的发现导致建立了多种无尺度模型，通过关注网络的动态演化从 而提出一种关于网络演化的通用理论，即无尺度网络具有增长性和偏好连接的特 性。具体来说，新进入网络的结点会选择原本度较高的结点进行连接。 第8 页 国防科学技术大学研究生院硕士学位论文 气；j ：鸳 i j ：膏之r - 、沁 图1 4b a 模型示例 注：图l 。4 引自参考文献【2 1 】 0 i 在图1 4 所示图例中，无尺度网络的结点从2 个成长到1 1 个。当新结点( 绿色) 决定建立连结时，总是倾向于和已经拥有较多连结的结点( 红色) 相连结，成长性 和优先连接这两种基本机制，最终会造成拥有大量连结的集散结点所控制的系统 2 i 】 o 从以上对无尺度网络的分析模型可以看出，单纯从统计力学的角度对网络的成 因进行解释具有局限性：偏好连接是如何产生的? 到目前为止，科学家还未找到 一个通用的合理答案。这样的问题引发了国际上对网络结构化成因的研究热潮。 在2 0 0 0 年初k u m a r 和k l e i n b e r g 等人就展开了对万维网幂指数特性的成因研 究。他们认为关于一个主题的新网页会和该主题相关的旧网页存在链接关系，并 由此提出了一种复制机制模型。在这个模型中，每个时间步新加入的结点会和网 络中原有的一个结点进行连接，这个随机选出的被连接结点称为“原型 结点 ( “p r o t o t y p e ”n o d e ) 。新结点的出边根据以下方法进行分布：以概率p 随意连 接任意一个结点，以概率l - p 选择原型结点的第i 条边窿1 。v a z q u e z 在2 0 0 0 年受 文章引用网络的启发提出了与概率等式方法( r a t e e q u a t i o na p p r o a c h ) 不同的另 一种模型：漫步机制( w a l k i n gm e c h a n i s m ) 。当人们研究一个新领域时，通常会关 注一些非常重要的论文并沿着它的参考文献进而找到其他相关文章。很显然，这 是一个递归的过程。v a z q u e z 将算法描述为：首先从一个孤立结点开始，在每一个 时间步加入一个新结点，它随机的与系统原有结点进行连接，接着沿着它所连接 旧结点的出边以概率p 连接目标结点。第二步一直重复进行直到在系统中再找不 到目标结点。事实上，这个算法与应用于寻找网络集群结构的宽度优先遍历搜索 类似，只是多加入了概率连接的因素口】。在2 0 0 1 年k r a p i v s k y 和r e d n e r 提出了称 为边重构的模型，它在数学理论基础上等同于复制模型。在这个模型中，每一个 时间步将一个新结点加入系统，新结点以概率1 - r 连接到随机选择的结点i 上， 以概率r 连接到结点i 的祖先结点j 上( 结点j 为结点i 首次进入系统时连接的 结点) h 1 。在诸多规避偏好连接来探索网络结构化成因的新算法中，最简单的可能 第9 页 麓 黪，。 参。 叠一 o 囊， |、 _ r ， 一。 一慧 ： 詹 嬉， ，io。 、+ t 弋 ， 叶 国防科学技术大学研究生院硕士学位论文 要数d o r o g o v t s e v ，m e n d e s ，和s a m u k h i n 在2 0 0 1 年提出的模型。在这个模型中， 每个时间步新加入的结点将连接随机挑选出来的边的两端点。因而一个结点形成 一条新边的概率将与它的度成正比璐1 。实际上该算法模型与b a 模型所强调的偏好 连接完全一致。 从以上的模型概述中我们可以看到，对网络结构化成因的解释都主要集中在统 计力学和概率等式方法上，统计力学方法的局限性已在前面进行了详细论述，而 概率方法还未出现一个对网络结构成因的普适解释，它们都是针对某一特定网络 进行的论述。最重要的一点是，这两种方法存在一个共同的缺陷：它们都将网络 结构化的形成描述为一个优化过程。众所周知，网络结构化的形成绝不是一个纯 粹的优化过程，而是由许多因素共同作用的结果。 为了更进一步探究网络结构化成因，找到一种对网络结构化形成的普适合理的 解释，我们需要对分析工具进行拓展。 博弈论考虑博弈中个体的预测行为和实际行为，并研究它们的优化策略。博弈 的过程实际上是一个根据自身情况结合周围环境进行折中和做出决策的过程瞳别。 它的这种特点使其在经济学、社会学、生物进化动力学等诸多领域有广泛应用口3 。 为了探究无尺度网络结构化成因，我们将研究离散个体经过特定博弈过程是否可 以形成结构化网络形式。如果该博弈过程所得结论合理，可以将该过程视为对无 尺度网络结构化成因的一种解释。 具体来说，我们考虑将个体描述为图上的点，制定尽可能复杂的博弈规则策略， 使其两两之问发生博弈行为，若个体之间存在联系则在两者之间添加上一条边。 在经历了若干次搏弈过程后，待系统达到稳定时，研究此时网络的形成情况。如 果形成的网络具有无尺度的结构化特性，则认为该博弈过程是对无尺度网络结构 化成因的一种解释，否则再对算法进行改进，争取找到一种合理解释，并最终找 出导致网络结构化形成的内因。 1 3 本文主要研究内容 本文借鉴“图上博弈的基本理论哪! ，将研究的焦点集中在群体博弈上，综 合现有关于生物进化的五种规则，对每个博弈者赋予多个属性，设计搏弈过程的 相关规则，并设计实验进行模拟，以此探索无尺度网络的结构化成因。 为了给无尺度网络结构化的形成找到一种合理性解释，本文从生物进化起源入 手，选取n 个离散个体，假设初始时它们之间没有任何联系、彼此孤立。接着令 其根据本文算法设计的博弈过程进行交互，研究形成的网络结构及其本身所处状 态。实验证明，该n 个个体最终形成的网络具有无尺度特性，因此我们认为本文 算法描述的博弈过程和实验结论找到了对无尺度网络结构形成的一种与b a 模型迥 第1 0 页 国防科学技术大学研究生院硕士学位论文 然不同的解释。 本文的创新之处在于用博弈论和图论相结合的方法对无尺度网络结构化形成 原因进行了解释，指出“竞争和合作在复杂网络无尺度化过程中起重要作用( b a 模型中的“择优连接”实际上指出“竞争”是造成无尺度网络结构化的原因) 。 本文具体研究成果如下： 1 将图上博弈( g a m e so ng r a p h ) 的基本理论之“生物进化的五种规 则进行综合扩展，运用于解释无尺度网络结构化形成原因； 2 根据扩展的理论设计基于进化规则的博弈算法，考虑了比较复杂的博弈情 况，可以更真实的模拟诸多无尺度网络变化过程；基于c + + 语言编写程序，实现该 算法；从现实角度考虑设计了多个实验对该算法进行合理性论证； 3 通过分析博弈过程和个体属性的变化趋势，找到无尺度网络结构化形成原 因，得出关于个体属性的变化趋势及相互关系的结论。 1 4 论文结构 本文总共分六章。 第一章简要介绍了本文研究背景。本章首先对复杂网络进行概述，接着介绍了 无尺度网络的发现和研究现状，指出当前研究无尺度网络结构化的模型存在的主 要缺点，并说明了本文论题的研究意义。 第二章详细论述基于进化规则的博弈算法的理论基础图上博弈( g a m e so n g r a p h ) 。本章首先对图论和博弈论中与本文相关的基本概念和理论进行了简要介 绍，接着具体列举了图上博弈理论中关于生物进化的五种规则机制，为介绍本文 算法做铺垫。 第三章具体介绍基于进化规则的博弈算法。本算法借鉴第二章所列生物进化的 五种规则机制，并将其融合在个体所拥有的属性值和博弈过程中。为了更真实的 模拟现实世界诸多无尺度网络的形成过程，强调网络结构化的形成确实是多个因 素综合作用的结果，我们赋予每个个体多种属性，增加算法的不确定性，尽可能 模拟真实的博弈过程。本章最后列举了实现该算法的主要功能代码。 第四章重点阐述本文设计的多个试验，以验证算法的合理性。首先对实验平台 和环境进行了简单说明，接着详细介绍本文设计的多个实验，从多个角度对本文 算法的合理性进行了验证。实验结果表明，从实际出发选取博弈策略并设置参数 范围，所得网络结构的节点度分布更具明显的无尺度特性，这充分说明，基于进 化规则的博弈算法能够较真实的模拟无尺度网络的动态演化过程。 第五章是对实验过程的详细分析。本章对个体属性的变化过程和个体的博弈行 为进行研究，得出系列实验结论，包括“竞争和合作是导致无尺度网络结构化 第1 i 页 国防科学技术大学研究生院硕士学位论文 的原因”、“高不确定性和高协同性能够提高个体外在适应值 、 “个体的外在适应值越高，其内在适应值也高”、“利己的合作带来外 在适应值和内在适应值双赢的结果 等。 第六章对本文研究内容进行了归纳总结，并对未来研究工作进行了展望，指 出进一步的研究方向。 第1 2 页 国防科学技术大学研究生院硕士学位论文 第二章图上博弈概述 图论很早以来就被认为是描述网络形态最简单也是最直接的数学工具 4 0 4 2 1 ， 它已有2 0 0 多年的历史，近几十年来发展迅速，已经成为一个新兴的数学分支。 图论在自然科学和社会科学诸多领域均有广泛应用，计算机科学的许多领域都离 不开图论1 4 2 。 博弈论早在我国春秋战国时期就已具雏形。1 9 4 4 年v o nn e u m a n n 与 m o r g e n s t e m 首次提出了博弈论的概念【4 引。他们在博弈理论与经济行为( t h e o r y o fg a m e sa n d e c o n o m i cb e h a v i o r ) - - 书中对博弈论进行了首次全面的论述，提出了 “可以对冲突加以数学分析 的想法，并提供了相应术语。之后t u c k e r 发展了“囚 徒困境”( p r i s o n e r sd i l e m m a ) ，n a s h 发表了关于均衡的定义与存在性的文章1 4 7 】， 这两项工作奠定了当代非合作博弈理论的基石。与此同时，合作博弈理论 ( c o o p e r a t i v eg a m et h e o r y ) 也取得了丰硕成果，包括n a s h 和s h a p l e y 关于“讨价 还价博弈”( b a r g a i n i n gg a m e ) 的文章以及g i l l i e s 和s h a p l e y 关于“核 ( c o r e ) 的文章 【1 4 】 o 近年来，许多学者将图论与博弈论结合形成了图上博弈( g a m e so ng r a p h ) 理 论：将博弈者表示成图上结点，若两者之间存在关系则连接图上对应结点从而形 成边【2 2 1 1 4 5 1 4 6 1 。它通常用来解决