复杂网络拓扑结构的网络模型研究综述.docx

复杂网络拓扑结构的网络模型研究综述*杨珉，张家玥，张达敏( 贵州大学 大数据与信息工程学院，贵州 贵阳 550025)摘 要: 基于复杂网络拓扑结构建模能够有效地分析其结构特征和传播机理。文中从网络拓扑结构方面总结了现有的网络拓扑基本模型，以及目前的研究状况，具体介绍局域世界演化网络、自相似性 网络、模块性网络、含权网络等典型模型的建立过程以及研究者们在其基础上的拓展研究。最后，在 讨论目前复杂网络拓扑基本模型存在问题的同时，也提出复杂网络拓扑结构上的网络模型发展的新 挑战。关键词: 复杂网络 演化 拓扑结构 动力学行为中图分类号: TP393文献标志码: A 文章编号: 1002 0802( 2014) 12 1354 06Overview on Network Models of Complex Networks Topology StructureYANG Min，ZHANG Jia yue，ZHANG Da min( College of Big Data and Information Engineering，Guizhou University，Guiyang Guizhou 550025，China)Abstract: Modeling based on complex network topology structure could effectively analyze its structural characteristics and propagation mechanism In terms of network topology structure，this paper summarizes the basic models of existing network topology and the research status Then it introduces in detail the setup procedure and research extension of several typical models，such as local world evolving network，the self similarity network，the module network，the weighted network Fianlly，the current issues of complex network topology basic model are discussed，and meanwhile，the new challenges in the development of net- work model on complex network topology structure are also pointed out in this paperKey words: complex network; evolution; topology; dynamic behavior家 Eular 开创图论学科开始的，之 后 在 相 当 长 的 一段时期没有得到发展，直到 20 世纪 50 年代末，两位著名的数学家 Erds 和 nyi 引出随机图理论，从此该发现在数学领域被公认为是开辟了复杂网络的系0引言复杂网络的相关研究进入中国已经有超过十年的时间了，其中的很多方向、分支都受到各个学科甚 至很多交叉学科的广泛关注 和 研 究，诸 如 Internet、 WWW、社会关系网络、经济网络、全球交通网络、大 型电力网络、科 学 家 合 作 网 络 等1，可 以 说 研 究 这 些网络的工具就是复杂网络。复杂网络的研究一般认为是从瑞士著名的数学2统性研究。1998 年小世界网络 和 1999 年无标度3网络这两 篇论文开创性地把现 实世界中的网络 数据抽象统计分析，研究更加符合实际网络特性的 网络结构对传播过程产生了重要影响，复杂网络的*收稿日期: 2014 09 12; 修回日期: 2014 10 21eceived date: 2014 09 12; evised date: 2014 10 21基金项目: 贵州省省委组织部项目( No TZJF 2011 37) ; 贵州省合作计划项目( 20127002 号) ; 贵州大学研究生创新基金项目( 研理工 2014005)Foundation Item: Guizhou Provincial Party Committee Organization Department of the Project ( TZJF 2011 37 ) ，Cooperation Projects ofGuizhou Province( 2012No 7002) ，Guizhou University Graduate Innovation Fund( esearch of Technology 2014005)1354杨珉，张家玥，张达敏: 复杂网络拓扑结构的网络模型研究综述第 47 卷第 12 期研究也发生了巨大的转变4 6。钱学森先生曾给出复杂网络的一个定义: 具有 自组织、自相似、吸引子、小世界、无标度中部分或全 部性质的网络称为复杂网络。当前对复杂网络的研 究主要集中在三方面: 各类实际网络的拓扑结构 实证研究，通过分析这些网络的拓扑性质，研究网络 演化的特征与规律; 网络生成机制及演化模型的 研究，确立网络演化模型，模仿真实网络行为; 复 杂网络上的动力学行为研究。研究之间并不是孤立 进行的，通常是复杂网络的结构决定了动力学过程， 而动力学过程反过来影响网络结构的演化。( Mm) 节点 进 行 连 接，而不是从整个网络中选择 节点15。新加入的节点根据择优连接概率: K i local ( ki ) = ( i LW )jkjlocalkiM( 1)m0 + t kjlocalj式中，m0 为初始网络的节点数，M 在局域世界中的 个数要满足 mMm0 + t，即 当 M / m 的 值 1 M /m0 + t范围内增加时，网络中节点度的分布显示mm出由指数分布向幂律分布的过渡过程。局域世界网络中的节点往往比无标度网路中节点数目少，即局 域世界网络中的度分布相较于随机网络、小世界网1复杂网络模型对于拓扑特性分析，研究者们根据建立的模型16。络、无标度网络中要更均匀很多研究者在基于 BA 无标度网络的局域世界网络演化模型的基础上又进行改进。Xuan 等 首 先通过节点之间度的相关性大小来判断局域世界范围的大小后，然后选取其中相关性最大的节点作为新 的节点，并且通过建立局域世界网络模型和数值仿利用图论、动力学特性以及相关交叉学科的方法进行计算分析和仿真。基于现实网络存在的缺陷，更 多符合实 际 需 求的网络扩展模型被相应提出。例 如，方锦清等提出随机性择优和确定性择优相结合模型7，史定华等提出优胜劣汰模型8和对数增长 模型9，Saramaki 等提出随机游走模 型10，Krapiv- sky 等提出非线性择优模 型11，Dorogovtsev 等 提 出 幂律增长模型12，郑蕾等提出的基于微博网络的信 息传播模型13。复杂网络的特征一般通过度分布、平均路径长 度、簇系数、中心性、模体、社团分类、有效性、鲁棒性等属性进行度量。其中，基本特征有节点的度分布、聚类系数和平均路径长度。本文重点阐述典型的更 加符合实际的网络拓扑结构模型，进一步探索真实 网络的传播机制和拓扑结构，分析和总结基本模型 及其性质，提出现有研究中存在的问题以及展望。17。Gu 等真模拟，得出 度分布呈幂率分布等规律 在局域世界中通过改变连接概率值和局域范围的大小构造出 LWD 网 络 模 型，同时还研究得出模型度 18分布、聚 类 系 数、平 均 路 径 长 度等参数的变化 。还有田立新等构造出一个基于二分网络的类局域世界网络模型，k ( t ) ki ( max ) ( t ) =k ( t ) +( 2)k ( t)i式中，k( t ) 为在 t 时刻节点 i 的饱和度，k( t) i ( max )节点平均度值，k ( t ) 指的是在指的是在 t 时刻 ki( max)it 时刻节点 i 的度值。该网络模型根据节点的度和 饱和度两项指标为标准决定 该节点是否添加新节 点，即是由旧节点本身的承载能力判断之后被动生成的，故称类局域世界模型19。局域世界演化网络模型李翔和陈关荣于 2003 年提出了局域世界演化 网络模型14在 BA 无标度模型基础上做出了改进。 局域世界网络模型不仅保持了无标度网络具有的鲁 棒性，而且还改进了无标度网络面对恶意攻击所存 在的脆弱性。局域世界网络模型中保留 BA 模型中 的增长机制，也就是在每一个单位时间步长 t 内，加 入一个新节点和 m 条边; 而前者的全局优先连接机 制被局部优先连接机制所替代，即新加入的节点从 局域世 界 ( LW ) 中按照择优连接概率选择 M 个1 11 2网络的自相似性2005 年 Song 等 在 分 析 各种实际网络后发现:很多实际网络系统，诸如社会网络、万维网、细胞网络和蛋白质交互网络等，在所有长度标度下具有自 相似性结 构20。所 谓 自 相 似 性 ( self similarity ) ， 即局部 在某种意义上与 整 体 相 似，即 就 是 是 分 形( fractal) 的基本特征。复杂网络的小世界特征表明Lln ( N) ( L 为网络平均路径长度，N 为网络规模) ，1355www txjszz com通信技术2014 年其等价表示 NeL / L0 ( 常数 L 为特征长度) ，由此可各节点之间表现关系相对紧密，而社团内部节点和外部节点之间关系相对疏远。网络的高聚类性表明 在局部可能包含由高度连接的节点组构成的子图， 模块度( modularity) 的概念被 Newman 等首次引入， 该函数是社团划分优劣程度的量化标 准23。模 块 度 Q 的定义:0发现网络规模是网络平均路径长度的指数函数，而自相似性则满足某种幂律关系21。分数维这一概念随着自相似性原则的提出也引 起了人们的注意。计算自相似分形维数的最常用方法之一就是盒记数法，采用该方法计算几何图形维数的思路: 通 过 盒 子 ( 边 长 为 lB ) 覆 盖 该 图 形，同 时 统计最 少 的 盒 子 数 NB ( lB ) 直到完全覆盖该图形。 这里的盒子一维是线段表示，二维是正方形表示，三 维是立方体表示，盒子的尺寸即为 lB 。计算图形维 数的近似公式:= 1 ( AQ( 5) PCi ，Cj) ()2mij ijij式中，A 是图的邻接矩阵，m 是图的边数目，Pij 代表在随机图中的点 i 与点 j 之间期望的边数目，函数 表示如果点 i 与点 j 在同一个社团中 ( Ci = Cj ) ，那么 函数值为 1，否则为 0。基于模块度的社团发现的算法一时间也随着模块度定义的提出涌现出来，社团发现与分割问题很 相似，尽管是 NP 难题，但研究者们也提出了许多行 之有效的 解 决 办 法。其中最具代表性的算法是由 Newman 提出的凝聚算法，基本思想是: 首先把所有 节点都看作是单独的社团，然后每次迭代的时候选 择两个 Q 值最大的社团合并，直到整个网络所有的 节点都被凝聚至一个社团之内。采用凝聚算法后能 够得到一个社团结构分解的树状图，最终社团结构 就是从所有的社团里再选 择一个局部最大的 Q 值 社团23。随后，Newman 和 Girvan 还提出了与凝聚 算法思路完全相反的分裂算法，基本思想是: 首先自 顶向下不断地从网络中删除边的信息中心 度 ( edge centrality) 最大的边，直到又退化为每个节点单独存 在的社团，然后在上一步的过程中找出对应 Q 值最 大时的结果。通常边的信息中心度的值取为边的最 短路径数24。还有 Duch 等提出的基于直接寻优算 法思路的 EO 算法，基本思想是: 首先引入一个新的 局部变量，即每个节点所对应的模块度 Q 值贡献大 小，通过初始的随机划分后，采用贪婪策略局部变量 得以调整从而全局目标函数 Q 值 也 得 以 提 高25。 另外，还有 Kernighan Lin 算 法、模 拟 退 火 算 法、极 值优化算法的启发式搜索算法等。很多情况下，划分网络的社团中，许多节点不仅 属于一个社团而且是多个社团，该情形下的社团叫 做重叠社团( Overlapping Community) 。典型的重叠 社区挖掘 算 法 有: Palla 等人提出的派系过滤算法 ( CPM，Clique Percolation Method) 、Lancichinetti 等人提出的基于局部扩展算法 ( LFM) 、Lee 等 人 提 出 的lnNB ( lB )( 3)dB ln ( l)等价地有 dBNB ( lB ) lB( 4)然而复杂网络中节点间的距离表示的并非欧氏距离，而是节点间最短路径包含的边的数目。并且 规定盒子尺寸 lB : 盒子中任意两个节点之间的距离 都小于 lB ，一组不重叠的盒子即可重新构成一个完 整的网络，即网络中所有的节点都有且仅有一个盒 子覆盖。而大规模复杂网络中拥有许多不尽相同的 分割方式，其中的分数维计算式( 3) 或式( 4) 中要求 NB ( lB ) 是覆盖网络的最少的盒子数，然而找到覆盖 网络所需要的最少的盒子集合的问题与经典的图作 色问题类似，相当于一个 NP 完全问题，也是复杂网 络运用盒记数法的主要难点。目前复杂网络分形大体上可分为两种研究方 法: 几何法和代数法。其中盒子覆盖法即为基本的 几何法，比如: 紧凑盒子燃烧算法、MEMB 算法、贪心 策略图着色算法等; 代数法主要是基于网络结构与 网络谱的特殊关系，研究不同网络结构导致的网络 谱特征。姚灿中等创新地将计算机算法中的 welch powell 法应用到目前盒子覆盖算法 中，有 效 地 解 决 了目前盒子覆盖方法中的瓶颈问题，提高了算法效 率改进了算法性能22。1 3模块性网络一般而言，模块 ( module) 是指一组物理上或功能上连接在一起的、共同完成一个相对独立功能的节点。模块存在于实际系统中，比如“物以类聚，人 以群分”，社团在实际系统中表现为节点之间关系 较为紧密、节点的特性相同或较为相近，即社团内部1356杨珉，张家玥，张达敏: 复杂网络拓扑结构的网络模型研究综述第 47 卷第 12 期贪婪团 扩 张 算 法 ( GCE，Greedy Clique Expansion ) 、刘大有等人在原始网络与相应的退火网络的结合成的集成网络上，提出重叠社区挖掘算法( UEOC，Un- fold and Extract Overlapping Communities) 。方法会逐渐取代基于固定结构的、静态的、线性的复杂网络研究。动态的演化过程尽管具体构造机理互 不相同，但 是 它 们基本上都遵循择优连接的机制。 然而，已经有学者证实真实网络在演化过程中并不 是完全遵守严格的择优机制，而是随机和择优两种1 4含权网络在实际复杂系统中绝大多数网络的权值并不是29。还有许多实际网络是由 机制共同作用的 结 果多个个体或子系统由于相互作用而融合为网络，这时就需要新的度量指标和特定的新型工具来描述和 模拟网络间的相互作用和影响。复杂网络的理论模 型以及网络的拓扑构造方法、网络特征参数度量还 需要更加深入研究。2) 含权网络的权重与 拓 扑 结 构。节 点 与 节 点 间的最短路径可由权重随机化直接影响，从而影响 到点、边介数，因此网络的全局拓扑结构特征仅仅利 用权重随机化就可以改变。方锦清等在对实际网络 ( 包括恒河猴网络、经济物理科学家合作网络等) 进 行了多次划分，发现加权网络、无权网络和反权网络之间社团结构具有显著差别，认为权重与边的匹配 方式对于社团结构划分具有重要的影响。然而现实 网络中( 比如交通流量) 在网络负载足够的情况下， 网络拓扑结构不一定会随着 网络权重的变化而变 化，因此关于含权网络权重与拓扑结构的研究还有很多实际问题值得探讨30。3) 复杂网络演化的复 杂 性。某些真实网络系 统中出现的一些复杂现象，有的还没得到很合理的解释，其成因也缺乏研究，比如复杂网络的自组织临 界性; 网络的拓扑结构变化对网络动力学行为的影 响也少有研究，因此带有反馈功能的自适应网络的 动力学行为值得深入探索。许多研究成果单从物理 学角度并没有考虑网络的实际功能和现实条件的限 制，特别是针对网络工程。许多关于应用方面的文 献叙述的都是在某个方面对 某个特殊领域的网络 化，并进行网络的结构分析与定性讨论，还需要一些 深入的应用研究如何根据具体的应用场景有针对性 地选择合适的方法。近年来众多的研究成果还停留 在从真实网络到理论模型的建立和分析上，想要把 科学研究的结果返回到网络工程去检验和实现，还 有相当长的一段路要走。4) 复杂网络的规模。由于大数据时代的到来， 复杂网络的规模也日益扩大，目前以单机资源为主 的复杂网络研究迎来了巨大的挑战。不管是复杂网0 或 1，节点权和连边权两个概念随着含权网络的提出也应运而生，节点权用于描绘节点的重要程度，而连边权用于描绘节点间的作用强度。边权所描绘的 节点间的耦合关系多种多样，诸如，交通网络中的道 路流量、Internet 网络中两个路由器或两个域之间的 带宽流量、社会网络中朋友的亲疏之分、科研合作网 络中科学家合作的次数等，真实网络特性包括拓扑 结构、动力学特征都能够从含权网络中反映出来。Yook 等提出的网络模型演化规 则 遵 循 BA 无 标度模型，另外在演化规则的基础上给每条新加入的边赋 权，称 为 考 虑 权 重的无标度网络演化模型 ( YJBT 模型) 26。Barrat 等提出边点权值动态演化 模型 ( BBV，Barrat Barthelemy Vespignani) ，该 模 型综合考虑点强度与边权值加强机制，BBV 模型的 动态演化利用权驱动方式得以实现，从而得出结论: 节点强度、边权值和度都实现了幂率分 布27，其 演化算法如下: 网络初始节点 m0 ，初始边随机连接，每 一个时间步长内带有 m 条 边 的 新 节 点 j ( 按 照 节 点 强度择优方 式 ) 连接到初始网络中，且 新 边 的 权 值为 w0 。新边 lij 的加入会造成边权( 按照边权值择优 方式) 重新分配，权值变化如下:wij wij + wij ，li( 6)wij式中，wij = ，式中 si 是节点强度，定义为:si= wij( 7)sijNi式中，Ni 是节点 i 的邻点集合。我们可以把含权网络演化模型看作是网络拓扑 结构与其承载的业务有着共生演化的耦合关系。不仅是 BBV 模型，还有 TDE 模型28把网络业务耦合进网络拓扑演化过程，得到网络的度、强度、权重的幂律分布以及非相称混合性和高聚集性等特征，描 绘出更加符合真实工程网络的特征。2当前复杂网络模型存在的问题及展望1) 复杂网络的建模。基于高度动态的、过程的1357www txjszz com通信技术2014 年络的数据存储还是大型运算，即使单机配置了更大容量的存储设备和更高处理能力的处理器，其结果 也收效甚微。一个有效的解决办法就是采用由多台 单机组成的集群进行分布式存储与处理; 另一种解 决办法是利用云计算技术，在云计算的环境下处理我们的任务既提升了研究的高度、提高了工作的效 率，也增加了技术的灵活性。在云计算的环境下，例 如 Map educe、Erlang 等编程框架也可以用于实现 任务算法。( 04) : 10315 10316SHI D H，CHEN Q H，LIU L M Markov chain basedNumerical Method for Degree Distribution of Growing Net-works J Physical eview E，2005，( 71 ) : 036140 036148Saramaki J，Kaski K Scale free Networks Generated byandom WalkersJ Physica A，2004，341( 11) : 80 86Krapivsky P L，edner S，Leyvraz F Connectivity ofGrowing andom NetworksJ Physics eview Letters，2000，85( 21) : 4629 4632Dorogovtsev S N，Mendes J F F Effect of the AcceleratingGrowth of Communication Networks on Their StructureJPhysical eview E，2001，63( 06) : 025101 025104周涛，韩筱璞，闫小勇，等 人类行为时空特性的统计力学J 电子科技大学学报，2013，42( 07) : 481 540 ZHOU Tao，HAN Xiao pu，YAN Xiao yong，et alStatistical Mechanics of the Temporal Characteristics of Human BehaviorJ University of Electronic Science and Technology，2013，42( 7) : 481 540陈关荣 复 杂 动 态 网 络环境下控制理论遇到的问题 与挑战J 自动化学报，2013，39( 04) : 312 321 CHEN Guan rong，Issues and Challenges of Control Theory based on a Complex Dynamic Network Environ- ment Acta Automatica Sinica，2013，39( 4) : 312 321 Nepusz T，Vicsek T Controlling Edge Dynamics in Complex NetworksJ Nature Physics，2012，8( 07) : 568 573 郑蕾，李生红 基于微博网络的信息传播模型J 通 信技术，2012，45( 02) : 39 41ZHENG Lei，LI Sheng hong A Novel Information Dif- fusion Model based on Microblog NetworkJ Commu- nications Technology，2012，45( 2) : 39 41LI X，CHEN G A Local world Evolving Network ModelJ Physics Letters A，2003，328( 02) : 287 296许丹，李翔，陈关荣 局域世界复杂网络中的病毒传播及免疫控制J 控制与决策，2006，21( 07) : 817 820Xu D，Li X，Chen G Local World Complex Networkof Transmission of the Virus and Immune ControlJControl and Decision，2006，21( 7) : 817 820汪小帆，李翔，陈关荣 复杂网络理论及其应用M北京: 清华大学出版社，2006: 4 5WANG Xiao fang，LI Xiang，CHEN Guan rongComplex Network Theory and its ApplicationM Bei-jing: Tsinghua University Press，2006: 4 5XUAN Q，LI Y，WU T J A Local World NetworkModel based on Inter node Correlation DegreeJPhysica A，2007( 378) : 561 572GU Y Y，SUN J T A Local World node Deleting Evol-ving Network ModelJ Physics Letters A，2008，372( 25) : 4564 456867893结语10基于复杂网络理论的拓扑演化能够从网络拓扑的角度揭示复杂网络结构特征对复杂网络本身的影 响。复杂网络是物理学、数学、计算机科学、生物学、 社会学等学科之间的桥梁。如，医学家希望了解传 染病是如何在人群中传播的并希望找到有效的预防 和控制策略; 社会学家关心谣言、舆论观点等信息是 如何在社会上传播的; 网络安全专家关心各种计算 机病毒是如何在 Internet 上传播的。研究复杂网络 模型可以有效地分析传播动力学行为及度量指标， 从而提出相应有效的防御和控制策略，进而达到降 低网络安全风险、提高网络运行效率、优化网络设计 结构等现 实 目 的。论文中错漏和不妥之处在所难 免，敬请专家批评指正。111213参考文献:141周涛，张子 柯，陈 关 荣，等 复杂网络研究的机遇与挑 战J 电子科技大学学报，2014，43( 01) : 1 5ZHOU Tao，ZHANG Zi Ke，CHEN Guan rong，et alThe Opportunities and Challenges of Complex NetworkesearchJ Journal of University of Electronic Scienceand Technology of China，2014，43( 1) : 1 5Watts D J，Strogatz S H Collective Dynamics of Small World NetworksJ Nature，1998，393( 6684) : 440 442Barabsi A L，Albert Emergence of Scaling in andomNetworksJ Science，1999( 286) : 509 512方锦清，汪小帆，郑志刚 非线性网络的动力学复杂性研究J 物理学进展，2009，29( 01) : 1 74FANG Jin qing，WANG Xiao fang，ZHENG Zhi gang Dynamical Complexity of Nonlinear NetworksJProgress in Physics，2009，29( 1) : 1 74SHI D H，LIU L，ZHU S X，et al Degree distribution ofevolving networks J Europhysics letter，2006，761521634171851358杨珉，张家玥，张达敏: 复杂网络拓扑结构的网络模型研究综述第 47 卷第 12 期2819田立新，贺 莹 环，黄 益 一种新型二分网络类局域世 界演化模型J 物理学报，2012，61( 22) : 228903TIAN Li xin，JIA Ying huan，HUANG Yi A NewClass of Local World Bipartite Network Evolution ModelJ Physics，2012，61( 22) : 228903SONG C，Jalvin S，Makse H A Self similarity of Com-plex NetworksJ Nature，2005( 433) : 392 395王江涛，杨建梅 复杂网络的分形研究方法研究J复杂系统与复杂性科学，2013，10( 04) : 1 7WANG Jiang tao，YANG Jian mei Fractal Study ofComplex Networks esearch MethodsJ Complex Sys-tems and Complexity Science，2013，10( 4) : 1 7姚 灿 中，杨 建 梅 复杂网络分形的盒维 数 改 进 算法J 计算机工程与应用，2010，46( 08) : 5 7YAO Can zhong，YANG Jian mei Box Fractal Di-mension of Complex Networks Improved AlgorithmJComputer Engineering and Applications，2010，46 ( 8 ) : 5 7Newman M E J Fast Algorithm for Detecting Community汪秉宏，王 文 旭，周 涛 交通流驱动的含 权 网 络J物理，2006，35( 04) : 304 310WANG Bing hong，WANG Wen xun，ZHOU Tao AWeighted Complex Network Model Driven by TrafficFlowJ Physics，2006，35( 4) : 304 310蒋国平，宋玉蓉，巩永旺 基于复杂网络结构特征的 病毒传播研究综述J 南京邮电大学学 报: 自 然 科学版，2012，32( 05) : 1 5JIANG Guo ping，SONG Yu rong，GONG Yong wang Summary