（运筹学与控制论专业论文）一类节点分裂网络演化模型的研究.pdf

大连理工大学硕士学位论文 摘要 当代科学在阐述有许多相同元素相互作用，只要是局部相互作用，构成的系统的物 理特性方面卓有成就。但是，当代科学不能描述有各种不同性质、非局部相互作用的元 素构成的系统，这就限制了从分子生物学到计算机科学的许多领域的进展。描述这些系 统的部分困难在于它们的拓扑结构：很多系统形成复杂网络，节点为系统的元素，边表 示元素间的相互作用。由于这些网络规模很大且相互关系缀复杂，他们的拓扑结构基本 上不为人所知且未曾探索。无尺度网络指节点度服从幂律分布的网络。b a 模型是第一 个无尺度网络演化模型，它捕捉到了无尺度网络形成的两个必不可少的机制增长和 择优连接是，说明了大规模复杂网络自组织成为无尺度状态的原因。b a 开创性论文的 发表，掀起了无尺度网络和b a 模型研究的高潮，在新世纪初的最近几年里，科学家们 就提出了许多产生无尺度网络的模型，并对b a 模型的主要性质进行了深入研究。 本文提出了具有自分裂机制的复杂网络演化问题，其演化规则为：每一新增点都是 某个已有节点的部分或全部复制，或者说是由这个点自分裂出来的。给出了这一网络演 化模型的解析方程组及迭代求解算法。通过实例计算，验证了这一复杂网络为无标度网 络，并且其幂率随着分裂相似度a ( f ) 的增大而增大，并可逼近+ * 。当新增分裂点的度 始终保持不变时，该网络演化与b a 模型一致。 关键词：无标度网络；幂率；自相似性；分裂 一类节点分裂网络演化模型的研究 r e s e a r c ho nt h ee v o l u t i o n a r ym o d e lo fak i n do fv e r t e x s p l i t t i n gn e t w o r k a b s t r a c t t 瓢ei n a b i l i t yo fc o n t e m p o r a r ys c i e n c et od e s c r i b es y s t e m sc o m p o s e do fn o n i d e n t i c a l e l e m e n t st h a th a v ed i v e r s ea n dn o n l o c a li n t e r a c t i o n sc u r r e n t l yl i m i t sa d v a n c e si nm a n y d i s c i p l i n e s ，r a n g i i l gf r o mm o l e c u l a rb i o l o g y t oc o m p u t e rs c i e n c e s c a l e f r e en e t w o r ki st h en e t m a to b e y sp o w e r - l a wd i s t r i b u t i o n b am o d e li st h ef i r s tm o d e lo ft h es c a l e f r e en e t w o r k ， w h i c hc a t c h e st w on e c e s s a r yf o n n a t i v em e c h a n i s mo ft h es c a l e f r e en e t w o r k - - i n c r e s c e n ta n d p r e f e r e n t i a l a t t a c h m e n ta n ds h o w st h er e a s o n 也砒t h el a r g es c a l ec o m p l i c a t e dn e t s e l f - o r g a n i z e st os t a t eo fs c a l e f r e en e t w o r k n ep u b l i c a t i o no fb a l sp a p e rs t a r t st h ec l i m a x o ft h er e s e a r c hi ns c a l e - f r e en e t w o r ka n db am o d e l i nt h er e c e n ty e a r so ft h en e wc e n t u r y ， t h es c i e n t i s t sp u tf o r w a r dm a n yf o r m a t i v em o d e l so fs c a l e f r e en e t w o r ka n dd os o m ed e e p r e s e a r c hi nt h em a l np r o p e r t yo f b am o d e l a p r o b l e mi sp r e s e n t e da b o u tt h ee v o l u t i o n a r yp r o c e s so ft h ev e r t e xs p l i t t i n gc o m p l e x n e t w o r k n er u l eo ft h ee v o l u t i o ni s ：e v e r yn e w l y - a d d e dv e r t e xi st h ec o p yo fo ri ss p l i tf r o m t h ee x i s t i n gv e h e x t h ea n a l y t i ce q u a t i o ns c to ft h i sn e t w o r ke v o l u t i o n a r ym o d e la n d a r i t h m e t i co fi t e r a t i o na r ep u tf o r w a r d as e r i e so fs i m u l a t i o nc a l c u l a t i o np r o v et h a tt h e c o m p l e xn e t w o r ki s s c a l ef r e en e t w o r ka n dt h ep o w e r - l a wi n c r e a s e sa l o n gw i t ht h e i n c r e m e n to ft h es p l i t t i n gs i m i l a r i t yd e g r e eo fa ( f ) a n de v e na p p r o a c h e s 幻+ w h e nt h e i n i t i a ld e g r e eo fe a c hn e wv e r t e xi sc o n s t a n t ，t h ee v o l u t i o n a r yp r o c e s so ft h ei l e t w o r ki s s i m i l a rt ot h a to ft h eb am o d e l k e yw o r d s ：s c a l e - f r e en e t w o r k ；p o w e r - l a w ；s e r f - s i m i l a r i t y ；v e r t e x - s p l i t t i n g 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签日期： 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 名：煎必哆 导师签名： 坪旦莩 大连理工大学硕士学位论文 引言 复杂性科学已经成为最受关注的新兴交叉学科之一，许多杰出的科学家为发展复杂 性科学进行了不懈的努力。然而，迄今为止，复杂性科学尚未取得重要突破。数学家f a d o d a 教授表达了多年来从事复杂性科学研究的科学家们的共同感受，他说：“w eg o f r o mc o m p l e x i t yt op e r p l e x i t y ( 我们从复杂到了困惑) ”。使科学家们感到困惑的一个重要原 因是，复杂性科学研究正处在探索阶段，一些基础问题有待解决，如：是否存在从简单到 复杂的自然法则的问题以及什么是复杂性的根源问题等，这些问题极大地阻碍着复杂性 科学研究的发展，如果不能从理论上得到解决，那么复杂性科学就难以建立起坚实的理 论基础，从而影响和制约复杂性科学的发展。 b a r a b 缸i 和a l b e r t 发现大量实际网络具有高度的自组织特性，其节点度分布服从幂 律分布，由于幂函数具有标度不变性，因此这类网络又被称为无标度网络 1 】。b a r a b d s i 和a l b e r t 给出了构造无标度网络的演化模型( b a 模型) 并利用平均场的理论计算了节 点度分布的幂指数 2 】。b a 模型捕捉到了许多现实网络的幂律形成机制，开创了复杂网 络研究【3 6 】的新局面。过去几年中，研究者在很多不同的系统中都发现了无尺度结构 7 。在b a 模型提出的短短几年内，研究者们就提出了许多无尺度网络模型 8 - 1 4 ， k l e m m k ，e g u f l u z v m l l l 】【1 2 】提出了基于节点有限记忆量的网络增长模型，证明了现实 网络中的节点的年龄和它被连接的概率呈负相关关系，而b a 模型在这一点上的结果恰 恰相反，j a r is a r a m a k i 和k i m l n ok a s k i 1 4 n 通过一系列随机走的方式选择和新节点连接 的老节点的机制建立一个无标度网络模型，并对b a 模型进行了深入研究 1 5 - 1 6 。 在现实自然中，一些网络演化中具有某种模仿、复制节点的功能，如此演化的网络 显示出某种节点间的自相似性。例如，在朋友网络中，新来者( 新节点) ，将被某个人 ( 老节点) 介绍给其关联者( 老节点的相邻点) 。计算机网络也具有类似发展特征。第 一个尝试正式定义和叙述无标度和自相似性这一概念的是a e i l l o 等人 1 7 ，把网络看成 是通过在每一时间步对某一网络加入新的结点和新的边而演化出来的结果。另一个尝 试，对某一给定的网络通过系统粗粒化这一更为结构化的概念来描述无标度和自相似性 这一概念的工作，应归功于i t z k o v i t z 等人 1 8 。主要内容就是通过研究基本的网络组件 的局部结构模体来重现整个网络，同时断言这是许多自然系统或人造系统的组成部分。 其观点就是通过识别在一个给定的网络中的模体- ( 这往往比在相应的随机网络中出现的 频率更高) ，就有可能把研究重点转移到网络的宏观统计特性( 例如幂律结点度分布) 上 来，而且试图去理解网络的一些更为微观的和结构上的特征。 针对这一现象，本文提出了具有自分裂机制的复杂网络演化模型，给出了这一网络 二茎堇盛坌型旦垒塑垡堡型塑婴塞 演化模型的解析方程组及迭代求解算法。通过实例计算，验证了这一复杂网络为无标度 网络，并且其幂率随着分裂相似度a ( f ) 的增大而增大，并可逼近+ 。当新增分裂点初 始时刻的度相同时，该网络演化与b a 模型一致。 1 复杂网络基本概念 近几年来，人们在刻画复杂网络结构的统计特征上提出了许多概念和方法，其中有 三个基本概念：平均路经长度( a v e r a g ep a t hl e n g h ) 、聚类系数( c l u s t e r i n gc o e m c i e m ) 和度分布( d e g r e ed i s t r i b u t i o n ) 。 1 1 平均路经长度 阿络中两个节点f 和_ ，之间的距离吒定义为连接这两个节点的最短路径上的边数。 网络中的任意两个节点之间的距离的最大之称为网络直径( d i a m e t e r ) ，记为d ，即 d 2 呼吒 ( 1 1 1 ) 网络的平均路经长度l 定义为任意两个节点之间的距离的平均值，即 三= r l 吒( 1 - 1 2 ) 2 n ( n + i ) 。列 其中n 为网络节点数。网络的平均路径长度也成为网络的特征路径长度( c h 啪c 蜥s t i c p a t hl e n g t h ) 。如果不考虑节点到自身的距离，那么要在公式( 1 1 2 ) 的右端乘上因子 ( + 戮知一1 ) 。在实际应用中，这么小的差别是完全可以忽略不计的。 1 2 聚类系数 一般的，假设网络中的一个节点f 有毛条边将它和其他节点相连，这t 个节点就称 为节点i 的邻居。显然，在这七1 个节点之间最多有可能有t ( 南一1 蟛条边。而这毛个节点 之间的实际存在的边数e 和总的可能的边数t ( 南一1 之比就定义为节点i 的聚类系数 e ，即 c f 一_ 2 e , ( 南( 毛一1 ) ) ( 1 2 1 ) 从几何特点来看，上式的一个等价定义为 c ：量盛i 塑整堕三鱼垄盟塑篓，。 q2 写耵雨蠢硅磊面丽 ( 1 2 2 ) 其中，与点i 相连的三元组是指包括节点i 的三个节点，并且至少存在从点i 到其他两 一类节点分裂网络演化模型的研究 个节点的两条边。 整个网络的聚集系数c 就是所有节点i 的聚类系数g 的平均值。很明显，0 s c 蔓l 。 c = 0 当且仅当所有的节点均为孤立点。c = i 当且仅当网络全是耦合的，即网络中任意 两个节点都是直接相连的。 3 度与度分布 节点i 的度( d e g r e c ) t 定义为与该节点连接的其他节点的数目。直观上看，一个节 点的度越大就意味着这个节点在某种意义上越“熏要”。网络中所有节点i 的度k t 的平 均值称为网络的( 节点) 平均度，记为 。喇络中节点的度分布情况可以用分布函数 p ( k ) 来描述。p ( k ) 表示一个随机选定的节点度恰好为k 的概率。 近几年的大量研究表明，许多网络的度分布可以用幂律形式p ( 七) o c 七”来更好地描 述。幂律分布也称为无标度( s c a l e - f r e e ) 分布，具有幂律度分布的网络也称为无标度网络， 这是由于幂律分布函数具有如下无标度性质。 幂律分布函数的无标度性质：考虑一个概率分布函数f ( x ) 满足如下“无标度条件”。 f ( a x ) = b y ( 曲 ( 1 3 1 ) 那么必有( 假定f ( 1 ) f ( 1 ) 0 ) m ) - f ( 1 ) x - r = ，( 1 ) ( 1 3 2 ) 也就是说，幂律分布函数是唯一满足“无标度条件”的概率分布函数。 上述性质可简单推导如下：取算= l ，我们有，( 口) = b f o ) ，从而6 = 九( 1 ) ，则 ，( 神：! 业! ( 1 3 3 ) ，( 1 ) 由于上述方程对任意a 都成立，方程两边对a 求导可得 z 丛盟：f ( x ) d f ( a 一) ( 1 3 4 ) d ( 甜)，( 1 ) d a 如果取a = l ，则有 工哿= 鬻m ) ( 1 s 5 ) d ( x )，( 1 ) 。 微分方程( 1 3 5 ) 的解为 l n m ) = 罴h x + l n ，( 1 ) ( 1 3 1 6 ) 两边取指数，即得公式( 1 3 2 ) 在一个度分布具有适当幂指数( 通常为2 sr s 3 ) 的幂律形式的大规模无标度网络 - 4 - 大连理工大学硕士学位论文 中，绝大部分的节点的度相对很低，但存在少量的度相对很高的节点。另一种表示度数 据的方法是绘制累积度分布函数( c u m t t l a f i v ed e g r e ed i s t r i b u f i o nf u n c t i o n ) 只= p ( 砷 ( 1 3 7 ) k f f i k 它表示的是度不小于k 的节点的概率分布。 图1 3 1 六种网络累积度分布曲线( 取自文献 6 】) f i g 1 3 1 如果度分布为幂律分布，即p ( 女) 一k ，那么累积分布函数符合幂指数为r 一1 的幂 一 = 鲞堇盛坌型塑堑遗些堡型塑曼塞 律： 最* k 7 * k 叫” t ；i 表1 4 1 t 曲1 4 1 ( 1 3 8 ) 网络 类型nmc b lr c 电影演员 无向4 4 9 9 1 32 5 5 1 6 4 8 21 1 33 4 8 2 3 0 7 8 公司董事无向7 6 7 3 5 5 3 9 21 4 44 6 o 8 8 数学家合作无向2 5 3 3 3 94 9 6 4 8 9 3 9 27 5 7 o 3 4 社 合作物理学家 无向5 2 9 0 92 4 5 3 0 09 2 76 1 9 0 5 6 会 领 合作生物学家无向 1 5 2 0 2 5 11 1 8 0 3 0 6 41 5 54 9 2 0 6 域 电话呼叫图无向4 7 0 0 0 0 0 08 0 0 0 0 0 0 0 3 1 6 电子邮件有向5 9 9 1 2 8 6 3 0 01 4 44 9 51 5 ，2 0 0 1 6 电子邮件地址 有向1 6 8 8 15 7 0 2 9 3 3 85 2 2 o 1 3 学生关系无向 5 7 34 7 7 1 6 61 60 w w w ( r i d e d u )有向2 6 9 5 0 4 1 4 9 7 1 3 55 5 51 1 32 1 ，2 4 o 2 9 信 w w w ( a l t a v i s t a )有向2 0 3 5 4 9 0 4 62 1 3 b m 91 0 51 6 22 1 ，2 7 息 领 引用网络有向7 8 3 3 3 9 6 7 1 6 1 9 88 5 7 3 弘 域 罗氏字典 有向1 0 2 25 1 0 3 4 9 94 8 7 0 1 5 单词搭配网络无向舶5 0 9 0 2 1 7 0 e + 0 77 0 i 2 70 4 4 自治层i n t e m e t无向 1 0 6 9 7 3 1 9 9 25 9 83 3 12 5 0 3 9 技 电力网无向 4 9 4 16 5 9 4 2 6 71 9 o 0 8 术 铁路网 无向5 8 7 1 9 6 0 36 6 82 1 6 0 6 9 领 软件包 有向1 4 3 9 1 7 2 31 22 4 21 6 ，1 4 o 0 8 域 软件类 有向1 3 7 7 2 2 1 31 6 l 1 5 1 0 0 1 电子网络无向 2 4 0 9 75 3 2 4 8 4 3 41 1 13 0 0 3 对等网络 无向 8 8 01 2 9 61 4 74 2 8 2 1o 0 l 代谢网络 无向7 6 53 6 8 6 9 6 42 5 62 2 o 6 7 生 蛋白质网络无向 2 1 1 52 2 4 02 1 26 8 2 4o 0 7 物 领 海洋食物网 有向1 3 5 5 9 84 4 32 0 5 0 2 3 域 淡水食物网有向 9 29 9 7 1 0 81 9 0 0 9 神经网络 有向3 0 7 2 3 5 97 6 83 9 7 0 2 8 如果度分布为指数分布，即p ( 七) “g 一，其中r o 是一常数，那么累计度分布函 数也是指数型的，且具有相同的的指数 足“羔e 一么* e 一 k - - t ( 1 _ 3 9 ) 大连理工大学硕士学位论文 图( 1 3 1 ) 画出了一些网络的累计度分布曲线。其中曲线( a ) 对应于数学合作网络，( b ) 是1 9 8 1 至1 9 9 7 年间i n s t i t u t ef o rs c i e n t i f i ci n f o r m a t i o n 上发表的文献之间的引用网络，( c ) 为1 9 9 9 年的w w w 的一个拥有3 亿个节点的子网，( d ) 对应于1 9 9 9 年4 月的自治 ( a u t o n o m o u ss y s t e m ，a s ) 层的i n t e r a c t ，( e ) 表示美国西部电力网络，( f ) 表示酵母菌代谢 网络中的蛋白质相互作用。曲线( c ) ( d ) ( f ) 符合幂律，分布曲线在对数坐标系中基本为直线 形式；( b ) 只在末端符合幂律分布；( e ) 服从指数分布( 半对数坐标) ；( a ) 看上去像两个不 同指数的幂律曲线组合。图( 1 3 1 ) 横轴是节点的度，纵轴是累积度分布。 1 4 实际网络的统计性质 在近些年来，人们对来自不同领域的大量实际网络的拓扑特征进行了广泛的实证性研 究，表1 4 1 给出了部分结果。测量的性质包括：有向或者无向、节点总数n ，边总数 m 、平均度数 、平均路径长度l 、聚类系数c 。如果符合幂律，则给出幂指数r 。 表中的空白表示没有可靠数据。各种网络对应的参考文献见文献 6 】 大连理工大学硕士学位论文 2 复杂网络研究简史 2 1 从七桥问题谈起 当e u l c r 在1 7 3 6 年访问k o n i g s b c r g ，p r u s s i a ( n o wk a l i n i n g r a dr u s s i a ) 时，他发现当地 的市民正从事一项非常有趣的消遣活动。k o n i g s b c r g 城中有一条名叫p r e g e l 的河流横经 其中，在河上建有七座桥如图2 i 1 所示： 图2 1 1 f i g 2 1 1 这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一 次而且起点与终点必须是同一地点。 e u l e r 把每一块陆地考虑成一个点，连接两块陆地的桥以线表示，便得如下的图形： 圈2 1 2 f i g 2 1 2 后来推论出此种走法是不可能的。他的论点是这样的，除了起点以外，每一次当一 个人由一座桥进入一块陆地( 或点) 时，他( 或她) 同时也由另一座桥离开此点。所以 每行经一点时，计算两座桥( 或线) ，从起点离开的线与最後回到始点的线亦计算两座 桥，因此每一个陆地与其他陆地连接的桥数必为偶数。 七桥所成之图形中，没有一点含有偶数条数，因此上述的任务是不可能实现的。 欧拉对七桥问题的抽象和论证思想，开创了数学中的一个分支一一图论( g r a p h t h e o r y ) 的研究。因此，欧拉被公认为图论之父，而图2 也被称为欧拉图。事实上，今天 一9 一类节点分裂网络演化模型的研究 人们关于复杂网络的研究与欧拉当年关于七桥问题的研究在某种程度上是一脉相承的。 即网络结构与网络性质密切相关。 2 2 随机图理论 在欧拉解决七桥问题之后的相当长的一段时间里，圈论并没有得到足够的发展。2 0 世纪6 0 年代，由两位匈牙利数学家脚ds 和r 6 n y i 建立了随机图理论( r a n d o mg r a p h t h e o r y ) 被公认为是在数学上开创了复杂网络理论的系统性研究 1 9 1 。在e r d ；s 和r 6 n y i 研究的随机图模型( 称为e r 随机圈) 中，该模型始于个节点，没有连接边( 见图2 2 1 ( a ) ) ， 以概率p a ( n ) 用一条边连接每一对节点，产生一随桃图。e r 最伟大的发现是该图的许 多特性在p 。( j v ) 的临界值点突然出现，该图拓扑结构的一个非常重要的特性是树和环 的出现。k 阶树是一个有k 个节点k l 条边的连通图。k 阶环是一个有k 条边的环状序 列，其中，每两条邻边且只有这两条邻边有一个共同节点。e r 已经证明，若 p 。，c 1 ，则几乎所有的节点属于孤立树，但当各阶环出现时，在p 。，( 即 c = 1 ) 有一个突变。在物理文献中，e r 模型常常被认作是无限维逾渗，为属于连续域 逾渗的酱适性类别所知。在这种情况下，p c 蚝是系统逾渗临界值。当p 以系统碎 裂成许多小群，在以值点。构成一个大群，在渐进极限值时，包含所有节点。 _ l o o 俨 囝固 圈2 2 1 f i g 2 2 1 e r d o s - r 6 n y i ( e r ) 模型及w a t t s - s 响g a t z ( w s ) 模型示意图。( a ) 用e r 模型描述的随 机网络，以概率p 。连接的n 个节点，系统的总边数为n = p 站一。图例给出节 点数n = i o ，p e s = 0 及p 。= o 2 时的网络。在p 衄= 0 时，系统中没有边。我们选择每个 大连理工大学硕士学位论文 节点对并以概率p 。= 0 2 连接它们。图例显示出这个过程的结果，网络有9 条边。当 = l 时，模型产生一全连通图。( b ) w s 模型始于一维规则图，节点与邻接点及次邻 接点之间相连接形成边。则平均连通度为 _ 4 。然后，一部分边p 。随机重新连接 ( 它们的端点改接到随机选择的节点上) 。图例给出节点数n = 1 0 的网终，当时，系统为 有2 n = 2 0 条边的规则图。当= o 3 。有2 肺= 6 条边重新连接到随机选择的节点上。 注意p 。= 1 时，我们得到一随机圈与e r 模型p n = 随n 线性增长，当p w s = 1 时，系统变成一随机图，群集性差，且 随 对数增长。w s 发现在0 ) ，仍然高度集群。 w s 模型的连通度分布强烈依赖p 。，当p v e s = 0 时，p ( ) = 6 ( 七一z ) ，式中z 为网络配 位数，当p v s 为有限值时，p ( 女) 在z 周围仍出现峰值，但它变宽。最后，当p w s - - 1 ，p ( 七) 分布近似于随机图的连通度分布，即收敛于e r 模型在p w s = 时，所获得的分布( 见 图2 2 2 b ) 。 大连理工大学硕士学位论文 3b a 模型 3 1 队模型 e r 随机图的w s 小世界模型的一个共同特征就是网络的连接度分布可以近似用 p o i s s o a 分布表示，该分布在度平均值k 处有一个峰值，然后呈指数快速递减。这意 味着当k 时，度为k 的节点几乎不存在。为了解释幂律分布的产生机理，b a r a b 巨s i 和a l b e , r t 提出了一个无标度网络，现被称为b a 模型【2 3 】。b a 网络模型用两步来详细说 明。( 图3 1 1 ) _ e o 口 _ 0 o o o oo oo 口o o 肉j 洮j 礴 砣；豫 嘲k 一。吣澎絮蠓岁 图3 i 1 f i 9 3 1 1 图3 1 1b a 模型图解及其变量。( a ) 当m o = 3 ，m = 2 时的b a 模型。在t = 0 时， 系统包含m o = 3 个孤立节点。在每个时间间隔添加一个新节点，新节点连接到m = 2 个 节点上，节点按照公式( 3 1 1 ) 择优确定有高度连通度的节点。园此，在t = 2 时，有 + f = 5 个节点，两条新边用短划线画出。由于择优连接，新节点连接到已经有高连通 度的节点上。( b ) 当= 3 ，m = 2 时的模型a 。在f = 0 时，有m o = 3 个节点没有边。 在每个时间间隔，一个新节点添加到新系统中，随即连接到m = 2 个已经存在的节点上。 如( a ) 。在t = 2 时，有5 个节点及4 条边。在f = 3 时，第六个节点添加到系统中。两条 如( a ) ，在f = 2 时，有5 个节点及4 条边。在t = 3 时，第六个节点添加到系统中。两条 一类节点分裂网络演化模型的研究 新边用短划线画出。又由于缺少择优连接，新节点以相等的概率连接到系统中的任意节 点上。( c ) 当n = 8 个节点时的模型b 。在该模型中节点数是固定的。t = 0 时没有边。 每一部弓l 入一条新边，一端连接到随机选择的节点上，另一端服从( 3 1 1 ) 式择优连 接。在f - n ，在所研究的例中有8 条边，在f ；n ( n 一1 彳时，系统全连通。 ， ( 1 ) 增长：开始于少量节点( ) ，在每个时间间隔添加一个具有m 岱) 条边的新 节点( 连接到已存在于系统中的节点上) 。 ( 2 ) 择优连接：当选择与新节点连接的节点时，假设新节点连接到节点i 的概率石取 决于该节点的连通度t ，则有 厶 筇( 也) = 夕七 ( 3 1 1 ) ，七一 在t 个时间间隔后，模型产生一有n = m o + f 个节点和m t 条边的随机网络。如图3 i 2 ( a ) 所示，该阿络演化进入标度不变状态。具有k 条边节点的概率服从幂律分布。指数 为。2 9 + 0 1 。标度指数与模型中的唯一参数m 无关。由于从实际网络观察到的幂律 分布描述在系统演化的不同阶段中规模额不相同的系统，人们期望准确模型应能提供分 布状态，其主要特性与时间无关。的确，如图3 1 2 ( b ) 所示，p ( 女) 与时间无关( 且随 后与系统规模n = + f 无关) ，表明尽管不断增长，系统组织自身进入无标度静止状态。 图3 1 2 f i g 3 1 2 图3 1 2 ( a ) b a 模型的联通度分布。n = m o + f = 3 0 0 0 0 0 ，z o = m = l ( 圆形) = m = 3 大连理工大学硕士学位论文 ( 方块) ，m o = m = 5 ( 菱形) 及= m = 7 ( 三角形) 。短划线斜率为r = 2 9 。插图给出 m 值相同的重新按比例绘制的分布烈哆乞：，短划线的斜率为r = 3 。c o ) 当= m = 5 ， 系统规模n = 1 0 0 0 0 0 ( 圆形) ，n = 1 5 0 0 0 0 ( 方块) 及n = 2 0 0 0 0 0 ( 菱形) 时的。插图给 出在f l = 5 及f ，= 9 5 时，添加到系统的两个节点的连通度的时间演化。短划线斜率0 5 如 式( 2 4 1 4 7 所预测的一样。 接着，我们描述解析计算概率p ( k ) 的方法，可精确确定标度指数，。增长与择优连 接的结合使单个节点连通度产生了有趣的动态特性，由于节点增长相对于其他节点与其 连通度成正比，具有大量连接边的节点是那些在网络演化早期就已经添加的节点。于是， 一些最老的节点就有相当长的时间获得连接边，这是造成p ( k ) 高k 部分的主要原因。给 定节点连通度的时间相关性可用连续域方法解析计算。假设k 连续，则概率 抓蛐2 多圭岛可理解为岛的连续变化率。因此对节点i ，有 百o k , 也一甄k , ( 3 l 2 ) 考虑到勺= 2 肌。在一个时间间隔连通度的变化为址= m ，可知a = m ，有 孽：生( 3 1 ) 孤2 t 当初始条件为节点f 在时刻添加到系统，连通度q ) = n l ，方程的解为 眇m 1 4 ) 如图3 1 2 b 的插图所示，数值研究结果表明与其预测值完全一致。因此，老节点( 小 ) 以年轻节点( 大) 的损耗方式来增加其连通度，随着时间变化导致一些节点高度 连通，一种实际网络中很容易看到的“富者越富”现象。此外，这个特性可用来解析计 算r 值。用( 3 1 47 式，节点连通度t ( t ) 小于的概率p ( t ( f ) ( + f 一1 ) e x p ( 1 一兰) 一+ 1 ) 一坠竺型! 二猃二业 5 ，+ t 利用方程( 3 1 8 ) ，假设经过长时间，得 一类节点分裂网络演化模型的研究 p ( 七) = 三e x p ( 羔) ( 3 2 6 ) r f lr n 表明式( 3 2 ，1 ) 的系数为 b ：三，口：三 ( 3 2 7 ) m ，扎 结果，模型中节点具有特征连通度： 2 吉跏 ( 3 28 ) 与系统中节点平均连通度之半相同，因 - 2 m ，如图3 2 1 a 插图所示，数值模拟结果 与理论预测接近。该模型的指数特征度分布表明，缺少了择优连接，就消除了b a 模型 的无标度特性。 3 3b a 模型的限制条件( 模型b ) 该模型检验增长特性是保持从现实网络观察到的无标度状态所必需的这一假设。模 型b 详细说明如下：( 见图3 1 t o ) 开始于个节点且没有边，在每个时间间隔随机选择一节点，并以概率 吣卜答q 连接到系统中肺舶l 图3 _ 3 1 f i g 3 5 1。 因此，与b a 模型相比，改变形消除了增长过程，在网络演化过程中节点数保持常 大连理工大学硕士学位论文 数a 在早期，模型显不出幂律标度( 见图3 3 1 ) ，p ( k ) 不稳定：由于是常数，边的数 量随时间增长。在t = n 2 时间间隔后，系统达到所有节点均连接的状态。 图3 3 1 ( a ) 在n = 1 0 0 0 0 及t = n ( 圆形) ，扣5 n ( 方块) 及t = 5 n ( 菱形) 时模 型b 的连通度分布。( b ) 两节点连通度时间相关性。系统规模n = 1 0 0 0 0 。插图给出由 重新按比例绘制的连通度，支持理论预测t ( f ) _ l 。 单一节点连通度的时间演化可用连续域理论解析计算，与前述模型相近似。节点i 的 连通度变化率有两个作用：第一，描述随机选取的节点作为初始连接的概率 ，r “( 畸) _ 。第二，i e = v = j = 万( 墨) 2 多圭岛，描述从随机选取的一个节点中产生的 一条边连接到节点i 的概率： 警“轰+ 专 ( 3 3 1 ) 考虑到七，= 2 t ，且连通度在一个时间间隔的变化为龇= 2 ，从总数中去掉来源于 且终止于相同节点的边得a = 一1 ，导致 孽：旦生+ 一1 ( 3 3 2 ) a fn 一12 tn 。 方程解的形式 岛( f ) ；兰型二+ 甜( _ 1 ) n ( n 一2 1 由于n 1 ，可简化丘 ( f ) = 2 f + 甜“ ( 3 3 3 ) ( 3 3 4 ) 因节点数是常数，对节点无“进入时间”t ，然而，对存在一时间模拟：当节点i 初次 被选为一条边的起始点的时刻，结果其连通度从0 到l 变化。方程( 3 3 3 ) 仅对t t i 有 效。仅当f 之后，所有节点服从这个动态特性a 常数c 可由条件女，= 2 f 确定，其 j 值为 c = 0 ( 3 3 5 ) 于是 一一 二耋堇盛坌型旦堑塑些堡型堕塑壅 岛( r ) z 万2 f ( 3 3 6 ) 数值模拟结果见图3 3 1 b ，与该预测完全一致。表明在丁* n 的过渡时间后连通度 随时间线性增长。 以上所采用的连续域近似法预计，在过渡阶段后，所有节点的连通度应具有式( 3 3 6 ) 所给定的相同值。期望连通度分布围绕其均值为一高斯分布。的确，图3 3 1 a 显示出随 着时间增长p ( 七) 的形状从最初的幂律变化到高斯分布。 模型a 和b 不能产生无标度分布表明，增长和择优连接这两种机制对于再现从实 际网络中观察到的稳定的幂律分布是必要的。 4 复杂网络的自相似性 现实中很多网络都有一个非常明显的特征，那就是该网络的部分与整体有着很明显 的相似性i 而局部在某种意义上与整体相似，即自相似性( s e l f - s i m i t e r i t y ) ，正是分形( f r a c t a l ) 的一个基本特征。图4 1 把等级网络与一个经典的具有白相似性的分形s i e r p i n s k i 三角形并列放在一起，以作比较。( 图4 1 a 见文献【2 4 】) 图4 i 等级网络与s i e r p i n s 崩三角彤 f i g 4 1 当然，绝大多数实际网络以及网络模型结构，都不具有像这样一个等级网络一样能 够棍直观地看出来自相似性。特别地，复杂网络的小世界特征意味着网络平均路径长度 l 可用网络模型n 的对数函数来表示即“i n n ，其等价表示为 。p 纥 ( 4 1 ) 其中常数上t 1 表示特征长度。上式意味着网络规模是平均路径长度的指数函数。而自相 似性则要求满足某种幂律关系【2 5 】。然而，s o n g 等人的研究指出，许多实际网络，包括 w w w 、社会网络、蛋白质交互作用网络( p i n ) 和细胞网络等，在某种长度一标度 ( 1 e n g t h - s c a l e ) 下确实是自相似的【2 4 】。 与自相似性密切相关的一个概念是分堆数。计算自相似分形的维数的一种常用方法 是盒记数法( b o x - c o u n t i n gm e t h o d ) 。我们知道，任意一个几何图形都可以嵌入在一个 整数维的欧式空间中。用盒记数法计算一个几何图形的维数的基本思想就是用边长为z 的盒子来覆盖该图形，并统计完全覆盖该图形所需要的最少盒子致以以) 。这里的盒子 在一维的情况下就是线段，二维情况下就是正方形，三维情况下就是立方体，而f 。也称 为盒子的尺寸( s i z e ) 。图像的维数的近似计算公式为 一类节点分裂网络演化模型的研究 d 。一! 翌丝盟 ( 4 2 ) 。l n ( 1 b ) 等价地由幂律标度公式 虬( ) = “。( 4 3 ) 但是，在一般情况下，在理论上只有当盒子尺寸趋近于零的时候，才能由公式( 4 2 ) 得 到维数的精确值。人们通常画出n s ( ) 和之间的关系，拟合直线的斜率的负值就是如。 s o n g 等人通过把盒记数方法推广用于复杂网络，指出对于许多复杂网络也存在类 似于分数维的自相似指数，从而也具有某种内在的自相似性。s o n g 等人对用于覆盖复 杂网络的的尺寸为的盒子规定为：盒子中任意两个节点之间的距离都小于。这样就 可以把一个网络分割成一组不重叠的盒子。但是这里面存在一个复杂的计算问题：对于 大规模网络，存在着数量巨大的不同的分割方式。s o n g 等入是通过穷举搜索找到覆盖 网络需要的最少盒子数的，因此该问题的有效近似计算法仍然是一个值得研究的课题。 通过检查这个最少盒子数以心) 和盒子尺寸之间的关系，他们发现许多实际网络都服从 分形所遵循的幂律标度公式( 4 3 ) 。图4 2 ( a ) 一( c ) 的上半部分显示了也和的对数坐标 关系。 警 鼍 3 掌 1 鼍 、“飘。 1 “嗨啮 ! i 、。r 。，强噶。 淄。”、；啦j o & e 鸭i 二二。码靠 - 忡蛙j t 矗d 自_ _睦- o i 。0 、 b 图4 2 复杂网络的自相似标度( 取自文献 2 4 1 ) f i g 4 2 ( a ) w w w 和电影演员网络； 大连理工大学硕士学位论文 ( b ) 两个蛋白质交互作用网络( p 矾) ； ( c ) 三个细胞网络； ( d ) w w w 度分布 岛= 2 = 3 = 4弓三哼 图4 3 复杂网络的重整化过程( 取自文献 2 4 】) f i g 4 3 s o n g 等人进一步通过采用重整化过程( r c n o r m a l i z a t i o np r o