（计算机应用技术专业论文）复杂网络模型的构造与分析.pdf

东北大学硕士学位论文摘要 复杂网络模型的构造与分析 摘要 i n t e rn e t 作为当今人类社会信息化的标志， 其规模正以指数速度高速增长的同 时. 如今 i n t e r n e t的“ 面貌” 已与其原型 a r p a n e t 大相径庭， 依其高度的复杂性， 可以将其看作一个由计算机构成的“ 生态系统” 。 虽然 i n t e rn e t 是人类亲手建造的， 但却没有人能说出这个庞然大物看上去到底是个什么样子， 运作得如何。 对i n t e rn e t网络的研究带动了复杂网络研究的发展。 近年来， 复杂网络己 经成 为一个新兴的 研究热点。 如何通过对复杂网络模型的 研究， 揭示i n t e r n e t 网络系统 的规律， 就成了 摆在科学家及研究工作者面前的一个问 题。 过去科学家对i n t e rn e t 网络的研究主要集中在网络微观世界，包括网络的硬件设备、网络协议等等。 无 法认识到网络的宏观规律和特性。 本文就是针对这个问题，采取从复杂网络建模入手对复杂网络的宏观规律进 行研究。首先介绍了网络研究的背景与发展过程以及复杂网络系统研究的现状， 然后重点放在对复杂网络的建模过程的研究，设计了“ 复杂网络构造器” 来实现 对复杂网络模型的构造，不仅包括小世界网络模型、无标度网络模型也对经典规 则网络及随机网络进行了建模。 而且 对实际的复杂网络i n t e rn e t 网络也进行了建模 尝试。最后在构造出的复杂网络模型的基础上，设计了一种简单的传播算法对所 有的构造的网络模型进行了传播试验，已达到对网络模型的测试与验证。分析并 总结出网络拓扑影响传播特性的相关结论，希望是对复杂网络研究的一种有意义 尝试。 关键词 复杂网络 i n t e r n e t小世界 无标度 拓扑结构 建模 东北大学 硕士学位论文 a b s t r a c t t h e c o n s t r u c t i o n a n d a n a l y s i s o f c o m p l e x ne t wo r k mo d e l ab s t r a c t a s a s i g n o f t h e h u m a n i n f o r m a t i o n s o c i e t y , i n t e rne t i s k e e p i n g o n i n c r e a s i n g i n a n u n i m a g i n a b l e s p e e d . n o w a d a y s i n t e r n e t h a s b e e n w i d e l y d i v e r g e n t f r o m a r p a n e t , w h i c h i s a p r o t o t y p e o f i n t e rne t . b e c a u s e o f t h e p r e s e n t i n t e r n e t s c o m p l e x i t y , w e c a n a b s o l u t e l y r e g a r d i t a s a n e c o s y s t e m w i t h c o m p u t e r s b e i n g t h e c o m p o n e n t s . i t i s t h e h u m a n b e i n g w h o h a s b u i lt i n t e rne t , b u t n o b o d y c a n t e l l w h a t i t l o o k s l i k e a n d h o w i t r u n s e x a c t ly . t h e s t u d i e s o n i n t e rn e t b r i n g a l o n g t h e s t u d i e s o n c o m p l e x n e t w o r k . i n r e c e n t y e a r s , c o m p l e x n e t w o r k h a s b e c o m e a n e w h o t s p o t i n t h e c o m p u t e r s c i e n c e f i e l d . t h e r e i s s t i l l a q u e s t i o n a b o u t h o w t o d i s c o v e r t h e l a w s o f t h e c o m p l e x n e t w o r k s y s t e m i n t h e r e a l w o r l d b y r e s e a r c h i n g t h e c o m p l e x n e t w o r k m o d e l s . b e f o r e a b o u t t h e s t u d y o f i n t e rn e t s c i e n t i s t s f o c u s e d o n t h e m i c r o - w o r l d o f n e t w o r k i n c l u d i n g h a r d w a r e d e v i c e , n e t w o r k p r o t o c o l s a n d s o o n . s o i t i s v e r y d i f f i c u l t i n d i s c o v e r in g t h e m a c r o n e t w o r k r u l e a n d c h a r a c t e r i s t i c s . i n o r d e r t o s o l v e t h i s q u e s t i o n t h e a u t h o r a n a l y z e t h e c h a r a c t e r o f t h e c o m p l e x n e t w o r k s t u d y b e f o r e a n d a d o p t t o b u i l d n e t w o r k m o d e l s a n d d e s i g n t h e s p r e a d a r i t h m e t i c t o t e s t a n d v a l i d a t e t h e m . f i r s t i n t r o d u c e t h e b a c k g r o u n d a n d t h e p r o c e s s o f t h e c o m p l e x n e t w o r k a n d t h e a c t u a l i t y a b o u t t h e s t u d y o f c o m p l e x n e t w o r k . t h e n i t i s f o l l o w e d b y t h e k e y p a r t f o c u s e s o n t h e s t u d y o f t h e p r o c e s s o f b u i l d i n g t h e m o d e l o f c o m p l e x n e t w o r k . i n c l u d i n g n o t o n l y s m a l l - w o r l d n e t w o r k m o d e l a n d s c a l e - f r e e n e t w o r k m o d e l b u t a l s o r e g u l a r a n d r a n d o m n e t w o r k m o d e l . a t t h e s a m e t i m e b u i l d s a m o d e l o f i n t e r n e t . n e x t o n t h e b a s i s o f t h e a b o v e b u i l t c o m p l e x n e t w o r k m o d e l t h i s t h e s i s i s t o d e s i g n a s im p l e s p r e a d - a r i t h m e t i c a n d t e s t i t i n t h a t m o d e l . f i n a l l y t h e a u t h o r c o n c lu d e s s o m e s t u n - u p s a b o u t t h e n e t w o r k t o p o l o g y a n d i t s t r a n s m itt i n g c h a r a c t e r i s t i c s o n t h e b a s i s o f h i s s t u d y . h e r e t h e a u t h o r h o p e s w h a t h e h a s d o n e i s a m e a n i n g f u l a tt e m p t i n t h i s f i e l d . k e y w o r d s c o m p l e x n e t w o r k , i n t e rn e t , s m a l l wo r l d , s c a l e - f r e e , t o p o l o g y , mo d e l in g 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中所 取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表 或撰写过的研究成果， 也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了 明确 的说明并表示谢意。 学位论文作者签名: 日期: 消走 q/ : ， : 夕 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定:即学校有权保留并向国家有关部门 或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、 ( 如作者和导师同意网上交流， 请在下方签名; 学 位 论 文 作 者 签 名 : 玛走 导师签名: 签 字 日 期 : ? p 0 (, ， ，7 签字 东北大学硕士学位论文 第一章 绪论 第一章 绪论 1 . 1 复杂网络研究背景及现状 网络是一个由许多节点及连接节点的边组成的集合。其中节点用来代表真实 系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某 种特定的关系则连一条边，有边相连的两个节点被看作是相邻的。系统所表现的 网 络形式在现实世界到处可见。例如， i n t e m e t , t h e w o r l d wi d e w e b 、社会关系网 络或是其他在个人之间、组织之间、商业公司之间具有联系的网络，以及神经网 络、代谢网络、食物链网络、分布式的血管网络等。 自1 7 3 5 年数学家欧拉对著名的哥尼斯堡七桥问题的解答开创了图论的研究以 来。两百多年来，对网络理论的研究经历了三个阶段。在最初的一百多年里，科 学家们认为真实系统各因素之间的关系可以 用一些规则的结构表示，例如二维平 面上的欧几里得格子，它看起来像是格子体恤衫上的花纹;又或者最近邻环网， 它总是会让你想到一群手牵着手围着簧火跳圆圈舞的姑娘。到了十九世纪五十年 代末，数学家们想出了一种新的构造网络的方法，在这种方法下，两个节点之间 连边与否不再是确定的事情，而是根据一个概率决定，数学家把这样生成的网络 叫做随机网络，它在接下来的四十年里一直被认为是描述真实系统最好的网络。 直到最近儿年，由于计算机数据处理和计算能力的飞速发展，科学家们发现大量 的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计 特征的网络。 这样的一些网络被科学家们叫做复杂网络，对于他们的研究标志着 第三阶段的到来。 在复杂网络的诸多统计特征中最重要的是小世界效应和无标度特性。如果网 络中的两个节点可以通过一些首尾相连的边连接起来，我们就说这两个点是可达 的，并把连接他们所需要的最少的边的数目叫做他们之间的距离，显然，这两个 点之间的距离总是比网络拥有的节点总数要小。如果两个节点是不可达的，我们 就令它们之间的距离等于网络的节点总数。 把所有节点对的距离求平均，就得到 了网 络的平均距离。另外一个叫做簇系数的参数，专门用来衡量节点集聚成团的 情况。 对于某个节点，它的簇系数被定义为它所有相邻节点之间连边的数目占 可 能的最大连边数目 的比 例。 类似的，网络的簇系数则是所有节点簇系数的平均值。 研究表明，规则网络具有大的簇系数和大的平均距离，随机网络则具有小的簇系 数和小的平均距离。1 9 9 8年，物理学家通过以某个 很小的 概率改变规则网络中边 东北大学硕士学位论文第一章绪论 第一章绪论 1 1 复杂网络研究背景及现状 网络是一个由许多节点及连接节点的边组成的集合。其中节点用来代表真实 系统中不同的个体，而边则用来表示个体问的关系，往往是两个节点之间具有某 种特定的关系则连一条边，有边相连的两个节点被看作是相邻的。系统所表现的 网络形式在现实世界到处可见。例如，i n t e m e t 、t h ew o r l dw i d ew e b 、社会关系网 络或是其他在个人之间、组织之间、商业公司之间具有联系的网络，以及神经网 络、代谢网络、食物链网络、分布式的血管网络等。 自1 7 3 5 年数学家欧拉对著名的哥尼斯堡七桥问题的解答开创了图论的研究以 来。两百多年来，对网络理论的研究经历了三个阶段。在最初韵一百多年里，科 学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平 面上的欧几垦得格子，它看起来像是格子体恤衫上的花纹；又或者最近邻环网， 它总是会让你想到一群手牵着手围着篝火跳圆圈舞的姑娘。到了十九世纪五十年 代末，数学家们想出了一种新的构造网络的方法，在这种方法下，两个节点之间 连边与否不再是确定的事情，而是根据一个概率决定。数学家把这样生成的网络 叫做随机网络，它在接下来的四十年里一直被认为是描述真实系统最好的网络。 直到最近几年，由于计算机数据处理和计算能力的飞速发展，科学家们发现大量 的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计 特征的网络。这样的一些网络被科学家们叫做复杂网络，对于他们的研究标志着 第三阶段的到来。 在复杂网络的诸多统计特征中最重要的是小世界效应和无标度特性。如果网 络中的两个节点可以通过些首尾相连的边连接起来，我们就说这两个点是可达 的，并把连接他们所需要的最少的边的数目叫做他们之间的距离，显然，这两个 点之间的距离总是比网络拥有的节点总数要小。如果两个节点是不可达的，我们 就令它们之间的距离等于网络的节点总数。把所有节点对的距离求平均，就得到 了网络的平均距离。另外个叫做簇系数的参数，专门用来衡量节点集聚成团的 情况。对于某个节点，它的簇系数被定义为它所有相邻节点之间连边的数目占可 能的最大连边数目的比例。类似的，网络的簇系数则是所有节点簇系数的平均值。 研究表明，规则网络具有大的簇系数和大的平均距离，随机网络则具有小的簇系 数和小的平均距离。1 9 9 8 年，物理学家通过以某个很小的概率改变规则网络中边 一1 东北大学硕士学位论文 第一章绪论 的连接方式构造出了一种介于规则网络和随机网络之间的网络，它同时具有大的 簇系数和小的平均距离，因此既不能当作规则网络处理，也不能被看作是随机网 络。后来物理学家把大的簇系数和小的平均距离两个统计特征合在一起称为小世 界效应，具有这种效应的网络就是小世界网络。 下面是图1 1 小世界网络结构示意图，左边的网络是规则的，右边的网络是 随机的，中间的网络是在规则网络上加上一点随机的因素而形成的小世界网络， 它同时具有大的簇系数和小的平均距离。 蚓1 1 小世界网络结构不葸图 f i g 1 1t h es t r u c t u r ef i g u r eo fs m a l l w o r l dn e t w o r k 科学家们对大量的真实网络，比如电力网络、计算机互联网、食物链网络、 演员关系网、科学家合作网络等等做了大量实证性的研究，发现它们几乎都是小 世界网络，同时，他们还发现了真实网络的另一重要统计特征，即节点度服从幂 律分布。节点度是指一个节点拥有相邻节点的数目，节点度服从幂律分布就是说 具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地 表示。幂函数曲线是一条下降相对缓慢的曲线，这使得我们不仅能在网络中发现 大量度很小的节点，还能找到一些度很大的节点。上面那幅图中的规则网络，随 机网络和小世界网络的节点度分布都不是幂律的，它们的分布区间非常狭窄，几 乎找不到偏离节点度均值较大的点。对于这样的网络，上述均值就可以被看作衡 量其节点度的一个特征标度，在这个意义上，我们把节点度服从幂律分布的网络 叫做无标度网络，并称这种节点度的幂律分布为无标度特性。 遗憾的是，就目前而言，科学家们还没有给出复杂网络精确严格的定义，从这 几年的研究来看，之所以称其为复杂网络，大致上包含以下几层意思：首先，它 是大量真实复杂系统的抽象；其次，它至少在感觉上比规则网络和随机网络复杂， 因为我们可以很容易地生成规则和随机网络，但就目前而言，还没有一种能够生 成完全符合真实网络统计特征的简单方法；最后，它还被认为是有希望解决“复 杂系统之所以复杂”这一至关重要问题的有力武器。 下面是图1 2 无标度网络的结构，1 9 9 9 年，物理学家给出了生成无标度网络 2 图1 2 无标度网络的结构图 f i g 1 2t h es t r u c t u r ef i g u r eo f s c a l e - f r e en e t w o r k 如前所述，关于网络的研究，数学家早在两百多年前就开始了，他们已经发 展出了成体系的理论与技术，而物理学家的进入只有不到五年的历史! 到底是什 么鼓动物理学家来趟这塘浑水，他们的到来有意义吗? 在我看来，研究对象特殊 的尺度效应是召唤物理学家到来的根本原因。数学家经典的网络理论，要么是包 含几十数百个顶点，可以清晰地画出来形成直观印象的网络；要么是讨论不含尺 度效应，可以精确求解的网络性质。“随机移走一个顶点会对网络的性能产生什么 样的影响? ”这个问题对于数学家是有意义的，但对于拥有几千万个节点，连接 方式复杂多样的真实网络而言，或许“随机移走3 的顶点会对网络性能产生什么 样的影响? ”这个问题更有意义。这个尺度的网络，是被物理学家称作“足够大” 的网络，对它们的研究，需要使用统计物理的方法。有的人可能会问，数学家除 了经典的网络理论外，还发明了一套随机图的理论，这套理论就是专门对付“足 够大”的网络的，统计力学的方法到底能不能得到随机图论不能得到的新的有意 义的结果呢? 正如在以后的章节中所要提到的，随机图论的方法的确在复杂网络 的研究中扮演了不可或缺的角色，我也会专门辟出章节介绍它的理论和应用，但 是，数学家的“足够大”和物理学家的“足够大”完全不是一个概念，虽然他们 都使用顶点数趋于无穷的假设。对于物理学家而言，平均场的近似，主方程的求 解，在网络顶点数达到百十万甚至几千万时，误差就已经可以接受了；而随机图 的大量有意义的结果，要求节点数在连续求取三次常用对数后还要比1 0 大，而在 我们的宇宙中，目前还没有任何一个有物理意义的数值达到如此的量级。 3 一 东北大学硕士学位论文第一章绪论 物理学家不仅在方法论上为网络研究注入了新的活力，而且大大地拓展了网络 研究的视野。他们不仅和数学家一样关心网络自身的性质，而且关注网络上进行 的各种物理过程和动力学行为，诸如传播、同步、自组织临界、玻色一爱因斯坦 凝聚等等，他们发现了网络结构对各种动力学行为的影响，并给出了很多虽不严 谨但很美妙的解释。这些工作很有可能会推动相关数学物理理论的发展。 下面是图1 3s c i 收录的关于复杂网络的研究论文统计图，统计了从1 9 9 8 年 到2 0 0 4 年第一季度的情况，从图中可以看出，复杂网络的研究方兴未艾。 图1 3s c i 收录的关于复杂网络的研究文统计图 f i g 1 3t h es t a t i s t i c so f t h ed i s s e r t a t i o ni ns t u d y i n g c o m p l e xn e t w o r ko ns c i 4 。 下面是图1 4a r ) ( i v 上关于网络的研究论文数量，统计了从1 9 9 7 年到2 0 0 3 年 c o n d m a t 上标题含有“n e t w o r k 的文章情况，从图中可以看出，网络的研究在近 6 年来越来越受到科学家的关注。 图1 4a r x i v ：c o n d m a t 上关于网络研究论文统计图 f i g 1 4 t h es t a t i s t i c f i g u r e o f t h e d i s s e r t a t i o no f s t u d y i n g n e t w o r ko n a r x i v 关于小世界网络的研究，n e w m a n 1 和h a y e s 2 3 1 给出了不算太长的三篇综 述，更短的一篇由s t r o g a t z 完成f 4 】，发表在n a t u r e 上；a l b e r t 和b a r a b 矗s i 给出了 一篇更像是教科书的综述【5 】，他们讨论的熏点是演化的无标度网络，这篇文献在两 年之内已经被引用了近千次；最为详尽的综述是d o r o g o v t s e v 和m e n d e s 给出的 6 ， 在这篇文章中，他们用超过1 0 0 页的篇幅穷举了在此之前几乎所有关于演化网络 的结论，和相当详细的实验与分析的过程；2 0 0 3 年n e w m a n 的综述堪称精品n 7 l ， 漂亮的组织结构，地道风趣的语言和独到的视角，是你在阅读时会忘掉是在读一 篇学术文献，后面所附的四百多篇参考文献，足以填饱任何人的肚子；w a n g 和 c h e l a 在电子信息类的期刊上的一篇短综述【8 】，非常适合作为入门读物，一个完全 不谙此道的人都可以通过一个下午的阅读对复杂网络研究的概貌有所了解；w a n g 的另一篇综述像是上一篇文章的扩展版 9 】，在这篇文献中，w a n g 强调了复杂网络 上的混沌同步和混沌控制，对这方面工作感兴趣的读者切不可放过该文献。最新 的综述是e v a n s 在2 0 0 4 年5 月完成的 1 0 】，这篇文献中包含了很多最新研究的结 果。 5 一 哪a啊也o l o 霜b j z 东北大学硕士学位论文 1 . 2 本文研究的意义与内容 第一章 绪论 i n t e rne t 作为人类社会信息化的标志， 其规模正以指数速度增长， 如今i n t e rn e t 的 面貌已 经与 其原型啊a r p a n e t 大相径庭， 其高 度的 复 杂性， 使得没有 人能 说出 这 个庞然大物看上去到底是个什么样子，运作如何。因此探求这个复杂网路中蕴含 着的规律，发现特性肯定是对i n t e rne t 研究的重要方式。然而 i n t e rn e t 与生俱来的 异构性、动态性、发展的非集中性以及如今庞大的规模都给建模带来了巨大挑战 1 1 . i n t e rn e t 的 建模至今仍然是一个开 放性的问 题， 在计 算机网 络 研究中占 有重 要地位。 如果能够通过对复杂网络的研究能揭示出i n t e rne t 网络中蕴含的规律的话， 将非常有助于人类认识它并利用它。 目 前，还没有一种最优的算法来进行复杂网络的建模，对复杂网络的研究仍 然出在起步阶段。因此，设计一个复杂网络构造器，并以此为基础进行复杂网络 的拓扑结构及传播行为的研究将是一项非常有意义的尝试。 本文首先介绍了复杂网络的背景和发展过程，以及目 前研究的现状。发现目 前科学家包括数学家、物理学家等在研究复杂网络的时，都把重点放在了对复杂 网络理论的研究上，并没有很好的利用计算机这个有力的工具。而对于计算机科 学的研究工作者来说，研究复杂网络有更大的优势就是强大计算机能力。因此， 这里对复杂网络的研究， 选择利用计算机的强大计算及仿真能力， 设计实现了“ 复 杂网络构造器” ， 然后在此基础设计了一种简单的传播算法， 进行了传播的统计与 分析。 下面简单介绍一下各个章节所述内 容。 第二章是复杂网络的介定。先介绍了图论的基本概念，然后分析了复杂网络 研究中的一些量纲和己 经存在的经典的网络模型 ( 包括规则网络、随机网络)的 定义及其构造的方式。重点放在对复杂网络 ( 包括小世界网络、无标度网络及真 实的i n t e rn e t 网 络) 的建模机制的定义， 从理论上说明复杂网络的研究应该考虑的 特性及各种网络模型的拓扑特征。 第三章开始就是本文完成的一些工作，这一章首先介绍了本构造器构造各种 网络模型的算法，并构造出了相应的网络模型。然后介绍了“ 复杂网络构造器” 的设计与实现。虽然对设计与实现介绍的比较简要，但是它却是本文的主要工作 所在。而且是实现所有研究分析的基础。 第四章，介绍了在复杂网络模型的上传播行为的设计与分析。这一章也是在 复杂网络构造器设计和实现之后的进一步尝试。通过简单传播模型的设计及在网 络模型上的试验，按照回归分析及线性拟合的方法，估算出了各种网络模型的传 播的曲 线方程，并对他们的网络拓扑结构与传播特征进行了分析比较，发现了在 一6- 东北大学硕士学位论文 特定条件下的网络拓扑结构对传播行为一些影响。 最后，对全文的工作进行了总结与展望，对 提出了一些看法。 第一章 绪论 “ 复杂网络构造器”发展与改进 东北大学硕士学位论文第 二章 复杂网 络的 介定 第二章 复杂网络的介定 2 . 1 图的基本概念 对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，图论本 身也是目前组合数学领域最活跃的分支之一。我们在复杂网络的研究中将要遇到 的各种类型的网络，无向的、有向的、加权的都可以用图 论的语言和符号精 确简洁地加以描述。图论是研究网络共性的有力工具。以下简单的介绍一下图论 的几个基本概念。 图g 是 指两 个 集 合( v , 习， 其中 集合e 是 集 合v x v 的 一 个 子集. 集 合v 称 为 图的 顶点集，往往用来代表实际系统中的 个体， 集合e被称为图的 边集，多用于 表示 系统中 个体 之间 的 关系 或 相互 作 用。 若 x , y e e ， 就称图g中 有一 条从x 到 y 的弧 ( 有向 边) ， 记为x - . y ， 其中 顶点x 叫 做弧的 起点， 顶点y 叫 做弧的 终点。 根据定义， 从任意顶点x 到y 至多只有一条弧， 这是因为如果两个顶点有多种需要 区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这 种复杂的关系而给解析研究带来困难。如果再假设图g中不含自己到自己的弧， 我们就称图 g为简单图，或者更精确地叫做有向简单图。记 g 中顶点数为 v ( g ) = 1 川 ，边数为e ( g ) = 1 e i ，分别叫做图 g 的阶和规模，显然有 -, ( g ) 6 , 2 - x 7 ,3 -6 ,4 y7 , 4 -8 ,6 9 , 7 9 , 8 - * 1 0 ) ; 图2 . 1 b 是6 阶 无向 图 ， 顶点 集为 1 ,2 ,3 ,4 ,5 ,6 1 ， 边 集为1 1 3 , 1 4 , 1 5 ,2 3 , 2 4 ,2 6 ,3 6 , 5 6 ) . 东北大学硕士学位论文第 二章 复杂网 络的 介定 第二章 复杂网络的介定 2 . 1 图的基本概念 对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，图论本 身也是目前组合数学领域最活跃的分支之一。我们在复杂网络的研究中将要遇到 的各种类型的网络，无向的、有向的、加权的都可以用图 论的语言和符号精 确简洁地加以描述。图论是研究网络共性的有力工具。以下简单的介绍一下图论 的几个基本概念。 图g 是 指两 个 集 合( v , 习， 其中 集合e 是 集 合v x v 的 一 个 子集. 集 合v 称 为 图的 顶点集，往往用来代表实际系统中的 个体， 集合e被称为图的 边集，多用于 表示 系统中 个体 之间 的 关系 或 相互 作 用。 若 x , y e e ， 就称图g中 有一 条从x 到 y 的弧 ( 有向 边) ， 记为x - . y ， 其中 顶点x 叫 做弧的 起点， 顶点y 叫 做弧的 终点。 根据定义， 从任意顶点x 到y 至多只有一条弧， 这是因为如果两个顶点有多种需要 区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这 种复杂的关系而给解析研究带来困难。如果再假设图g中不含自己到自己的弧， 我们就称图 g为简单图，或者更精确地叫做有向简单图。记 g 中顶点数为 v ( g ) = 1 川 ，边数为e ( g ) = 1 e i ，分别叫做图 g 的阶和规模，显然有 -, ( g ) 6 , 2 - x 7 ,3 -6 ,4 y7 , 4 -8 ,6 9 , 7 9 , 8 - * 1 0 ) ; 图2 . 1 b 是6 阶 无向 图 ， 顶点 集为 1 ,2 ,3 ,4 ,5 ,6 1 ， 边 集为1 1 3 , 1 4 , 1 5 ,2 3 , 2 4 ,2 6 ,3 6 , 5 6 ) . 东北大学硕士学位论文第二幸 复杂网络的介定 图2 . 1 网 络拓扑结构示意图 f i g .2 . l t h e f i g u r e o f t h e n e t w o r k t o p o l o g y s t r u c t u r e 对于两个图g ( v , e ) 和g ( v , e ) ，如果v c v , e 二e，就称g 是g的子图。 若v = v ， 则称g 是g的生成子图: 若在g中 所有连接集合v 中两顶点的边都出 现 在 集合e 中 ， 则 称g 是g的 导出 子图 ， 记 为g 二 g v 。 如 果图h与图g 有相 同的顶点集，并且图h中两点之间 有边相连 ( 相邻)当且仅当在g中 这两点是不 相 邻 的 ， 就 称 图 h 是 图 g 的 余 图 ， 记 做 h= 云 。 拥 有心条 边 的 n 阶 无 向 图 或 拥 有对 条 边 的 。 阶 有 向 图 叫 做 完 全 图 ， 用 符 号 k表 示 ， 其 余 图 k . 叫 做 空 图 。 在 无向 图g中 ， 与 某 顶点x 关 联的 所 有边的 数目 叫 做x 的 度， 用 符号吨( x ) 表示， 在不致混淆的 时候， 可以 简单地记为d ( x ) 。 对于有向 图，由 于需要区分从顶点出 去的弧和进入顶点的弧， 所以 不能简单地用度表示。 我们把以 顶点x 为起点的弧的 数目 叫 做x 的出 度， 把以 顶点x 为 终点的 弧的 数目 叫 做x 的 入度， 分别记为d ( x ) 和 d - ( x ) 。 顶点 度与图的规模之间有一个显然的关系: 【 定 义2 . 1 】 对 于 无向 图g ( v , e ) 有: 艺 d ( x ) = 2 6 ( g ) ( 2 . 1 ) 对于有向图g ( v , e ) 有: 艺d ( x ) = yd - ( x ) = 二 ( g )( 2 .2 ) x . 犷 x e 犷， 在图g中 ，以 x 为 起点 ，y 为 终点的x - y 路p 是指 一系列首 尾相 连的 边组 成 的 集 合 : e ( f ) = x o x x ,x l ， 一 ， x r_ ,x , a 其 中 x 0 二 x , x r 二 y , x , # x , , v o s i r 2 的两个圆周上均匀散布n 个点( v l ，v 2 ，k ) ， 3 从第一节点h 开始按照1 k 2 i 条边向前连接，每条边都是无向的，既 v l 寸v 2 与v 2 呻v l 是同一条边， 4 循环执行3 靳1 i + l k 2 1 h ；f ( 1 ，n ) 时，把f _ 0 ， 5 当i = 聆时结束。 b 1 规则网络模型的表现 下面是图3 1 规则网络的结构，由于规则网络特性，小规模的节点和连边数与 大规模的节点与连边数所反映出的网络特性都相同。这里我构造的是一个节点数为 1 0 0 ，连边数为2 0 0 ，节点度为4 的规则网络。 图3 1 规则网络结构图 f i g 3 - 1t h es t r u c t u r ef i g u r eo f t h er e g u l a rn e t w o r k 2 )随机网络的建模 随机网络的网络机制前面已经给出了三种定义，按照任何一种都可以构造出 网络模型。这里我结合三种定义，得出了一种新的生成算法。 a ) 随机网络建模算法的自然语言描述 1 输入n ，r ，i = 0 ， 一18 东北大学硕士学位论文第三章复杂网络建模 2 在以，为半径的圆形范围中随机散布，2 个点v l ，v ：，“) ， 3 从节点v ，o cr a n d o l 工阳。如m( 3 1 ) 式中： 出。鲁 ( 3 2 ) 托 、 。 r 1 n 竹 l r a n d o m i i ( 3 - 3 ) c 。出。是指与小世界网络具有相同节点数和相同平均数的随机网络的聚类 系数；三。眺。是指与小世界网络具有相同节点数和相同平均度数的随机网络的特 征路径长度；即是网络节点数；彪是每个节点的平均度数。 c ，。和。是通过引入m o o r e 图来逼近相应的随机网络分析得到的，其 计算细节参见文献 2 2 ，2 3 。式( 3 2 ) 表明，小世界网络具有与随机网络大致相近 的特征路径长度，但具有丈得多聚类系数。 小世界网络是介于规则网络与随机网络之间的一种复杂网络，构造的方法 般是在规则网络的基础上增加断边重连来构造的。下面所构n n 4 , 世界网络是在 一维链形式的规则网络基础上，按照一定重连概率形成的小世界网络模型。 a ) 小世界网络建模算法的自然语言描述 1 规则网络的建模l 5 ， 一2 0 查些垄兰堡主茎竺垒查! 坚兰墨童旦竺! 墨堡 2 按照随机概率p 选择一定数量的点h ，f ( 1 ，功， 3 从v ，f _ 1 开始每一节点按照随机的和节点集中的任一节点相连， 4 当j = 仃时结束。 本算法的特点就在于随机选择了相应节点之后，没有进行断点，而是直接进行 了重连。因为在网络规模巨大的情况下，是否断开对网络特性没有任何影响。因 此，忽略它，使得算法简单易懂，而且对构造效果没有影响。 b 1 小世界网络模型的表现 下面是图3 3 小世界网络的结构，在规则网络的基础上，增加一定的随机连 线。这样就形成了一个小世界网络的模型。 图3 3 小世界网络结构 f i g 3 3t h e s t r u c t u r ef i g u r eo f t h er e g u l a rn e t w o r k 2 ) 无标度网络建模 在小世界网络的研究兴起之后，越来越多的科学家投入到复杂网络的研究中 来。大家发现其实更多的其他几何量的特征也具有很大程度上的普适性和特定的 结构功能关系。s c a l ef r e e 网络就是其中的一个重要方面。s c a l ef r e e 网络指的是 网络的度分布符合幂律分布，由于其缺乏一个描述问题的特征尺度而被称为无标 度网络。我们都知道幂律在自组织临界性( s o t ) 中的特殊地位 2 4 。实证研究发现， 大量的实际网络可以被认为是s c a l ef r e e 网络 2 4 。如下表。 下面是表3 1 实际网络的s c a l ef r e e 现象，列表中包括所研究网络的实际对象 ( n e t w o r k ) ，大小( s i z e ) ，平均度值( ) ，o u t 度幂率分布指数( 7 0 “) ，i n 度 - 2 】 查些垄堂堡主茎堡堡查 整三主墨墨塑竺壅堡 幂率分布指数( y 加) ，平均最短距离( z ) ，按随机网络计算的最短距离( ，r 锄d ) a 可 见，s c a l ef r e e 网络一般具有s m a l lw o r l d 特征。此表在文献 2 4 的基础上收集确认 其他文献编辑而成，感谢作者r a l b e r t 提供。 表3 1 实际网络的s c a l ef r e e 现象 t a b l e3 1t h es c a l e f r e ep h e n o m e n ao f t h er e a ln e t w o r k n e t w o r ks i z e仉。 k 以 w w w 2 5 】 3 2 5 7 2 945 i2 4 5211 1 28 3 2 w w w 2 6 】4 3 ，1 0 7 723 82 1 w w w 2 7 2 3 ，1 0 87 52 7 22 11 68 8 5 w w w 2 8 ，s i t e 2 6 0 0 0 01 9 4 i n t e m e t 2 9 ，d o m a i l l 3 0 1 5 4 3 8 93 。4 ”7 62 1 - 2 2】- 2 24 6 3 i n t e m e t 2 9 ，r o u t e r 3 8 8 82 5 72 4 8 2 4 81 2 1 507 5 i n t e m e t 3 0 ，r o u t e r 1 5 0 , 0 0 026 6 2 4 2 41 11 28 m o v i ea c t o r s 3 1 】2 1 2 2 5 0 2 8 7 82 32 34 5 43 6 5 c o a u t h o r s 3 2 ， s p i r e s 5 6 , 6 2 71 7 3i 21 242 1 2 c o a u t h o r s 3 3 ，n e u r o 2 09 2 9 31 1 5 42 1 2 160 0 l c o a u t h o r s 3 3 ，m a t h 7 0 , 9 7 53 92 52 59 58 2 s e x u a lc o n t a c t s 3 4 】 2 8 1 03 43 4 m e t a b o l i c 3 5 ，e c o l i 7 7 87 42 22 2 3 23 3 2 p r o t e i n 3 6 ，s c e r e v +1 , 8 7 0 2 3 92 42 4 c i t a t i o n 3 7 】 7 8 3 ，3 3 9 8 5 7 3 p h o n ec a l l 3 8 5 3 3 1 0 63 1 62 1 21 w o r d s 【3 9 】， c o o c c u r r e n c e * 4 6 0 9 0 2 7 0 1 32 7 2 7 现在我们来看看s c a l ef r e e 网络的形成机制。目前对于无向s c a l ef r e e 网络， 普遍认为偏好依附( p r e f e r e n t i a la t t a c h m e n t ) 【1 8 】是一个很好地形成s c a l ef r e e 网络 的机制。具体模型如下。取初始研。个顶点任意连接或完全连接。每一步在原网络 g o 一1 ) 的基础上加上一个新的顶点，同时加上从此顶点出发的m 条边，形成新的 i 网络g ( f ) 。其中新加边的另一个端点按照正比于顶点度数的分布 一 一 d 乃2 痔 ( 3 4 ) 随机选取。重复以上新加点的过程足够多步所形成的网络的各顶点的度满足 东北大学硕士学住论文第三章复杂旦竺垄坚 幂率分布p k ，见图3 3 。而且，指数y = 3 与模型的参数m o ，m 无关。进一 步的数值模拟表明，当，l 取某一范围内的随机数时，指数也不变。 鉴于实际网络的幂指数并不都是，= 3 ，有的作者发展了b a r a b a s i 和a l b e t t 的原 始偏好依附模型，使得幂指数可以用模型参数来调整。在偏好依附模型中，顶点v 的 度值瓦可以认为是其吸引力的度量。那么，随着时间的推移，除去少数精品之外，大 多数的顶点的吸引力会随着时间减弱。一个考虑了顶点的历史模型 3 5 】可以改变幂 指数y 。更多的可调参数模型甚至是破坏幂律分布的模型可以通过考虑更一般的 网络演化过程得到。 以上介绍了一种很好的形成无标度网络的算法。下面介绍在此偏好依附 ( p r e f e r e n t i a l a t t a c h m e n t ) 的基础进行改进后的构造无标度网络的一种算法。 a ) 无标度网络建模算法的自然语言描述 1 输入珂，r 2 在以，为半径的圆形范围中随机散布胛个点( v 。，v 2 ，k ) ， 3 按照层数t = l i g j 把边长为2 r 矩形区域分成三。层， 4 根据输入的关