（计算机应用技术专业论文）复杂网络核心子网的构造及特性分析.pdf

大连理工大学硕士学位论文 摘要 近年来，研究者们从复杂网络的角度对大量现实系统进行了特性分析，结果表明， 许多现实网络都具有相似的统计特性，例如特征路径长度较小的小世界现象、幂律分布 的无尺度特性以及聚集系数较大的小集团现象等等。网络拓扑统计特性及网络行为的研 究是现阶段复杂网络研究的热点问题之一，目前已有许多研究者通过模拟真实网络行为 来重现真实网络统计特性。这些研究包括重现真实网络统计特性的建模工作，网络拓扑 上的一些动态性问题，以及网络拓扑的变化对统计特性及网络行为的影响等等。 无论是自然界还是现实社会中的网络系统，都呈现出节点度分布的无尺度特性，这 反映了复杂网络中节点度值大小的差异性，这表明，网络中总是有一个或多个节点在整 个网络拓扑中占有重要的地位，这样的节点对整个网络拓扑连通性以及网络信息流的传 输具有重要作用。如果这些节点发生阻塞或受到威胁攻击，将对整个网络产生重要影响， 网络的健壮性、稳定性、运行效率将会发生重大变化，甚至导致整个网络的局部和全局 瘫痪。 为了确定这些节点或节点集的重要程度，本文利用图论中支配集的相关理论构造了 复杂网络拓扑核心子网，这种核心子网建立了复杂网络节点的微观特性与网络整体宏观 特征的联系，并且揭示了核心子网与原始网络的拓扑相似性。 本文利用度分布来度量核心子网的统计性质，发现并揭示核心子网结构与原网络具 有相似的无尺度特性；最后，分析了规则网络、随机网络、小世界网络和无尺度网络的 核心予网节点受到蓄意攻击、随机攻击和随机故障时，原始网络最大连通分支大小的变 化，揭示并发现了核心子网的行为对原始网络的连通性产生的影响和变化规律，研究结 果表明核心子网对整个网络性能的支配作用。 关键词：复杂网络；无尺度特性；网络拓扑；核心子网；支配集 大连理工大学硕士学位论文 t h ec o n s t r u c t i o na n dc h a r a c t e r i s t i ca n a l y s e so fk e m e ls u b n e ti n c o m p l e x n e t w o r k s a b s t r a c t r e c e n ty e a r s ，m a n yw o r k sh a v et r i e dt o s t u d yg e o m e t r i c a ls t a t i s t i e so fr e a l w o r l d n e t w o r k sf r o mc o m p l e xn e t w o r k sv i e w s t h er e s u l t ss h o wt h a tm a n yr e a ln e t w o r k sh a v e s i m i l a rc h a r a c t e r i s t i c s ，s u c ha ss m a l lw o r d ，p o w e r - l a wd i s t r i b u t i o n sa n dt h eh i g hc l u s t e r i n g a n ds oo n t o p o l o g yo f n e t w o r k si sah o t t o p i ci nr e s e a r c ho f c o m p l e xn e t w o r k s t h es t u d i e sa l o n gt h i sl i n eh a v eb e e na b l et om o d e l i n v e s t i g a t ec e r t a i nd y n a m i c a l p r o b l e m s o nn e t w o r kt o p o l o g i e sa n d s t u d yh o wt h eg e o m e t r i c c h a r a c t e r i s t i c sa n d p e r f o r m a n c e so f t h en e t w o r k sa r ea f f e c t e db yt h er e s t r i c t i o n si m p o s e do nn e t w o r k s s c a l e f r e ep r o p e r t yh a sb e e nf o u n db o t hi nn a t u r es y s t e m sa n dr e a l - w o r l ds y s t e m s i th a s s h o w nt h ed i f f e r e n c eb e t w e e nd e g r e e so fn e t w o r kn o d e s i nac e r t a i nn e t w o r k , t h e r ea r e a l w a y ss o m en o d e sw h i c ht a k ea ni m p o r t a n tr o l ei nt h ew h o l en e t w o r kt o p o l o g i e s t h e s e n o d e st a k ei m p o r t a n te f f e c t so nt h et r a f f i co f n e t w o r kf l o w s i f t h e s en o d e sh a p p e nt ob l o c ko r h a v eb e e na t t a c k e d ，i tw i l li n f l u e n c et h eh a l e n e s s ，s t a b i l i t ya n de f f i c i e n c yo ft h en e t w o r k sa s m u c ha st h ep a r a l y s i so f t h ew h o l eo rp a r to f n e t w o r k i no r d e rt od e t e r m i n et h ei m p o r t a n c eo fn o d e s ，t h i sp a p e rc o n s t r u c t sk e r n e ls u b n e tu s i n g t h ec o n c e p to fd o m i n a t i n gs e t si ng r a p h i c st h e o r y t 1 1 i sk e r n e ls u b n e ts e t su pt h er e l a t i o no f m i c r o c o s m i cc h a r a c t e r i s t i c sa n dt h ew h o l em a g n i f i c e n tp r o p e r t i e so fn e t w o r k s ，a n d d e m o n s t r a t e st h et o p o l o g i c a lc o m p a r a b i l i t yb e t w e e nt h ek e r n e ls u b n e t sa n dt h eo r i g i n a l n e t w o r k s i nt h i sp a p e r , w em e a s u r e dt h es t a t i s t i cp r o p e r t yo fk e r n e ls u b n e t su s i n gt h ed i s t r i b u t i o n s o fn o d ed e g r e e s ，a n dd i s c o v e r e dt h a tt h ek e r n e ls u b n e t sh a v et h es c a l e f r e ep r o p e r t ya st h e s a m ea st h eo r i g i n a ln e t w o r k s f i n a l l y ，t h i sp a p e ra n a l y s i st h ec h a n g e so fc o n n e c t i o nf r a c t i o n i no r i g i n a ln e t w o r k s ，w h e nk e r n e ls u b n c t st a k ee r r o r so ra t t a c k e d k e yw o r d s ：c o m p l e xn e t w o r k s ；s c a l e - f r e ec h a r a c t e r i s t i c s ；n e t w o r kt o p o l o g y ；k e r n e l s u b n e t ；d o m i n a t i n gs e t s 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：凌盘拯日期： 讼1 1 i 譬 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学傈留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名 艿墨抓 动年三月上巴日 崾 甄 、吖一 大连理工大学硕士学位论文 1 绪论 1 1 复杂网络研究背景及意义 人类所生活的这个世界充满了各种各样复杂的系统。无论是自然界的生态系统，还 是人造的各种物理系统，乃至人类社会的各种活动及社会关系都可以用形形色色的网络 来描述1 1 。”】。各个学科的研究者们从不同角度研究人类社会及自然界的不同网络，现阶 段主要研究领域包括生物网络、科技网络、社会关系网络等等，生物网络包括细胞网络 1 2 1 、蛋白质相互作用网络1 3 1 、新陈代谢网络 4 1 、食物链网络【5 1 等等；科技网络主要有w w w 网络【6 】、i n t e r n e t 网络【7 1 等等；社会关系网络主要有科学家合作网络f 8 】、人际关系网络1 9 1 等等。 现实生活中的网络无处不在，而且大部分真实网络无论是节点和连边的规模还是网 络的结构，都是非常复杂的。这些规模庞大、结构复杂，并且充满着大量动力学特性的 网络系统被科学家称为复杂网络。很多人尝试着对现实网络进行分类，但是设计一套严 格的分类标准是比较困难的。美国一些科学家提出了人们最关注的、值得深入研究的几 类典型复杂网络1 1 0 】。他们将网络分为三类，分别为生物网络、物理网络和社会网络，各 种网络从属的类型如表1 1 所示。无论是自然界还是人类社会，从其自身到相关的各类 活动都存在不同类型的网络，网络科学的研究将极大程度的促进人们对知识的理解以及 对信息的有效利用。 表1 1 三类典型的现实网络 t a b 1 1t h r e et y p e so f r e a ln e t w o r k s 复杂网络核心子网的构造及特性分析 尽管网络的存在对生命的繁衍、文明的发展具有重要意义，但是网络的危害也是显 然易见的，它对自然界和人类社会的作用是双面性的。常见的网络危害性就是病毒的传 播、谣言的扩散，以及各种网络局部性能的破坏导致的整个网络的瘫痪等等。这方面的 例子屡见不鲜，例如，i n t e r n e t 网络的病毒传播、s a r s 病毒的大范围感染、“雪崩效应” 所引起的美加大停电事故等等。 1 ) h r r p 网络拓扑2 ) 9 1 1 恐怖组织网络 3 ) 蛋白质相互作用网络4 ) 美国航空网络 图1 1 复杂网络拓扑图 f i g 1 1t o p o l o g yo f c o m p l e xn e t w o r k s 随着高性能计算能力的提高，研究者们利用计算机工具发现了复杂网络有趣的规律 性特征，以此探究复杂网络深层次上的共性规律。对复杂网络的深入认知，可以帮助研 究者们更好的利用网络、控制网络来造福于世界。 目前，人类对复杂网络的认知还处于萌芽阶段，尚没有一个清晰的理论体系和有效 的研究工具。从系统科学角度来看，复杂网络是一个典型的复杂系统，其特征可以归纳 如下【1 1 j ： 大连理工大学硕士学位论文 ( 1 ) 网络行为的统计特性：复杂网络具有成百上万的节点，甚至更多，因此，使得 大规模性的网络行为具有统计特性； ( 2 ) 网络连接的稀疏性：具有个节点的全局耦合结构网络拓扑连接数目为o ( n 2 1 ， ， 而通常实际大型网络的连接数目只有o ( n 、； ( 3 ) 拓扑结构的复杂性：现实网络的拓扑结构并不是完全规则的，也不是完全随机 的，但却存在内在的规律性； ( 4 ) 网络节点动力学行为和网络时空演化的复杂性。 1 2 复杂网络研究现状 人类对网络的研究可以追溯到1 7 3 5 年，数学家欧拉解答了著名的哥尼斯堡七桥问 题，开g , j y 图论的研究历史。当时人们对网络的研究主要工作是面向经典的规则图的研 究。直到1 9 5 9 年，匈牙利的两位数学家e r d o s 和r e n y i 为了描述通信和生命科学中的网 络，提出了新的构造网络的方法，根据一个概率值来确定网络中节点之间是否连边。使 用这样的方法构造的网络模型称为随机网络模型。在以后的近半个世纪时间里，随机网 络模型一直作为研究者们认识真实网络的重要工具。 直到最近几年，计算机数据处理能力和高性能技术的飞速发展为科学家们分析真实 网络数据提供了强大的研究工具。通过对大量真实网络拓扑数据的统计和分析，研究者 们惊奇的发现，真实网络所表现出的某些特性并没有体现在现有的网络模型中，真实网 络既不是规则网络，也不是随机网络。这些拓扑数据究竟暗藏着怎样的机理? 上个世纪9 0 年代末，两篇著名的文章带领人们重新认识了我们所熟悉的网络。在 w a t t s 和s t r o g t a z l 9 9 8 年发表于( n a t u r e 上的文章中，作者分析了真实网络的两个普 遍特性高集聚性和短路径特征。他们发现通过传统的规则网络和随机网络机制来建 模无法重现真实网络的这两个特性。w a t t s 和s t r o g t a z 在文章中提出了一种新的模型， 这种模型介于规则网络和随机网络之间，能够再现真实网络的高集聚特性和短路径特 征，作者称之为小世界模型( s m a l lw o r l d ) 。图1 2 是小世界网络结构示意图，它同时具有 高集聚性和短路径特征。随后，1 9 9 9 年b a r a b a s i 和a l b e r t 在s c i e n c e 上发表的论文【1 2 1 阐述了大量真实网络共同的统计特性节点度分布的幂律分布特性，这种特性被作者 称为无尺度特性。作者又提出了偏好依附机制构造了无尺度模型来重现真实网络的这一 特性。 小世界模型和无尺度模型的提出掀开了网络研究的新篇章，研究者们将这些规模庞 大结构复杂的网络称为复杂网络。近几年来，大规模复杂网络的研究一片兴旺，涌现出 大量研究成果，影响范围迅速扩大，参与人数迅猛增长。大量复杂网络相关文章发表在 复杂网络核心子网的构造及特性分析 n a t u r e 、s c i e n c e 、p n a s 、p r l 等国际一流刊物上，相关理论迅速增长，图1 3 显示了 2 0 0 4 年复杂网络相关研究所占复杂性科学研究的比重【1 3 】。 好转辩 1 ) 规则网络结构2 ) 小世界网络结构3 ) 随机网络结构 图1 2 小世界网络结构示意图 f i g 1 2s m a l lw o r l dn e t w o r k 遗憾的是，直到目前为止，学术界还没有给出复杂网络的严格定义。网络的复杂性 来自于网络的结构复杂性、连接复杂性、演化复杂性和时空复杂性等多个方面l l ”。网络 拓扑统计特性及网络行为的研究是现阶段复杂网络研究的热点问题之一，目前已有许多 研究者通过模拟真实网络行为来重现真实网络统计特性。这些研究包括重现真实网络统 计特性的分析及建模1 1 5 - 1 9 】工作，网络拓扑上的一些动态性问题，以及网络拓扑的变化对 统计特性及网络行为的影响1 2 0 之3 等等。 1 ) 2 0 0 4 年p r l2 ) 2 0 0 4 年p r e3 ) 2 0 0 4 年p h y s i c aa4 ) 2 0 0 4 年p h y s i c ad 图1 3 复杂网络占复杂性科学研究领域的比重 f i g 1 3t h ed i s t r i b u t i o n so f c o m p l e x i t y s c i e n c e 人们对复杂系统的认识逐渐深入，不断发现其子系统之间存在密切的相互作用。因 此，人们在计算机的高性能技术的辅助下开始重视生物系统、科技网络、社会系统等复 杂巨系统及其子系统之间的相互作用关系和系统的整体性。复杂网络的研究者们通过对 不同领域的相对简单的网络拓扑进行观察，发现这些网络不同于前人所假想的网络系 统，它们具有不断增长的动态演化特性，在局部层面上杂乱无序，在整体层面上去呈现 - 4 - 大连理工大学硕士学位论文 出小世界、无尺度以及高集团化特性。这些特性引起了人们对复杂网络的强烈兴趣，研 究者们试图通过随机图、小世界模型、无尺度模型及网络演化机制建模，研究模型的统 计特性及生长规律，以此重现具有某种特性的真实网络。 对复杂网络的研究可以从微观特性和宏观特性两个角度来分析，微观特性指网络的 局部特征，例如顶点的度值、边的权值等，宏观特性包括网络的几何性质、效率与稳定 性等问题，属于网络的全局特征。研究网络中微观性质与宏观性质之间的关系是复杂网 络研究的核心内容。图论和社会网络分析在复杂网络中的研究，为复杂网络提供了静态 几何量及其分析方法，这是复杂网络的研究基础；而统计物理学可在复杂网络的模型研 究，演化机制与结构稳定性等方面提供丰富的研究经验。 当前，复杂网络研究进展主要依赖于对系统各部分之间简单的相互关系所形成的网 络拓扑结构的研究。网络拓扑结构是对复杂系统的一般抽象和描述方式，突出强调了系 统结构的拓扑特性。原则上，我们把复杂系统所包含的大量组成单元抽象成节点，单元 之间的相互作用抽象成边，这样，任何复杂系统都可以当作复杂网络来研究。 ： 现阶段，对复杂网络的研究内容可以归纳为以下几个方面： ( 1 ) 复杂网络拓扑结构的统计特性分析。这方面工作集中在复杂网络的认识层面。 通过获取的真实网络数据，深入研究其拓扑特征，全面刻画真实网络拓扑特性，例如对 网络度分布匹配模式的研究、网络集聚程度的研究、加权网络统计特性的研究等等。 7 7 ( 2 ) 复杂网络演化机制的研究和模型的建立。通过对真实网络的拓扑特性分析，归 纳出网络的统计规律，发现新的或完善现有的网络演化机制，构造更能反映真实网络统 计特性的网络模型，例如由偏好依附演化机制而构造的b a 网络模型、小世乔网络模型 等等。 ( 3 ) 复杂网络上的动力学研究。这部分研究工作包括网络上的传播、同步与共振等 各种动力学过程，以及网络对错误和攻击的鲁棒性问题。 1 3 本文工作 目前，复杂网络的研究仍处于起步阶段。现有的网络参数并不能全面描述真实网络 的所有特性，还没有一种网络模型能够生成完全符合真实网络各种统计特性的网络拓扑 结构。 本文针对复杂网络所表现出的无尺度特性，对无尺度网络的拓扑结构进行深入分 析，主要做了以下工作： 第一，基于复杂网络拓扑所表现出的无尺度特性构造了支配子网，并验证了该支配 子网能够起到拓扑核心予网的作用： 复杂网络核心子网的构造及特性分析 第二，对网络拓扑核心子网的统计特性进行了分析，发现该子网同样显示出度分布 的无尺度特性，具有与原网络的拓扑相似性； 第三，研究了支配子网拓扑改变对复杂网络行为的影响，主要针对支配子网节点随 机错误和蓄意攻击两种状态下，网络最大连通分支大小和网络效率的变化情况来检验支 配子网对整个网络性能的重要性。 1 4 本文组织结构 本文余下部分组织如下： 第二章，复杂网络概述。主要介绍复杂网络的统计特性及演化模型，并针对无尺度 特性进行详细分析。 第三章，网络核心予网发现。对真实网络数据的分析发现，网络中部分节点对网络 拓扑、流量、可靠性等方面起关键作用，对这些节点进行集中分析及保护对全局网络具 有重要价值。本章引入图论中支配集的理论来构造复杂网络的核心予网模型，该核心子 网反映了复杂网络的拓扑核心特性，对全局网络的拓扑优化、流量控制及容错与抗攻击 能力的提升具有广泛的研究意义。 第四章，核心子网对全局网络的支配作用。本章应用第三章提出的基于最大度的支 配子网构造算法，分别在真实网络和网络模型上进行实现，并验证了应用此算法构造的 支配子网符合拓扑核心子网的某些特性；然后，对复杂网络支配子网的特性进行了分析， 得到了与原网络相似的统计特性。 最后，通过模拟规则网络、随机网络、小世界网络和无尺度网络这四种网络模型对 核心子网发生随机故障或受到蓄意攻击的鲁棒性。 6 大连理工大学硕士学位论文 2 复杂网络概述 近几年来，复杂网络成为不同学科研究者们研究的热点。来自数学、物理学、生物 学、社会学、经济学、信息学等各个领域的科学家从不同角度对复杂网络的拓扑结构与 功能、建模机制、动力学特性及各种应用进行全方位的研究。本章从网络的基本表示开 始，对复杂网络拓扑特性及建模方法进行了综合分析。 2 1 网络的表示 网络可以抽象为一个由节点集y 和边集e 组成的图g = f y ，功，e 中的每条边都有 集合矿中的一对节点与之相对应。图g 的节点个数记为n 刊y i ，边数记为m = e i 。一 个图的画法并不是唯一的，表示节点的点和表示边的线的相对位置是无关紧要的。图2 1 表示了一个图g 的两种不同表示形式。图的多种表示形式适用于无地理位置信息的网 络，而对于大型电力网络等这样受地理位置限制的网络，图中的节点与边的相对位置应 该是固定的。如果一个图中既没有自环( 即不存在以同一个节点为起点和终点的边) ，也 没有两条边连接同一对节点的重边，则称该图为简单图。图2 1 所示的图中有自环，有 重边，则该图不是简单图；图2 2 所示的图中无自环且无重边，则为简单图闭。 图2 1 图疗的多种表示形式 f i g 2 1f o r m so f g r a p hg 按照边的性质，我们可以将图分为无向图、有向图及加权图。相应的，我们可以将 网络定义为无向网络、有向网络及加权网络。若集合y 存在一对节点( “，v ) 与( v ，t ) 对应 e 中的同一条边，则该网络称为无向网络( 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 ) 。如果e 中的每条边都赋予相应的权值，则称该网络为加权网络 ( w e i g h t e dn e t w o r k ) ，否则称为无权网络( u f n e i g h t e dn e t w o r k ) 。图2 2 给出了几种不同类 复杂网络核心子网的构造及特性分析 型的网络例子。本文中所涉及的网络，若无明确说明，均为无权无向网络，并且无重边 和自环的简单网络。 1 ) 无向网络2 ) 有向网络3 ) 加权网络 图2 2 不同类型的网络 f i g 2 2t y p e so f n e t w o r k s 一个网络图中，节点的度为与该节点直接相连的边的数量。对于有向图，节点的度 分为出度和入度，其中，出度为从该节点指出的边数，入度为指向该节点的边数。 大部分网络研究工作只关注于节点及边的关系，而不依赖于节点的具体位置和属 性，这样的研究属于网络拓扑结构的研究。 2 2 复杂网络统计特性 研究者们通过对大量真实网络数据的统计分析，发现不同系统抽象出来的复杂网络 具有很多的共同统计特性。目前，研究e e 较充分的统计特性有网络度分布、集聚系数、 特征路径长度、介数等，以下对这些概念进行简单介绍： ( 1 ) 节点度及度分布 节点度( d e g r e e ) 是节点的简单而又重要的属性，从网络整体的层面上来讲，节点度 是复杂网络的微观属性。节点度是指节点的连边数，用符号t 表示，若该网络的邻接矩 阵为a ，则第i 号节点的度为： t = y 口。 ( 2 1 ) 蜀7 有向网络节点度分为出度( o u t - d e g r e e ) 和入度( i a - d e g r e e ) 。节点的出度指以该节点为 起点指向其他节点的边的数目，节点的入度指从其他节点指向该节点的边的数日。直观 上来讲，一个节点的度越大，表示这个节点在网络拓扑中的地位越重要。 节点的平均度是指网络中所有节点度的平均值，用符号 表示 大连理工大学硕士学位论文 = 专屯 ( 2 2 ) n 鲁1 节点的度分布用分布函数p ( k 1 来描述，表示随机选择一个节点的度值恰好为k 的 概率。节点的度分布特征是复杂网络的重要几何特性之一。规则网络中各节点度值相同， 因此符合d e l t a 分布；随机网络的节点度分布近似为泊松分布，在节点平均度 处， p ( k 1 的概率值最大。 ( 2 ) 集聚系数 集聚系数( c l u s t e r i n gc o e f f i c i e n t ) 是网络的局部属性，反映了网络的集团化程度。一 个节点的集聚系数可以理解为该节点邻居间的紧密程度，表示为其定义如下： 对于网络中的任一节点i ，令岛表示节点i 的度，即表示节点i 有七j 个邻居，这岛 个邻居之间最多存在t ( 毛一1 ) 2 条边，令n l 表示节点i 的岛个邻居之间实际存在的边数， 则定义节点i 的集聚系数岛为： 铲志 q 3 ) 铲而知 心鄙 网络的平均集聚系数c 是所有节点i 的集聚系数a 的平均值： c 2 专善q ( 2 4 ) 从公式( 2 3 ) 和公式( 2 4 ) 我们可以看出，网络的集聚系数c 的取值范m y g o ，l 】。当且 仅当网络中所有节点均为孤立节点，没有任何连边的时候，网络集聚系数c = 0 ；当且 仅当网络是完全图的时候，网络集聚系数c = l 。 ( 3 ) 特征路径长度 网络中两个节点“和节点v 之间的距离( d i s t a n c e ) 定义为连接这两个节点的最短路径 上的边数，记为以，。对于节点数为的网络，若网络中一对节点i 和，之间不存在通路， 则记以= 。网络中任意两个节点的距离的最大值定义为网络的直径( d i a m e t e r ) ，记为d ： d = 四譬乃 ( 2 5 ) 在科技网络中，距离和直径是度量网络信息传输延迟的重要标准。但网络距离和直 径无法评价网络的总体特性，因此，研究者们提出网络特征路径长度的概念从宏观角度 度量网络的总体特性。节点数为的网络特征路径长度( c h a r a c t e r i s t i cp a t hl e n g t h ) 定义为 任意两个节点直径的距离的平均值，记为工： 复杂网络核心子网的构造及特性分析 如赢若吃 6 近期对复杂网络的研究发现，尽管现实网络规模巨大，节点众多，但网络的特征路 径长度却非常小。 ( 4 ) 介数 介数( b e t w e e n n e s s ) 是网络的全局变量，分为点介数和边介数。 节点“的介数定义为网络中经过节点甜的所有最短路径数目，反映了节点的影响力。 记节点对( i ，j ) 之间最短路径集合为s ( i ，) ，节点“的最短路径的集合为最( ，) ，则节 点的介数最表示为： e = 船 ( 2 7 ) 边e 的介数含义为网络中所有最短路径之中，经过p 的数量。记从顶点i 到顶点， 之间最短路径的集合为研圳，从顶点i 到顶点，之间经过边e 的最短路径的集合为佤驴， 那么边e 的介数定义为： 盈= 船 ( 2 8 ) 实证研究表明，大量实际网络的介数也拥有共同的统计特征，对于无尺度网络e 符 合幂律分布p ( 鼠) ：鼠叶。文献 2 2 3 中研究了不同度分布指数y ，( 2 丫 3 ) 的无尺度网络上 的吃，研究表明或分布独立于y 和平均度 ，r “2 2 ( 1 ) ，对于有向和无向网络均是 如此。因此，介数指数可以作为刻画无尺度网络特性的一个通用的量。 2 3 复杂网络模型 随着人们对复杂网络研究的不断深入，网络模型的发展经历了一个从简单到复杂的 过程，越来越多的新特征被发现，以前的网络模型不能符合实际观察到的复杂网络的特 性，越来越多的复杂网络模型正在被提出来。下面简要讨论几个关键的复杂网络模型： ( 1 ) 规则网络模型 规则网络是指平移对称晶格，任何一个格点的近邻数目都相同，例如一维链，二维 正方晶格等均为规则网络，如图2 3 所示。 大连理工大学硕士学位论文 研究者们将任意两个节点之间都直接相连的网络称为全局耦合网络( g l o b a l l y c o u p l e dn e t w o r k ) 。节点数为n 的全局耦合网络有( 一1 ) 2 条边，每个节点的度均为 一1 ，特征路径长度为l = 1 ，每个节点的集聚系数均为l 。然而大多数现实网络都是稀 疏网络，网络的边数一般至多是d ( ) ，因此，最近邻耦合网络( n e a r e s t - n e i g h b o rc o u p l e d n e t w o r k ) 得到了大量的深入研究，在这样的网络模型中，每个节点和它周围的邻居节点 相连，该网络模型属于规则网络模型的一种构造方式。具有周期边界的最近邻耦合网络 包含个围成一个环的节点，固定网络中每个节点的度值为k ，且为偶数，则每个节点 都与它左右各k 2 个邻居节点相连。该网络的集聚系数为： c ：辈望( 2 6 ) 4 ( k l j 当节点度k 很大时，网络集聚系数c “；，这样的网络是高度集聚网络。实证研究 斗 表明，规则网络的特征是平均集聚程度高而平均最短距离长。 硷好 1 ) 全耦合网络2 ) 最近耦台网络 3 ) 星形网络 图2 3 规则网络拓扑图 f i g 2 3t o p o l o g yo f r e g u l a rn e t w o r k s ( 2 ) 随机网络模型 随机网络是这样定义的：由个节点构成的图中，可以存在q 条边，其中随机连 接m 条边所构成的网络就叫做随机网络。或者给定一个概率p ，对于c ：中任何一个可 能的连接，以概率p 进行连接。如果我们选择m = p c l ，这两种随机网络模型就可以联 系起来，如图2 4 所示。 复杂网络核心子网的构造及特性分析 对于随机网络g ( ，p ) ，包含了从空图到完全图所有可能情况，因此随机图的几何 性质需要对每一种可能图做平均，例如计算每一种可能图的最短距离，然后按照各自出 现的几率做平均。研究结果表明随机网络节点的度值符合平均值为 的泊松分布，其 集聚程度约等于p ，最短距离d ：l n ( ) 。随机网络的特征是平均集聚程度低而平均最短 距离小。 o o o o o o o 1 ) 节点数相同的随机网络 2 ) 随机网络模拟图 图2 4 随机网络拓扑图 f i g 2 4t o p o l o 舒o f r a n d o mn e 似o r km o d e l ( 3 ) 小世界网络模型 从规则网络和随机网络的特征来看，平均集聚程度和平均最短距离似乎是一对相互 矛盾的几何量。而对真实网络数据的统计结果表明，许多真实网络同时具有高集聚程度 和小最短路径特征。对于传染病模型，平均集聚程度对应于传播的广度，平均最短距离 代表的是传播的深度。因此如果实际网络同时存在宽的广度和大的深度的话，在这样 大连理工大学硕士学位论文 的网络上的传染病传播显然将大大高于规则网络与随机网络。w a t t s 和s t r o g a t z 为我们 找到了这样的网络模型s m a l lw o r l d 网络。 黪露 1 ) w s 小世界模型：随机重连2 ) n 1 r 小世界模型：随机加边 图2 5 小世界模型拓扑图 f i g 2 5t o p o l o g yo f s m a l lw o r l dm o d e l p 图2 6 小世界网络模型 f i g 2 6s m a l lw o r l dm o d e l 我们可以这样定义：同时具有大的集聚系数和小的平均距离两个统计特征的复杂网 络，称为小世界网络。w a t t s 和s t r o g a t z 发现，只需要在规贝j i n 络上稍做随机改动就可 以同时具备以上两个性质。改动的方法是，对于规则网络的每一个节点的所有边，以概 率p 断开一个端点，并重新连接，连接的新的端点从网络中的其他节点里随机选择，如 果所选择的节点已经与该节点相连，则在随机选择别的节点来重连。当p = 0 时就是规 复杂网络核心子网的构造及特性分析 则网络，p = l 时则为随机网络，对于0 p 1 的情况，存在一个很大的p 的区域，同时 拥有较大的集聚程度和较小的最小距离。 图2 6 是w a t t s 和s 缸d g a t z 在n a t u r e ) 上发表的文章中所显示的小世界网络的几何 统计特性。图中横坐标表示每个节点断开规则网络中的连接重现建立连接的概率，纵坐 标为平均集聚系数c ( p ) 和平均最小距离z ( p ) 分别与相应的规则网络的集聚系数c ( o ) 和平均最小距离l ( 0 1 的比值。 ( 4 ) 无尺度网络模型 在小世界网络的研究兴起之后，越来越多的科学家投入到复杂网络的研究中去。大 家发现其实更多的其他几何量的特征也具有很大程度上的普适性和特定的结构功能关 系。无尺度( s e r ef r e e ) 网络就是其中的一个重要方面。 无尺度网络指的是网络的度分布符合幂律分布，由于其缺乏一个描述问题的特征尺 度而被称为无尺度网络。节点度服从幂律分布就是说具有某个特定度的节点数目与这个 特定的度之间的关系可以用一个幂函数近似的表示。幂函数曲线是一条下降相对缓慢的 曲线，这使得我们不仅能在网络中发现大量度很小的节点，还可以找到度很大的节点。 图2 8 无尺度网络拓扑图 f i g 2 8t o p o l o g yo f s c a l e f l e en e t w o r k s 2 4 现实网络特性研究 小世界现象和无尺度特征提出之后，随着近年来计算机存储能力与运算能力的迅速 提高，研究者们对不同领域的大量实际网络的拓扑特征进行了广泛的实证分析，表2 1 大连理工大学硕士学位论文 列出了部分研究结果。测量的参数有：网络的方向性、网络节点总数、平均度值 ， 特征路径长度厶集聚系数c 和幂律分布指数，等等。数据来源参考文献【1 7 】。 表2 1 真实网络的小世界现象和无尺度特性 t a b 2 1s m a l l w o r l da n ds c a l e - f r e ec h a r a c t e r i s t i c si nr e a ln e t w o r k s 复杂网络核心子网的构造及特性分析 3 复杂网络的核心子网发现技术 随着对复杂网络性质的物理意义和数学特征的深入研究，大量真实网络所呈现出的 度分布的无尺度特性反映了复杂网络中节点度值的差异性。度值大的节点对整个网络拓 扑连通性及网络信息流的传输具有重要作用，在整个网络拓扑中占有重要的地位。由此 可见，在规模庞大、结构复杂的网络中，部分度值大的节点对网络的连通性及信息的中 转起到支配性作用。本章根据图论中的相关理论，对网络拓扑结构进行处理，用构造网 络的拓扑子图，并通过分析证明这样一个子网结构即可代表复杂网络的拓扑核心子网。 图3 1 六种网络的度分布曲线 f i g 3 1d e g r e ed i s t r i b u t i o n s 大连理工大学硕士学位论文 3 1 复杂网络的无尺度特性 3 1 1 无尺度特性的发现 1 9 9 8 年，b a r a b a s i 和a l b e r t 等对万维网的产生机理进行研究，意外的发现万维网基 本上是由少数连通性非常高的页面串连起来，接近8 0 的页面的连接数不到4 个，而不 到万分之一的少数页面却拥有1 0 0 0 多个连接。这种现象无法用具有平均值特性的随机 网络来描述。而w a t t s 和s t r o g a t z 所构造的小世界模型也不能反映出节点度分布的这种 巨大差异性。于是，他们把具有这种性质的网络称作无尺度网络。在对万维网数据的统 计分析发现网页的连接分布遵循幂律特性。后来，研究者们对大量复杂系统进行实证研 究【l ”，发现很多网络都是由具有高连通度的少数节点所支配，包括新陈代谢网、演员合 作网等等。这些少数的具有高连通度的节点被称作集散节点。在无尺度网络中，有些集 散节点甚至具有数不清的连结，而且不存在代表性的节点。许多复杂系统抽象出来的网 络拓扑结构都是由少数集散节点支配的无尺度网络。 3 1 2b a 无尺度演化模型 b a r a b a s i 和a l b e r t 在分析了万维网、引文网络及演员合作网等复杂网络中存在的节 点度幂律分布的共同特性后，进一步阐述了产生无尺度特性的深层原因，分析了为什么 随机网络拓扑结构不能反映集散节点的支配特性。1 9 9 9 年，他们提出了一种具有重大影 响力的新的网络拓扑演化模型，以后，大多数新的复杂网络模型的提出都是对他们提出 的这种模型的改进及完善，这种模型成为b a 网络模型。b a 网络模型明确的提出复杂 网络的两个基本因素，网络节点的增长性( g r o w t h ) 和新增节点的偏好依附特性 ( p r e f e r e n t i a la t t a c h m e n t ) 。网络节点的增长性改变了随机网络模型中节点数量固定不变的 模式，反应了现实网络的动态性特征，并为复杂网络动力学特性的研究奠定了有力的基 础；偏好依附特性可以用来描述产生无尺度特性的内在因素，在大多数现实网络中，新 加入的节点倾向于连接对自身最有利的节点上，例如在i n t e m e t 网络中，新路由器的加 入倾向于连接到带宽大、处理能力高的路由器上。b a 模型的节点增长性和偏好依附理 论很好的解释了集散节点的产生。b a r a b a s i 和a l b e r t 基于这两个机制设计了b a 模型的 生成过程： ( 1 ) 初始化：网络初始节点数为，每隔一个时间步向网络中加入一个新节点，连 到m 个已存在的节点上； ( 2 ) 偏好依附：新加入网络的节点与网络中旧节点i 之间按照一定的概率n 建立连 接。这里概率n 。与节点f 的度砖，节点，的度k ，之间的关系满足： 复杂网络核心子网的构造及特性分析 兀f _ 轰 ( 3 1 ) 经过时间步r 后，网络中节点总数为n = m o + t ，边数为n t 。 图3 2 展示了根据b a 模型的演化机制而生成一个网络的过程。 图3 2b a 模型演化过程 f i g 3 2e v o l v i n gp r o c e s so f b am o d e l b a 模型提出来之后，引起了研究者的广泛关注。很多研究者分析了b a 模型的优 缺点之后，在b a 的基础上提出了更合理的扩展模型，其结果更加符合真实网络的统计 特征规律。 3 1 3b a 扩展模型 b a r a b a s i 和a l b e r t 发现了w w w 网络的增长性和偏好依附连接的特征，更多研究者 对其模型进行了改进和扩充。d o r o g o v t s e v 等人以及k r a p i v s k y 和r e d n e r 提出了新节点 在加入网络时选择度值为k 的节点进行连接的概率与k + k 0 成正比，其中是一个常量， 且一聊 l 。经过推导得到，口= 旦+ 3 ，因此得到口 2 时，网络中以某个概率出现一个与所有节点都有连边的超级节点。 文献【2 7 】和文献【2 8 提出了对参数历的改进。原始b a 模型新加入的节点的同时引 入m 条边与网络中以有节点相连，这里的m 是常量，这与现实网络不相符合。d o r o g o v t s e v 和m e n d e s 提出将常量m 修改为一个函数m ：搬，这里口是一个常数，栉是当前网络总 1 8 一 大连理工大学硕士学位论文 的节点数，每个新节点加入网络时与度值为k 的节点连接的概率为k + b n a ，其中b 是 个常量。以上规则，经过推导可得网络的度分布为最：旷，口= 2 + b ( 1 + a ) 0 一丑口) 。 原始b a 模型中，新边的加入只发生在新节点与网络已有节点之间，并且网络的边 一旦存在就不再改变，这也与现实网络的情况不相符。d o r o g o v t s e v 和m e n d e s 在b a 模 型的基础上提出了修改模型，提出老节点直接会以一定的概率添加新边或去掉已有的 边。这个改进的模型依然符合节点度的幂律分布特征。k r a p i v s k y 和r e d n e r 提出了一种 允许把节点和边分别加入的新模型。a l b e r t 和b a