（运筹学与控制论专业论文）复杂网络的特征谱应用初探.pdf

2 0 0 7 年上海大学硕士学位论文 摘要 网络是由结点以及连接结点的连线组成的集合，现实生活中- 的许多系统都是 以网络的形式存在的，如因特网、社会中的熟人网络、生物学中的新陈代谢网络 等。关于网络的研究最初是从欧拉的哥尼斯堡七桥问题开始的，逐渐发展成了离 散数学中的一个重要分支图论，由于当时可获得的实际数据规模小等原因， 图论主要研究的对象是规模较小且结点数目固定的网络。随着计算机技术和通讯 技术的发展，可获得的实际数据大量增加，人们开始把对实际网络的研究从结点 数目固定的小规模网络转向结点数目变化的大规模网络。随着研究重点的转移， 人们发现许多在小规模网络中成立的结论，在大规模的网络中已不再适用。因此 人们开始寻找新的方法来对实际网络进行研究，利用网络的特征谱来进行研究便 是其中的一个很好的方法。 本文主要研究了复杂网络的特征谱在分析网络结构和计算群集系数等方面 的应用，提出了一个更切合实际的模体增长秩次择优模型，并用特征谱对其群集 系数进行了研究。此外，还对复杂网络特征谱的期望和标准差进行了分析。 第一章简要介绍了复杂网络的基本内容和本课题的研究背景，并对本文研究 内容做了扼要阐述。 第二章比较详细地介绍了复杂网络邻接矩阵和l a p l a c i a n 矩阵的特征谱的研 究现状，并对主要结论和使用的方法做了简要论述。 第三章主要是对邻接矩阵特征谱的数字特征来研究的。首先介绍了特征谱的 计算方法，然后对特征谱的期望和标准差进行了分析。 第四章主要利用特征谱密度来分析网络的结构。首先，利用谱密度对秩次增 长模型的演化机理进行了分析；然后，把一些实际网络的谱密度与已有模型进行 了比较。 第五章主要利用特征谱来计算网络的群集系数。首先，导出了特征谱计算群 集系数的计算公式并对现有模型的群集系数进行了分析；然后，根据前面的分析 提出了一个新的模型，并对其群集系数进行了研究 本文的结论部分对所做工作进行了概括，并对进一步的研究指出了方向。 关键词：复杂网络；特征谱；谱密废；网络结构；群集系数 l 2 0 0 7 年上海大学硕士学位论文 a b s t r a c t n e t w o r k sc o n s i s to f t h en o d e sa n de d g e sw h i c hc o n n e c tt h e m m a n ys y s t e m si n t h er e a lw o r l dt a k et h ef o r mo f n e t w o r k s s u c h 船i n t e m e t , s o c i a ln e t w o r k so f a c q u a i n t a n c e ，m e t a b o l i s mn e t w o r k sa n d s oo n e u l e r ss o l u t i o no f t h ek o n i g s b e r g b r i d g ep r o b l e mi so f t e nc i t e da st h ef i r s tt r u ep r o o fi nt h et h e o r yo f n e t w o r k s ，a n d d u r i n gt h et w e n t i e t hc e n t u r yg r a p ht h e o r yh a sd e v e l o p e di n t oas u b s t a n t i a lb o d yo f k n o w l e d g e b e c a u s et h ea v a i l a b l ed a t aw a sf e w , t h em a i no b j e c t so f t h eg r a p ht h e o r y a r en e t w o r k s 谢mf e wa n du n c h a n g e a b l en o d e s w i mt h ed e v e l o p m e n to f c o m p u t e r s c i e n c ea n dc o m m u n i c a t i o nt e c h n o l o g y ，t h e r ea r em o r ea n dm o r ea v a i l a b l ed a t at h a t c a nb ea n a l y z e d s o ，t h ec h a n g eo f t h er e s e a r c hd i r e c t i o nf r o mu n c h a n g e a b l es m a l l s c a l en e t w o r kt oc h a n g e a b l el a r g es c a l en e t w o r ki so b v i o u s h o w e v e ri ti sf o u n d t h a t m a n yc o n c l u s i o n sw h i c hw o r kb e f o r ed on o tw o r kn o w s o ，s o m en e wm e t h o d sa r e i n t r o d u c e dt os t u d yt h e s en e t w o r k s , t h es p e c t r aa n a l y s i so f n e t w o r k si sav e r yg o o d o n e i nt h i sp a p e r , w em a i n l yu s et h es p e c t r ao f n e t w o r k st oa n a l y z et h es t r u c t u r e ， c o m p u t et h ec l u s t e r i n gc o e f f i c i e n to f n e t w o r k sa n db u i l dan e wm o d e lt h a ti sm o r e s i m i l a rt ot h er e a ln e t w o r k s w ea l s oa n a l y z et h ee x p e c t a t i o na n ds t a n d a r de r r o ro f t h e s p e c t r a i nt h ef i r s tc h a p t e r ，w em a i n l yi n t r o d u c et h eb a s i cc o n c e p t so f c o m p l e xn e t w o r k s a n dt h eb a c k g r o u n do f o u rr e s e a r c ht o p i c s t h e nw eb r i e f l yi n t r o d u c et h em a i n c o n c l u s i o n so f t h er e s e a r c ha n dm e t h o d sw en s e i nt h es e c o n dc h a p t e r ，w ei n t r o d u c et h er e s e a r c hd e v e l o p m e n to f t h es p e c t r ao f c o m p l e xn e t w o r k si nd e t a i l ，a n dg i v et h em a i nc o n c l u s i o n sa n dm e t h o d so f t h o s e r e s e a r c h e s i nt h e “r dc h a p t e r , w em a i n l ys t u d yt h en u m e r i c a lf e a t u r e so f t h ea d j a c e n t m a t r i x f i r s f l y , w ei n t r o d u c et h em e t h o dt oc o m p u t et h es p e c t r a , a n dt h e nw ea n a l y z e t h ee x p e c t a t i o na n ds t a n d a r de r r o ro f t h es p e c t r a i nt h ef o u r t hc h a p t e r , w em a i n l ys t u d yt h en e t w o r ks t r u c t u r e su s i n gt h es p e c t r a d e n s i t y f i r s t l y , w ea n a l y z et h ee v o l u t i v ef e a t u r e so f t h es c a l e - f r e en e t w o r kg r o w t hb y r a n k i n g , t h e n , w ec o m p a r et h es p e c t r ad e n s i t yo f s o m er e a ln e t w o r k sw i t ht h ee x i s t i n g n e t w o r km o d e l s i nt h ef i f t hc h a p t e r , w em a i n l ys t u d yt h ec l u s t e r i n gc o e f f i c i e n tu ；i n gt h es p e c t r a o f n e t w o r k f i r s t l y , w eg i v eaf o r m u l at oc o m p u t ei tb ys p e c t r aa n da n a l y z et h e mo f i l 2 0 0 7 年上海大学硕士学位论文 t h ee x i s t i n gm o d e l s ；t h e n , w eb u i l dan e wm o d e lb a s e do nt h ef o r m e ra n a l y s e sa n dg e t i t sc l u s t e r i n gc o e f f i c i e n t i nt h ec o n c l u s i o ns e c t i o n , w e $ u m m a r i 7 _ ea l lt h ew o r kw eh a v ed o n ei nt h i sp a p e r a n dg i v et h ef u r t h e rd i r e c t i o n so f t h er e s e a r c h k e yw o r d s ：c o m p l e xn e t w o r k s ，s p e c t r a , s p e c t r ad e n s i t y , n e t w o r ks t r u c t u r e ， c l u s t e r i n gc o e f f i c i e n t i l l 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人己发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 签名：叁基。弘。日期：2 丑孟2 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅：学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 2 0 0 7 年上海大学硕士学位论文 第一章绪论 复杂网络是对复杂系统的一种抽象概括，它用结点来表示系统中的个体，用 连线来表示个体间存在的相互作用，从这个意义上来说，一个复杂系统就是一个 网络。从复杂网络的角度来研究系统的结构可以使我们方便地从整体上了解系统 的结构特性和演化机理，减少和避免系统故障的发生，从而使系统更好地运转。 特别地，在生物、计算机和疾病传播等许多学科的发展中，了解网络的拓扑结构 一直都是一个很重要的问题。但由于现实中的网络是由大量不同的个体组成的， 且个体间存在不同的相互作用。因此研究现实中网络的结构是一个很复杂的问 题。下面先介绍复杂网络研究中最常用的三个基本网络模型。 1 1 三个基本网络模型 上世纪6 0 年代初，匈牙利数学家p e r d 6 s 和a r 6 n y i 通过著名的随机图模型， 运用概率的方法来研究随机图的临界现象和结构涌现f l 】，开创了图论的新方向。 在此后的很长一段时间内，随机图模型一直是复杂网络研究的重点。但随着因特 网和计算机技术的不断发展，可获得的实际网络数据逐渐增加，研究人员发现， 实际网络的连接概率是相互关联的，而不是像随机图模型那样相互独立的。因此， 实际网络和随机图模型的在结构上是有很大区别的，随机图模型并不能很好地反 映实际网络的特性【2 】。在对大量的数据进行分析总结后，d j w a t t s 等在1 9 9 8 年 提出了“小世界”模型嘲，反映了实际网络中普遍存在的小世界特性。随后，a l b a r a b 矗s i 等在1 9 9 9 年提出t b a 模型 4 1 ，反映了实际网络中普遍存在的无标度 特性。由于小世界和无标度特性在物理领域、生物领域和社会领域普遍存在【5 l ， 引起了数学、物理、生物和社会等许多学科研究人员的极大兴趣，从而掀起了复 杂网络的研究热潮。 1 1 1e r 模型 在随机图中，最简单也是最著名的模型就是以p e r d 6 s 和a r 6 n y i 命名的e r 模型，生成过程如下i l 】： 一条边连接着n 个带标号的结点，而这些边是从总共n ( n 一1 ) 1 2 条可能的边 2 0 0 7 年上海大学硕士学位论文 中随机选取的，这样的个结点力条边的图总共有c 品( 州) 2 种，构成了一个概率 空间，其中每一种图都是等概率的。另一种等价的定义为：给定个结点，每一 对结点以概率p 相互连接。这时总边数是一个随机变量，期望值为口 ，( 一1 ) 2 。 为了便于讨论，我们假设连接概率p 满足脚严；c ，其中c 为常数。 从上面的生成过程可知，它的度分布为 p ( k ) = c 嘉_ l p ( 1 一p ) ”4 。 对大的情形可以近似为p o i s s o n 分布： p ( 七) 。型芏p 哪 | ! 其中平均度k 吲_ 1 ) = n p 。 1 1 2w s 模型 研究发现，现实网络不仅和随机图模型一样具有平均路径小的特点，而且群 集系数比较大，为了解决这个问题，d j w a t t s 和s h s t r o g a t z 弓 入了小世界网的 概念和模型。w s 模型生成规则如下 首先，从编号为l 、2 、n 的个孤立的结点开始，每个结点与位于同 一侧最相邻的k 2 ( k 为偶数) 个结点相连，从而形成一个具有个结点k n 2 条 边的环形网络，其中每个结点的度均为k 。然后，再以概率所为网络中的每条边 重新连线，重新连线的另一结点从个结点中随机选取。重新连线同样是按照 同一个方向进行的，先对与结点最相邻的边进行重新连线，个结点最相邻的边 1 矿 1 一 图1 1w s 模型的度分布嘲 2 2 0 0 7 年上海大学硕士学位论文 重连完之后，再对次相邻的边重新连线，依此类推，直至结点一侧的所有边都重 连完毕，在重新连线的过程中要保证没有自连线和重复边产生。 w s 模型的度分布如图1 1 所示，从图中可以看出，它的度分布与e r 模型 的度分布相似，近似服从p o s s i o n 分布。 1 1 3 b a 模型 大量的实证研究表明，许多现实网络的度数分布都是幂律的，具有无标度特 性，与e r 模型和w s 模型有很大的区别。为了探索其形成机制，人们提出了许多 无标度网模型。最早的也是最简单的无标度网模型是a l b a r a b 6 s i 和r a l b e r t 提 出的b a 模型，它的生成规则为 4 1 ： 开始有个孤立( 或全连通) 结点，然后在每个时间步t 向网络添加一个新 结点和m ( a m o ) 条连线，使得新结点与埘个网络中的旧结点相连，其中m 条连线 选取旧结点是按照单个旧结点的度数与所有旧结点度数之和的比择优进行的。 b a r a b 矗s i 和a l b e r t f f j 平均场方法，得到度分布为 7 1 ： 撇) = 堂= 羔mt 古 僦 n 十弗。 b f l b a 模型的度分布是幂律的，并用数值模拟证实了这个结果r 玎由于b a 模 型不仅度分布具有无标度性，而且还体现了现实网络的增长和择优机制，因此得 到了广泛的引用。 1 2 特征谱的引入 随着因特网和疾病传播网等实际网络对人们日常生活的影响越来越大，这些 网络的组织原则、拓扑结构与动力学特性引起了人们的关注，成为了科学家研究 的重点。目前，复杂网络性能指标的研究还主要集中在其度分布、群集系数和平 均最短路径等的模拟与分析上璋l ，它们虽然重要但不能全面反映网络的结构。然 而，网络的邻接矩阵全面刻画了网络中结点之间的相连关系，因此网络邻接矩阵 的特征谱可以用来比较全面地分析网络的拓扑结构和动力学特性，并有着很广泛 的应用f 9 d 町。作为探索，本文只讨论简单网络，即无自连线和重复边的网络。 对一个简单无向网络g ，它的邻接矩阵彳( 回定义为：如果网络中两结点f 2 0 0 7 年上海大学硕士学位论文 和，有边相连，则= 1 ，否则为0 ，且吼= 0 。另外，g 的l a p l a c i a n 矩阵以g ) 定 义为d 彳，其中d 是对角线元素为相应结点度数的对角矩阵，彳是g 的邻接矩 阵。从定义可以看出，l a p l a c i a n 矩阵是邻接矩阵的变形，二者都是对网络结构 的刻画。特征谱就是矩阵彳或上特征值的集合。 从上面的定义我们知道，爿( g ) 是g 的数学表示，它包含了g 的全部信息，通 过分析4 ( g ) 我们就可得到g 的各种特性，如设屯= ，唧，则屯就是结点f 的度数 从爿( g ) 得出的特征谱可以用来计算网络中的环的个数，利用计算所得的三角形 ( 即边长为3 的环) 个数可以计算网络的群集系数，谱密度则可以用来分析网络的 结构。同时，三( g ) 的特征谱在网络同步的稳定性分析和研究中有着非常重要的应 用【l 7 1 。因此网络的特征谱是分析网络结构特性和动力学特性的有力工具。在文 章中，我们还将进一步介绍特征谱在其他方面的应用。 1 3 本文的工作与内容安排 本文主要利用特征谱来研究复杂网络的特性，主要进行了以下的研究： ( 1 ) 编写了网络生成程序和特征谱的计算程序； ( 2 ) 对三类基本网络模型多次模拟结果分析特征谱的期望和方差规律； ( 3 ) 对现有网络模型谱密度做了模拟，并与实际网络进行了比较； ( 4 ) 提出了一个新模型模体增长秩次择优网络模型； ( 5 ) 利用特征谱分析了该网络模型的群集系数。 本文共分六章，除本章外其余各章具体安排如下： 第二章，总结了近年来在网络特征谱方面的研究进展，首先介绍了三类基本 网络模型邻接矩阵的特征谱密度和网络结构的关系及其在网络中心性和二分性 中的应用，接着介绍了谱序列中存在的标度不变性和结构涌现，最后介绍了网络 l a p l a e i a n 矩阵的特征谱与网络同步之间的关系以及在分析网络社团结构中的应 用。 第三章，由于本文涉及到许多大型实对称矩阵特征值的计算问题，本章将首 先介绍矩阵特征值的计算方法。然后通过编写网络生成程序和特征谱的计算程 序，分析三个基本网络模型特征谱的期望和方差规律。 4 2 0 0 7 年上海大学硕士学位论文 第四章，是对特征谱在分析网络结构中应用的一个探索。利用特征谱密度可 以反映不同网络中结构变化的特性，通过对秩次增长模型 2 0 1 谱密度的分析，指出 了秩次增长机制对模型的度指数变化的影响。另外，还对现有模型的谱密度与实 际网络的谱密度进行了比较，并分析了差异存在的原因。 第五章，介绍了特征谱在计算网络群集系数方面的应用。首先介绍了群集系 数的概念与计算方法，然后对现有模型的群集系数规律进行分析，指出了原因， 最后根据所发现的原因提出了新模型，并对新模型的群集系数进行了分析。 第六章，对全文工作进行总结，指出存在的问题，并对今后的研究工作进行 展望。 2 0 0 7 年上海大学硕士学位论文 第二章复杂网络的特征谱研究概述 随着复杂网络研究的深入，关于含有网络结构丰富信息的特征谱的研究逐渐 引起了人们的重视。上世纪五十年代末，美籍匈牙利科学家e u g e n ep w i g n e r 发 表文章指出【2 m 3 】：对于一个n x n 的实对称矩阵4 ，如果它的非对角线元素的均 值为0 ，二阶矩为一个常数并且任意阶矩有限，则当_ o o 时，4 的谱密度将收 敛于半圆形分布。由于复杂网络可以由实对称矩阵来表示，因此它们的谱密度是 否和w i g n e r 所说的一样也收敛于半圆形分布呢? 关于特征谱的研究便由此开始， 其他方面应用的研究也随之展开。本章将对特征谱研究的进展做一个详细的介 绍。下面先介绍谱密度的概念。 2 1 邻接矩阵的谱密度 设简单无向网络g 有个结点，由于它的邻接矩阵a ( g ) 是实对称矩阵，因 此根据矩阵理论，它有n 个实特征值( 重特征值按重数计算) ，记为五，_ ，= 1 9 * m9 n ， 在本文中我们均假设五也知。借助邻接矩阵的特征值，可以定义谱密度 p ( 丑) 和k 阶矩m 如下： p ( 名) = 古万( 五一乃) ， 丸5j 二p ( 名y 五 ( 2 1 ) 进一步，由矩阵特征值理论有 = 导兰- i ( 乃广；告a 护( ) = 专。邑口“ ( 2 2 ) 因为邻接矩阵的元素均为0 和i ，所以( 2 2 ) 式中最后一个等式右边的意思是： 如果吒t 气 魄 = l ，那么就存在一条长为k 的闭合回路使得从结点i 出发经过 k - 1 个结点可以返回。于是，n m k 就表示网络中存在的长为k 的闭合回路的总 数。当k = 3 时，由于一个三角形中有6 条闭合回路，因此n m 3 6 就是图中三角 形的数目。而在树状网络中，从一点出发只有经过偶数步才能返回同一结点，故 树状网络谱密度的奇数阶矩为0 。 6 2 0 0 7 年上海大学硕士学位论文 2 1 1 随机网络的谱密度 我们利用e r 模型来研究随机网络的谱密度。 为了便于讨论，在1 1 1 节的定义中我们假设连接概率p 满足p n 4 = c ，其中 c 为常数。下面是谱密度和奇数阶矩的模拟结果。 ab 4 ， c p ( i 一，) 4 , v p ( i 一，) 图2 1e r 模型的谱密度。取n = 3 0 0 0 ，所有图形都是由5 0 个不同的图取平均得来的。 为了使图形标准化，将横坐标轴和纵坐标轴分别变为币丽和p 币画可= 商。 表2 1e r 模型n = 3 0 0 0 时谱密度的奇数阶矩 当口 l 且_ 时，结点的平均度数秭= ( 一1 归* p = a v “一o ，由表2 1 可知，谱密度的奇数阶矩几乎为0 ，说明此时网络具有树状结构。当口= l 且一0 0 时，结点的平均度数( t ) zp = c ，谱密度如图2 1 a 和图2 1 b 所示。结合表2 1 可 知，若c 1 时，网络仍基本上为树状结构；而c l 时，谱密度的奇数阶矩远远 大于0 ，说明网络的结构发生了显著的变化，出现了环和分支( c o m p o n e n t ) ，分支 也称为集团。当0 s 口 * 讲“_ 佃，由图 2 1 b ，网络的谱密度接近半圆形分布口2 5 1 7 2 0 0 7 年上海大学硕士学位论文 2 1 2 小世界网的谱密度 根据1 1 ，2 节的定义，我们模拟了w s 模型的谱密度，如图2 2 所示。当p ，= 0 时，w s 模型是一个规则的圆环，由图2 2 a ，谱密度的形状非常不规则，由表2 2 ， 此时它有很大的三阶矩。当p ，= o 0 1 时，由图2 2 a ，谱密度的形状变得比较光滑 了，说明虽然只有少量的随机重连边，但网络的结构已经发生了改变，不再是规 则的圆环。当p r = l 时，w s 模型已经是一个完全的随机网络，只是此时结点的 最小度数不是任意的，而是k 1 2 。从图2 2 b 可知，随着易哼l ，谱密度p ( 五) 逐 渐趋向于半圆形分布，但由表2 2 可知，只对较小的n ，仍然有大的三阶矩。 ab 图2 2 w s 模型的谱密度。取= 1 0 0 0 。除a = 0 的情况外，其它图都是由5 0 个不 同的图取平均得来的。为了使图形标准化和便于同e r 模型比较，将横坐标轴和纵坐 标轴分别变为0 而和户币石t 罚，取p 为k j v 表2 2w s 模型谱密度的各阶矩 2 1 3 无标度网的谱密度 由1 1 3 节的定义可知：当所= = 1 时，b a 模型是一棵树，因此它的谱密 度一定是关于0 对称的。当m ) 1 时，如图2 3 所示，b a 模型谱密度的主体部分 8 2 0 0 7 年上海大学硕士学位论文 基本上是关于0 对称的，呈三角形吐而文献【2 6 】认为中部指数衰减，尾部是幂 律分布的。从图2 3 还可以看出，谱密度在0 点附近有最大值，说明存在大量的 模较小的特征值，文献【2 】和【2 7 】解释了这一现象的原因。 i ，即( i 一， 图2 3 b a 模型的谱密度。取= m = 5 。谱密度是由5 0 个不同的图取平均得来的。为了使 图形标准化和便于同e r 模型比较，将横坐标轴和纵坐标轴分别变为丽= 五和 p 坝l 一| 口) ，取p 为平均度数 与总结点数n 之比 , v 。 综上所述，三个模型的谱密度各不相同，反映了每类网络的结构特征。将实 际网络的谱密度与这三个模型比较，如果相似或相同，便可以认为此网络具有与 模型网络类似的结构，以便于做更进一步的研究。 l 置 i 睡帖 q 4 o24 五厕；两 图2 41 2 9 7 个结点的蛋白质相互作用网的谱密度“l ，同样坐标轴经过了与图2 3 类 似的标准化处理，取p 为平均度数 与总结点数之比 n 9 2 0 0 7 年上海大学硕士学位论文 例如，文献【1 1 】模拟了1 2 9 7 个蛋白质相互作用网的谱密度( 如图2 4 所示) 。 从这张谱密度图可以看出，它基本上与无标度网的谱密度相同。主要区别是它有 双尖峰，这又有点类似于规则网的谱密度。因此可以初步推断蛋白质相互作用网 是无标度网，但同时有大的群集系数，三类网络的基本模型还不能很好说明它的 形成机理。由于基因复制机理在生物网络形成中扮演着重要角色，值得人们进一 步探索。 2 1 4 特征谱在网络的中心性和二分性中的应用 网络的中心性是刻画网络局部结构的一个性质，它有许多不同的指标，例如， 结点度中心性( d e g r e ec e n t r a l i t yd c ) 、介中心性( b e t w e e r m e s sc e n t r a l i t y8 0 、特征 向量中一i 性( e i g e n v e e t o rc e n t r a l i t ye o 等 9 1 。在复杂网络的研究中发现，网络模体 ( m o t i f ) ( 或子图) 的数量在生物和技术等实际网络中常常包含许多重要信息。利用 ( 2 2 ) 式中网络的环状子图与特征谱的关系，e m e s t o 等 9 1 定义了子图中心性 ( s u b g r a p he e n t r a l i 锣c s ) 来度量网络的中心性。 由( 2 2 ) 式，令版( f ) = ( ) ，表示结点，所在的长为k 的闭合回路的个数。定义 结点，的子图中心性为。( f ) = 二坐铲。文献【9 】证明了：c s ( i ) = 窆( q ) z 口而： ” 2 l 其中m ，v 2 ，v 是 ，如，如所对应的特征向量所构成的向量空间的一组标准 正交基，而q 表示v ，的第，个元素。因此整个网络的子图中心性可以定义为 2 专善c s ( 7 ) 2 专善驴 子图中心性是根据结点参与子图的数目来定义结点重要性的，由于较小的子 图在网络中出现的次数较多，对较小的子图赋予了较高的权重；文献【9 】通过计 算比较得：子图中心性与其它中心性指标相比，可以更好地刻画网络的中心性， 从而更便于分析网络的结构。 如果一个没有自连线的网络中不存在长度为奇数的闭合回路，则这样的网络 称为二分图。网络的二分性是对网络与二分图相似性的表示，它有很多应用，例 如可以根据网络的二分性来研究疾病的传播速度等口司。虽然许多网络可以用二分 图近似地表示口s 】，但完全是二分图的实际网络并不存在。因此，一般都是通过讨 论网络二分性来对网络的特性进行分析。特征谱为度量网络的二分性提供了一个 简单的工具【1 0 1 ： l o 2 0 0 7 年上海大学硕士学位论文 予圈中心性( o ) 由两部分组成，一部分是长度为偶数的闭合回路，另一部分 是长度为奇数的闭合回路，它们可用双曲函数来度量，即 ( d ) = 专【c o s h ( 乃) + s i n l l ( 乃) 】= d k + o ) 。 v i 1 如果网络g = ( 矿，e ) 是二分图，因为没有长度为奇数的闭合回路，所以 r j v ( d ) 一= 1 7 善s 1 椒乃) = o 则( o ) = ( o ) 一= 去j - i c o s h ( 乃) 于是，长度为偶数的闭合回路所占的比例可用来度量网络的二分性，即 即，= 铬= 硭= 紫j v e 。j 显然，觑g ) s 1 当且仅当( d ) 耐= o 时，g 是二分图。因为( s c ) 蒯o 并 且有s i r i l ( 乃) s c 。s h ( 乃) ，所以对任意的觑g ) 都有委 ( g ) l 。 2 2 谱序列的标度不变性 网络的特征谱是对网络拓扑结构信息的一种压缩，如何从特征谱中提取信息 来研究网络的特性是特征谱研究的一个重要方向。下面介绍一种提取特征谱信息 的方法：用特征谱构造的时问序列来分析网络特性。 设有n + 1 个结点的简单无向网络g ，它的邻接矩阵彳的特征谱记为 磊五2 乃氐。用相邻特征值之差来构造时间序列 五= 五一五一- ；七= 1 ，2 ，n + 1 ) = 一凡，如一 ，如一如中厶一以 其中约定厶+ i = 如。文献【2 9 】将d e ( d i f f u s i o ne n t r o p y ) 方法和m f d f a ( m u l t i f r a c t a l d e t r e n d e df l u c t u a t i o n ) 方法相结合来分析邻接矩阵特征谱中的自相似结构和长程 相依关系。 m f d f a 方法【3 川可用来度量时问序列的长程相依关系。将特征谱的首尾相 接，便可得到所有可能的长度为珀g 片断，即 ( 丸，厶。，厶。) ；坍= o ，1 ，2 ， 对每一个长度为珀g 片断用阶数为r 的多项式进行拟合，这个多项式记为雒。如 果时间序列具有长程相依性，则它的方差关于，将满足如下的关系 3 0 1 2 0 0 7 年上海大学硕士学位论文 v ( f ，渤2 南荟( 善【k 一一, v l q 2 1月ll v ( 1 ，r ，q ) = v ( ，州4 一 如果a ( 2 ，r ) = o 5 ，那么时问序列是不相关的，即白噪声；如果口( 2 ，) i i n 口( 2 ，2 ) = 1 对p r r = 1 n ，存在两个标度片断，短片断的标度指数是0 8 1 ，长片断的标 度指数是0 6 4 b ) e r 模型的d e 结果，对p h = o 8 n i n j 值为 0 4 4 ，0 5 1 ，0 5 4 ，有拶0 5 i $ i 对p e r = i n ，j 值为0 6 6 d e 方法口1 1 可用来度量时间序列的自相似结构取向量组 一矗，五一 ， ，五一礼) ， 五一 ，乃一五，磊。一乃 ， 矗一九， 一厶， 。一磊一： ，如 果把每个向量看成是一个粒子在n 个时间步内的运行轨道，则每个向量的前n 个分 量之和就是该粒子到时间”为止的位移，因此上面的向量组可以被看成是一个由 + 1 个粒子组成的系统的扩散过程。取单位长度f = 柚n + i l n 飞j 2 ( + 1 ) ，将粒 子的位移范围分成j | l 毛个区间，用j 0 ( 功来表示在时间棚寸位移进入第m 个区间的 粒子数目，则d e ( 扩散熵) 定义为d 1 】 阶嵩器制， 假设这个扩散过程的概率分布函数( p d f ) 满足 p ( ) = 并= 专f 删2 ， 将p ( m ，栉) 代入s ( n ) 中，求积分得 1 2 2 0 0 7 年上海大学硕士学位论文 s ( 珂) = j t + # l n n 其中彳是一个只与p d f 有关的常数。用d e 方法可以得到任何形式p d f 的指数艿 的值，但只有在特殊的p d f 形式下才能用m f d f a 方法得到指数艿的值。也就 是说，一般情况艿a ( 2 ，) 仅对于p d f 是高斯( g a l l s s i a n ) 分布，即正态分布， 才有占= a ( 2 ，) 。对于l e v y 行走过程的p d f ，艿= 1 3 2 a ( 2 ，r ) 】。因此，结合使 用d e 方法和m f d f a 方法可以得到有关p d f 的重要信息。 表2 3w s 模型的d e 结果f 捌 p , o 0 2 r m v l r l n gp r o b a b l l w 图2 6 w s 模型的m f d f a 结果嗍k = 4 ，对0 p 0 3 2 时，a ( 2 ，2 ) * 1 ，因此网 侣 ：! 仰 堪尊 2 0 0 7 年上海大学硕士学位论文 络的结构是和b = l 时相似的。对于增长的随机网络( g 融叼模型即每一步都有 一个新结点加入，并且与网络中的一个旧结点用有向边相连，下面来讨论新结点 与有七条边的1 日结点相连的概率n 满足p k 。ck a ( o 护s 1 ) 的情况【3 2 1 。表2 4 说明 g r n 模型长程相依的指数范围在o 7 4 到0 8 3 之问，将d e 和m f j d f a 方法相结合 可以在大多数情况下判断p d f 的形式，根据表2 4 中所得结果可知大多数g r n 网 络的特征谱所构造的时间序列的p d f j t 从g a u s s i a r t j - 争布。 表2 4d e 和i v l f - d f a 方法相结合来判断g r n 模型的p d f 嚣1 0 d 0 0 2 64 - 0 ，0 2p d f0 a 士0 0 26 0 0 2 p d f 针对【2 9 】中构造的特征谱序列，文献【3 3 】又提出了一个新概念d f m ( d i f f u s i o n f a e t o d a lm o m e m ) 来分析时间序列。得到了复杂网络特征谱序列的标度不变性。 肌 根据p ( m ，1 ) ，首先定义数量q ( 雄) = p ( 所，撑) r ，称为p m ( p r o b a b i l i t y m l m o m e m ) 。将p ( m ，厅) 代入，求积分可得 l i l c ：( 功= 4 + 联l q ) l n n 其中彳是一个只与p d f 有关的常数。 1 4 2 0 0 7 年上海大学硕士学位论文 n 图2 7e r 模型的d f m 结果p ，1 。参数g = 3 。( a ) ，( b ) ，( c ) ，( d ) 对应的( ，p 奴，5 ) 分别为 ( 1 0 4 ，0 8 n , o 5 1 ) ，( 1 0 41 n ，0 。6 ) ，( 4 0 0 0 , 4 n , 0 6 8 ) 和( 4 0 0 0 ，8 n , o 8 7 ) 。 当占= 0 5 时，f ( m ) 是m n 5 的g a u s s i a n 函数。而艿0 5 则可反映扩散过 程与这个标准扩散过程的偏离。但由于假设p 咖，打) * j c 册( 刀) 。j 0 ( 行) 会引起波 动，可能会极大影响结果的准确性，因此， 3 3 毛e f m ( f a e t o r i a lm o m c n t ) 3 4 】的基础 上提出了d f m 的概念，定义为 丝 d f m q ( n ) = 如( 瓦一1 ) ( 繇一g + 1 ) m j l 并且利用 3 4 1 中的方法证明了 i n d f m = c + l n g = b + 鄙- q ) l n n 对于e r 模型，当p 艘 i n 时，艿均明 显大于o 5 ，如图2 7 所示。对于w s 模型，除个别点外，所= l 时的占均明显大 于p ，= o 的万值，如图2 8 a 所示。当所e o 0 5 ，0 2 】时，w s 模型可以很好地反 映实际网络的标度特性，此时艿e 0 7 1 + 0 0 5 ，如图2 8 b 所示。因此，可以认为 研【0 0 5 ，0 2 】时，占的值没有发生变化。对于g r n 模型，在0 = o 3 3 和0 = o 4 9 处占存在最小值o 5 3 和o 5 2 ，当o e 【0 5 4 ，l 】时，除极少数点之外，j 0 7 ，如 图2 9 所示。文献【3 3 j 还指出，由于复杂网络特征谱的标度特性与度分布有所不 同，所以可以根据特征谱的标度来对复杂网络进行重新分类。 l s c一。暑ka 2 0 0 7 年上海大学硕士学位论文 的 b 图2 8 w s 模型的万值【3 3 】。a ) n = 3 0 0 0 ，q = 3 ，易= o 和弗= 1 时钓占值。 b ) q = 3 ，k = 4 时占值与所的关系。 1 0 o 9 0 8 0 7 的 0 6 o 。5 0 2 3l 矩阵的特征谱及其应用 设简单无向网络g 有个结点，因为它的上矩阵是行和为0 的实对称矩阵， 若设厶表示矩阵第f 行第，列的元素，则l 的二次型可以表示为 岛五勺= - x j ) 2 o i lj t i o 所以二是半正定矩阵，存在个非负的实特征值( 重特征值按重数计算) ，并且0 一定是三的特征值，相应的特征向量为常特征向量( 即特征向量各分量的值相同) 。 1 6 一 丽 广 弘卜 一 铲 呵 矗= 二 丽竺 | w o 2 0 0 7 年上海大学硕士学位论文 2 3 1 特征谱在网络同步中的应用 l a p l a c i a n 矩阵的特征谱在网络同步的稳定性分析和研究中有着非常重要的 应用【i 7 l ，文献 1 4 】对此有详细的介绍。如果在网络的每个结点附上一个动力学 系统，而让有边相连的两个结点的动力系统之间存在相互的耦合作用，就形成了 一个动力学网络。下面考虑最简单的情况，即对称线性耦合时工矩阵特征谱的重 要应用。设各结点有相同的动力系统，m 维状态变量记为 x ，i = 1 ，2 ，n ) ，而耦 合h 是每个结点状态变量的函数。假定不考虑耦合时，第i 个结点所满足的状态 方程为掣；f ( x ) ，则在存在耦合作用的情况下，第，个结点所满足的状态方程是 i = f ( x ) 一盯，l # h ( x ) 其中盯是耦合强度，厶是矩阵三的元素。 为了与文献中记号保持一致，记上的特征谱为0 = r o r n q = 7 嗍。 b a r a h o n a 和p e c o r a i ”1 通过分析r i s s s l e r 振子的主稳定性函数( 对角化后的线性稳定 性方程) 的最大l y a p u n o v 指数k 与一般耦合参数盯= o r , 的关系，得出了当 啦 口 0 ，f 0 ，使得关系式 【d f 0 ( f ) ) + d h r d + d 【d f o o ) ) + d h 】s - r l 。 对于d s 孑成立，其中i 是阶单位阵，s 0 ) 是网络在t 很大时达到的同步状 态。如果 t r r i 一孑 ( 2 4 ) 那么同步状态稳定。 1 7 2 0 0 7 年上海大学硕士学位论文 图2 1 0r i ；s s i e r 振子的主稳定性函数最大l y a p