（运筹学与控制论专业论文）无标度网络的建模分析与度分布计算方法.pdf

摘要 本博士学位论文研究无标度网络我们选择无标度网络的建模分析，度分布计 算方法以及相关性等作为主要的研究方向本论文系统深入地研究了这些同题 首先，我们研究了无标度网络的模型构造与模型分析，侧重于揭示现实网络的 演化机制，构建适合现实网络的演化模型 其次，我们研究了度分布的计算问题根据马尔可夫链理论，我们提出了一种 新的度分布数值计算方法 第三，我们研究了无标度网络的相关性问题，重点讨论了b a 网络的度相关。 给出了b a 网络的联合度分布 本论文取得了以下几个创新成果， ( 1 ) 我们构建了四个无标度网络的演化模型，即模型3 5 1 至模型3 5 4 ( 见第3 5 节) 在模型3 5 1 中，我们考虑了网络的局部相互作用，即内部边和重新连接等 在模型3 5 2 中，我们提出了一种反择优删除连线的演化机制根据乎均场方法。我 们计算了这两个网络的度分布p ( k ) ，它们都是幂律分布 在模型3 5 3 和模型3 5 4 中，我们首次提出了网络的对数增长，这是一种新的 演化机制特别指出，我们无法求出这两个网络度分布p ( k ) 的解析表达式我们 利用自己提出的马氏链方法给出了度分布p ( k ) 的数值计算( 见第四章) ，数值结果 表明这两个度分布都具有幂律尾部 ( 2 ) 我们用随机过程的观点研究复杂网络，发现了无标度网络与马氏链之间的 阿在联系对于b a 模型，任意给定一个结点t ，设甄( t ) 表示它在t 时刻的度数， 我们证明了随时间变化的度数序列 垃( t ) ，t = l ，t + 1 ， 是个非齐次马氏链，给 出了具有时间相依的一步转移概率矩阵p i ( t + 1 ) ，i = l ，2 ， ( 3 ) 根据马氏链理论，由转移概率矩阵n o + 1 ) 可以给出网络在t 时刻的度分 布p ( k ，t ) 的矩阵运算表达式因为矩阵r ( t + 1 ) 具有特殊的简单结构，利用矩阵 运算性质，我们提出了一种度分布数值计算的新方法，简称为马氏链方法 我们应用马氏链方法研究了b a 模型和三个加速增长网络模型，其中b a 网络 度分布的数值计算与原有的解析解和数值模拟进行比较，三种结果十分接近( 见图 4 1 1 ) 特别地，对于两个具有对数增长的( 有向) 网络模型，用原有的解析方法无 法得到度分布的表达式。我们进行了度分布的数值计算，数值结果表明这两个度分 布都具有幂律尾部( 见图4 3 1 和图4 4 1 ) ，这两个系统都演化成无标度网络 ( 4 ) 我们研究了无标度网络的相关性问题，求出了b a 网络的联合度分布应用 率方程方法和二维母函数性质，我们给出了b a 网络相邻点对的联合度分布p ( k ，1 ) 的公式( 5 2 1 ) 应用平均场方法和顺序统计量性质，我们也给出了b a 网络任意点 对的联合度分布p ( k l ，如) 的公式( 5 3 1 ) 这两个联合度分布都证明了b a 网络具有 结点的度相关特征 关键词t 复杂网络，现实世界网络，随机图，小世界网络，无标度网络，统计属性， 拓扑结构，度分布，平均路径长度，集群系数，演化机制，演化模型，数值计算， 非齐次马尔可夫链，转移概率矩阵，双变量差分方程，二维母函数，顺序统计量， 相关性，联合度分布 a b s t r a c t i i i w ee x p l o r es c a i e _ 妇n e t w o r k si nt h i sp h d d i s s e r t a t i o n w ec h o o s et h em o d e l s d e g r e ed i s t r i b u t i o n sa n dc o r r e l a t i o n so fs c a l e - f r e en e t w o r k sa 8t h r e em a i nd i r e c t i o n sf o r r e s e a r c h t h e s ep r o b l e m sa r es t u d i e ds c i e n t i f i c a l l yi nt h i sd i s s e r t a t i o n 。 f i r s t ，w es t u d yt h ec o n s t r u c t i o na n da n a l y s i so ft h em o d e l sf o rs c a l e - f r e en e t w o r k s w ee m p h a t i c a l l yi n v e s t i g a t et h ee v o l v i n gm e c h a n i s m sa n de v o l v i n gm o d e l sw h i c ha r ef i t f o rr e a l - w o r l dn e t w o r k s s e c o n d ，w es t u d yt h ec o m p u t a t i o no fd e g r e ed i s t r i b u t i o n sf o rs c a l e - f r e en e t w o r k s b y t h et h e o r yo fm a r k o vc h a i n s ，w ei n t r o d u c ean e wm e t h o dt oc a l c u l a t en u m e r i c a l l yt h e d e g r e ed i s t r i b u t i o n s t h i r d w es t u d yt h ec o r r e l a t i o n so f s c a l e - f r e en e t w o r k s t h ed e g r e ec o r r e l a t i o no ft h e b am o d e li sc o n s i d e r e de m p h a t i c a l l y w eg i v et h ej o i n td e g r e ed i s t r i b u t i o no ft h eb a n e t w o r k w eo b t a i nt h ef o l l o w i n gn e wr e s u l t s ( 1 ) w ec o n s t r u c tt h ef o u rm o d e l so f s c a l e - f r e en e t w o r k s ，t h e ya mt h em o d e l3 5 1 - 3 5 4 i nt h ec l m p t e r3 n e we d g e sb e t w e e ne x i s t i n gn o d e s ，t h er e w i r i n go rr e m o v a lo fe d g e sa r e i n c o r p o r a t e di nt h em o d e l3 5 1a n dm o d e l3 5 2 i np a r t i c u l a r ，w ei n t r o d u c ean e we v o l v - m gm e c h a n i b l nt h a ts o m eo l de d g e sa d e l e t e dw i t ht h ea n t i - p r e f e r e n t i a lp r o b a b i l i t yi n m o d e l3 5 2 u s i n gt h em e a n - f i e l da p p r o a c h ，t h ed e g r e ed i s t r i b u t i o n sp ( k ) o ft h et w o m o d e l sa x ec a l c u l a t e da n a l y t i c a f l y , a n dt h e ya r ea l lt h ep o w e r - l a wd i s t r i b u t i o n s i nt h em o d e l3 5 3a n dm o d e l3 5 4 ，w ep r o p o s ef i r s t l yt h el o g a r i t h m i cg r o w t hw h i c h i san e we v o l v i n gm e c h a n i s mo fn e t w o r k s i np a r t i c u l a r ，t h ed e g r e ed i s t r i b u t i o n so ft h e t w om o d e l sc a n tb ec a l c u l a t e da n a l y t i c a l l y u s i n gt h em a r k o vc h a i nm e t h o dw h i c hj 8 i n t r o d u c e df i r s t l yi nc h a p t e r4 ，t h ed e g r e ed i s t r i b u t i o n sa r ec a l c u l a t e dn u m e r i c a l l y , a n d t h en u m e r i c a lr e s u l t ss h o wt h a tt h e yh a v ep o w e r - l a wt a i l s ( 2 ) w ee x p l o r es c a l e - f r e en e t w o r k sb yt h ev i e w p o i n to fs t o c h a s t i cp r o c e s s e s w e e s t s b l l s hf i r s t l y8r e l a t i o nb e t w e e ns c ：自j e - f r e en e t w o r k sa n dm a r k o vc h a i n s w ed e m o n s t r a t e t h a tt h ed e g r e es e q u e n c e 甄( t ) ，t = i ，i + 1 ，) i san o n h o m o g e n e o u sm a r k o vc h a i n ，w h e r e 甄( t ) r e p r e s e n t st h ed e g r e eo fa # y e nn o d eia tt i m eti nt h eb am o d e l ，a n dg i v et h eo n e - s t e pt r a n s i t i o np r o b a b i l i t ym a t r i xp s ( t + 1 ) ， = 1 ，2 ，一 i v ( 3 ) b y t h e t h e o r y o f m a r k o v 蛐，t h e d e g r e e d i s t r i b u t i o n p ( k ，t ) o f t h e b a m o d e l a t t i m e t i s 西y e nb y t h e m a t r i x p i ( t + 1 ) s ；1 ，2 ，) n o t i n g t h a t t h e t r a n s i t i o n p r o b a b i l i t y m a t r i xp t ( t + 1 ) ( i = 1 ，2 ，) h a v eav e r ys i m p l es t r u c t u r e ，w ep r o p o s eal l e wa p p r o a c h t oc a l c u l a t en u m e r i c a l l yt h ed e g r e ed i s t r i b u t i o np 辑) ，i ti sn a m e da st h em a r k o vc h a i n m e t h o d w es u c c e s s f u l l ya p p l yt h i sm a r k o vc h a i nm e t h o dt oc a l c u l a t en u m e r i c a l l yt h ed e g r e e d i s t r i b u t i o n sp ( k ) f o rt h eb am o d e la n dt h r e em o d e l sw i t ht h ea c c e l e r a t i n gg r o w t h f o r t h eb am o d e l ，t h et h r e er e s u l t sf r o mt h en u m e r i c a lc o m p u t a t i o n ，a n a l y s i sa n dn u m e r i c a l s i m u l a t i o na r ev e r yc k _ s ei nf i g u r e4 1 i t h i ss h o w st h a tt h em a r k o vc h a 缸1m e t h o di s e f f i c i e n tf o rt h eb am o d e l t h ed e g r e ed i s t r i b u t k m sp ( ) o ft w om o d e l sf o rd i r e c t e do r u n d i r e c t e dn e t w o r k sw i t ht h el o g s w i t h m i cg r o w t ha r ec a l c u l a t e dn u m e r i c a l l y t h ei l u e 1 e r - i c a lr e s u l t ss h o wt h a te a c ho ft h et w od e g r e ed i s t r i b u t i o n sp ( 女) h a sap o w e r - l a wt a f ti n f i g u r e4 3 1a n df i g u r e4 4 1 a n dt h et w os y s t e m sm s e l f - o r g i z ei n t os c a l e - f r e en e t - w o r k s i np 础i e n l a r ，t h et w od e g r e ed i s t r i b u t i o n se ( k ) c a n tb ec a l c u l a t e da n a l y t i c a l l y ( 4 ) w ei n v e s t i g a t et h ec o r r e h t i o no fs c a l e - f r e en e t w o r k sa n dg i v et h ej o i n td e g r e e d i s t r i b u t i o n so ft h eb an e t w o r k b yt h er a t e - e q u a t i o na p p r o a c ha n dt h ep r o p e r t yo ft h e t w o - d i m e n s i o a n l g e n e r a t i n g f u n c t i o n ，t h e j o i n t d e g r e e d i s t r i b u t i o n p ( 女，j ) o f t w o c o l t l l e c t e d n o d e si nt h eb am o d e li sp r o v i d e d ，b yt h em e a n - f i e l da p p r o a c ha n dt h ep r o p e r t yo ft h e o r d e rs t a t i s t i c , t h ej o i n td e g r e ed i s t r i b u t i o np ( k l ，k 2 ) o fa n yt w on o d e si nt h eb am o d d i sg i v e n t h et w oj o i n td e g r e ed i s t r i b u t i o n si n d i c a t et h es p o n t a n e o u sa p p e a r a n c eo fn o d e d e g r e ec o r r e c t i o n si nt h eb an e t w o r k k e y w o r d s ：c o m p l e xn e t w o r k s ，r e a l - w o r l dn e t w o r k s ，r a n d o m 黟a p h s ，s m a j l - w o r l d n e t w o r k s ，s c a l e - f r e en e t w o r k s ，s t a t i s t i c a lp r o p e r t i e s ，t o p o l o g ys t r u c t u r e s ，d e g r e ed i s t r i b u - t i o n ，a v a g ep a t hl e n g t h ，c l u s t e r i n gc o e f f i c i e n t ，e v o l v i n gm e c h a n i s m s ，e v o l v i n gm o d e l s ， n u m e r i c a lc o m p u t a t i o n ，n o n h o m o g e n e o u sm a r k o vc h a i n s ，t r a n s i t i o np r o b a b i l i t ym b t r i x ， v a r i a t i o ne q u a t i o no ft w ov m - i a b l e s ，t w o - d i m e n s i o n a lg e n e r a t i n gf u n c t i o n ，o r d e rs t a t i s t i c ， c o r r e l a t i o n ，j o i n td e g r e ed i s t r i b u t i o n 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工 作除了文中特 j a j j n 以标注和致谢的地方外，论文中不包括其 他入已发表或撰写过的研究成果参与同一工作的其他同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意 第一章绪论 本博士学位论文研究复杂网络首先介绍复杂网络的研究背景和发展历程，其 次介绍复杂网络的研究现状与展望，最后阐明本论文的选题，研究成果和结构安排 1 1 复杂网络概述 网络是点和边组成的集合，其中点表示系统的元素，两点之间的连接边表示元 素之间的相互作用复杂网络描述从技术到生物直至社会的各种大规模复杂系统 近年来，复杂网络引起了国际科学界的广泛重视，已经成为统计物理学、数学， 计算机科学，系统科学、生命科学以及社会学等多个学科的研究热点，科学家们致 力于探索复杂网络的演化规律，结构功能和动力学行为f 1 0 ，5 4 ，1 3 6 ，1 6 7 1 一研究背景 复杂网络的发展是现实世界网络的客观要求事实上，在许多自然和人造系统 中都存在着大规模的复杂网络例如，在生态系统中，物种之间的相互关联可以描述 为复杂的食物链网络；在科技领域中，因特网和万维网是自组织网络的典型代表； 在我们的现代社会中，许多庞大的基础系统如能源网和航空运输网，都是不可缺少 的网络系统；具有活力的细胞也不例外，基因，蛋白质和其他分子之间的相互作用 形成了个复杂的网络，从而产生了细胞的组织和功能；社会系统也可以抽象成描 述个体问多种相互作用的网络以下几个网络是有较多研究的实际网络 万维两和因特网对我们的影响是不可估量的，它们已经是我们生活中不可缺少 的部分然而，直至几年前，我们对它们的结构特性、层次组织、局部特征以及 发生在这两个网络上的各种行为过程等等都知道的很少，而这方面的知识对万维网 和因特网的最有效运行是十分必要的，例如网络的安全性、运行效率以及提高网络 功能等都与网络的组织结构有关，参见【1 1 ，1 8 ，1 3 9 l 和，4 7 ，6 9 ，1 4 4 引文网络的结点就是学术论文，有向边表示一篇论文对另一篇论文的引用，这 是个相当复杂的信息网络，它包含了大量的学术信息f 1 5 2 ，1 7 3 1 生物网络的研究取得了很多成果的确，很多生物系统都可以被描述成网络例 如，新目舞代谢反应网络，其中结点表示基质( 分子化合物) ，连线( 边) 表示基质之间的 1 2第一章绪论 新陈代谢反应，一些学者对新陈代谢网络的拓扑结构进行了研究 9 0 ，1 7 9 】；基因功 能的个重要方面是蛋白质的相互作用，蛋白质被视为结点，有向边表示一对蛋白 质的相互作用，形成了蛋白质相互作用网络，它们的大型图已经被绘制【髂，船，1 7 1 】 生态学家通常用食物链网络来量化各个物种之间的相互作用，其中结点就是物 种，有向边表示捕食者与猎物之间的相互关系完全构建食物链网络的工作量是非 常大的，近年来已经取得相当广泛的数据集【1 2 1 ，1 8 3 ，1 6 4 ，1 9 1 】，一些学者对食物链 网络的拓扑结构进行了统计研究【如，6 4 ，9 5 】 社会网络是人或人的群体的集合，这些人之间具有某种接触或相互作用的模式 【1 5 7 ，1 8 5 例如，著名的小世界实验( n t 要求参与者把一封信传给他们熟悉的一 个人使这封信最后传到指定目标人，大约平均传过六个人之手，因此熟人网络的平 均路径长度仅为6 ，即所谓的六度分离概念目前，研究较多的社会网络是电影演员 合作网络f 9 ，1 5 】、科学家合作网络【2 0 ，1 2 9 ，1 3 0 ，1 3 l 】和电话网络【5 6 】等 大多数复杂网络的研究始于人们想要了懈各种实际网络的愿望研究网络最初 和最主要的原因之是为了了解疾病和其它事物( 如信息、计算机病毒和谣言等) 在网络上的传播机制研究复杂网络，对于防备黑客攻击、防治流行病、开发新药 以及提高复杂性计算速度等，都具有重要的实际意义 人们致力于揭示复杂网络的演化机制和结构功能为了表征网络结构和行为的 统计属性，人们引进了刻画网络结构的几个度量标准( 测度) i 度分布( d e g r e ed i s - t r i b u t i o n ) ，平均路径长度( a v e r a g ep a t hl e n g t h ) 和集群系数( c l u s t e r i n gc o e f f i c i e n t ) 网络的度分布e ( k ) 是随机选择的结点具有k 条连接边的概率度分布可以度 量随机网络的一些重要的结构特性在实证研究和模拟中以频率代替概率 网络中两个结点的距离定义为连接它们的最短路径的边数，平均路径长度是网 络中所有结点对的距离的平均值平均路径长度度量了网络的连通性 网络的集群系数定义为一个结点的两个邻居之间也是邻居的概率直观地，集 群系数是网络中三角形个数占连通三点组总个数的比倒集群系数度量了网络内在 的群聚倾向，集群系数的概念来源于社会网络中的小集团特征 现实世界中的复杂网络千差万别，表达的内容各不相同但是，大多数网络的 演化机制和拓扑结构却有着惊人的相同或相似人们对现实网络进行了大量的实证 研究f 1 0 ，5 4 ，1 3 6 ，1 6 7 ，研究发现大多数实际网络具有以下几个共同特征， ( 1 ) 复杂性，网络规模很大，包含数万个至数十万个结点，甚至万维网的网页 已达到数十亿，网络的图形结构非常复杂 2 0 0 5 上海大学博士学位论文3 ( 2 ) 动态性t 网络是一个动态的演化系统，通过点和边的增加和减少来进行演 化。并且网络会不断增长 ( 3 ) 随机性t 网络的演化过程具有明显的随机性，结点之间连接与否不是确定 性的，但也不是完全随机的 ( 4 ) 适应性- 在没有任何外部组织驱动下，网络可以自组织增长，具有适应性 ( 5 ) 小世界特征t 虽然网络的规模很大，但是任意两个结点之间有一条相当短 的路径，随着结点数的增加，网络的平均路径长度增加的非常缓慢( 对数地) ；而且 相对于随机图，实际网络的集群系数要大得多，网络具有明显的群聚特性 ( 6 ) 无标度特征，大多数实际网络的度分布具有幂律尾部，即p ( k 】一k - 1 幂 律分布是个重尾分布，它与随机图的度分布( 近似为泊松分布) 有本质区别正 是由于度分布的重尾特性，这种网络是一种非平衡网络，它与随机图完全不同这 种网络具有一些特殊的拓扑结构，例如t( a ) 网络中存在极少数具有大量连接边的 中枢点，( b ) 网络具有相关性，各个结点的度数是相关的 尽管各种网络具有明显的复杂性和随机性，但是研究人员总是试图用简洁的数 学和统计语言来描述复杂网络事实上，在简单规剐下自然界可以呈现复杂结构， 而在复杂背景下，自然界可以遵循简单定律为了探索实际网络的客观规律，人们 着重研究网络的几个基本问题。 ( 1 ) 网络是如何演化成我们所见到的形态? 是否存在普遍的演化机制? ( 2 ) 如何构建简单的演化模型来刻画实际网络? ( 3 ) 如何理解和分析阿络的结构性质与系统功能? 二发展历程 传统上，网络的研究属于图论和随机图论范畴很长时间以来，许多系统被考 虑成点和边随机分布的图，即数学上的随机图，例如分布式通讯系统 1 9 6 0 年，数学家e r d 5 s 和鼬n y i 【6 7 ，6 8 j 应用概率方法研究图论问题，建立了随 机图的数学理论，提出了著名的e r 模型给定个结点，每一对结点之间以概 率p 相互连接此后，在将近鲫年时间里，随机图一直是研究复杂网络的基本模 型他们在文章【6 7 ，6 8 】中深入研究了随机图的结构性质，最主要的数学成果是随 机图的相变现象随机图的主要结构特征为-( 1 ) 平均路径短，它的平均路径长度 l d 一1 ( ) 增长十分缓慢，反映了实际网络的短路径特征；( 2 ) 集群系数小，它 的集群系数口。讨一n - 1 随网络规模无限增大而趋于零，不能反映实际网络的群 4第一章绪论 聚特性；( 3 ) 度发布是轻尾部的，它的度发布为二项发布，近似为p o i s s o n 发布，与 实际网络度发布的重尾特征完全不一致事实上，由于随机图中点的连线是以等概 率随机生成的，因此各点的边数相差不大，没有连线特别多的点，随机图是一个平 衡网络特别指出，e r 模型是个静态网络，它总是先给定总点数总体上， 随机图不能很好地刻画实际网络 1 9 9 8 年，w a t t sa n ds t r o g a t z 在( ( n a t u r e ) ) 上发表了开创性论文【1 9 0 l ，提出了 小世界网络( s m a l l - w o r l dn e t w o r k s ) 概念过去，许多实际网络的拓扑结构被假定 为完全规则阿或完全随机网但是，许多生物网络、技术网络和社会网络却介于这 两种极端的网络之间w a t t sa n ds t r o g a t z 在文章 1 9 0 j 中探究能够直达这两种极端 网络中问地带的简单网络模型一通过重新连接规则网中结点之间的连线来增加该网 络的无规则性模拟结果表明这些网络能够像规则网那样具有高度的集群性，又像 随机网那样具有短的平均路径长度由于具有类似小世界现象，他们称这种网络为 小世界网络这个小世界网络模型被称为w s 模型 在生物系统，社会系统和人造系统中存在大量的小世界网络研究表明小世界 网络显示出能够增强信号的传播速度，提高计算能力和同步能力 8 4 ，1 2 7 ，1 8 2 ，1 9 0 特别地，传染性疾病在小世界网络中传播比在规则阿中要容易得多1 1 3 3 ，1 9 0 j 小世界网络同时具有平均路径长度短和集群系数高的特点，它们是不能从规 则网或随机网中产生但是，它的度分布是一个轻尾分布，其形态与p o i s s o n 分布 相似，小世界网络中不存在具有大量连接边的中枢点，因此它仍然是个平衡网络 5 1 ，1 4 0 近年来，研究人员对小世界网络的结构性质以及动力学行为进行了深入 的探索，取得了丰富的成果1 0 ，5 4 ，1 3 6 ，1 8 7 近十年来，随着数据库容量的持续增加以及计算机存储和操作能力的增强，使 得人们对大规模复杂网络的实证研究成为可能尤其是对于万维网和互联网的图形 化处理【1 1 ，1 7 ，1 8 ，6 9 】，为研究大规模复杂网络的拓扑结构提供了第一次机会逐 渐地，开展了用图论方法对许多实际网络的研究此时的研究开始用系统的眼光来 看待这些巨大的数据集合，试图寻找这些复杂系统的演化和动力学背后的规律和模 式因此，网络的研究方法发生了根本性的改变；从对含点数少的小型图以及图中 个体点或边的属性分析转变为对含大量点边的大规模图形的统计属性进行研究 1 9 9 9 年，a l b e r t ，j e o n ga n db a r a b d s i 1 1 1 发现w w w 网页的度分布不是想象中 的p o i s s o n 分布，而是一种具有重尾部特征的幂律分布，即度分布p ( k ) 一一，并且 发现w 、 n v 基本上是由少数含有大量超连接的网页串连起来的，绝大部分网页的 2 0 0 5 上海大学博士学位论文 5 连接数都很少，他( 她) 们把这个特性称为网络的无标度性质( s c a l e - f r e en a t u r e ) 与此同时，f a l o u t s o s 三兄弟也发现了i n t e r n e t 同样具有这种无标度特性【6 9 1 网络 的无标度梅性是复杂网络的一个重大发现，这是新的研究方法带来的突破 1 9 9 9 年，b a r a b d s ia n da l b e r t 在( & 把n c e ) ) 上发表了开创性论文f 1 5 1 ，提出了 无标度网络( s c a l e - f r e en e t w o r k s ) 的概念和演化模型 具有幂律度分布的网络被称为无标度网络如上所述，w w w 和i n t e r n e t 等许 多现实世界的大规模网络都是无标度网络但是，随机图和小世界网络都不能再现 幂律度分布b a r a b d s la n d 舭f 1 5 j 创造性地构建了无标度网络模型，成功的关键 在于观念的更新，网络被理解为动态的演化系统他( 她) 们考察了实际网络的 演化机制，发现增长( 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 ) 是实际网 络演化过程的两个基本要素于是，他( 她) 们1 15 】原刨性地提出了著名的无标度 网络模型一b a 模型 ( 1 ) 增长网络开始于少数几个点( m o 个) ，每个时间间隔( 步) ，增添一个新 点，新点与m ( sm o ) 个不同的已经存在于系统中的旧点相连接产生m 条新边 ( 2 ) 择优连接t 假设新点连接到旧点i 的概率i i 依赖于点l 的度数h ，即 厶， 蹶) = ；! -( 1 1 1 ) z i5 j 经过t 时间步，b a 模型演化成一个具有n = m o + t 个点和耐条边的随机网络 他们认为如果能够准确地捕获到实际网络的演化过程，那么就一定能够准确地 获得它们的拓扑结构事实上，正如他们所预测的那样，b a 模型生成的网络( 也 称为b a 网络) 具有实际网络中存在的各种结构特性和统计属性通过数值模拟和 理论分析【1 2 ，1 5 ，1 6 ，b a 网络具有以下几个特性t ( 1 ) b a 网络具有幂律度分布，是个无标度网络他们提出一种平均场方法， 以研究结点度数依时问t 变化的动态性质，进而得到了度分布的解析表达式t e ( k ) 2 m 。七一1 ，七m ，7 = 3( 1 1 2 ) 其中 称为度指数，这个结果得到数值模拟的验证因此，该系统自组织成一个平 稳的无标度状态b a 模型是第一个成功再现无标度特性的网络演化模型 ( 2 ) b a 网络具有短路径特征1 1 0 ，删，其平均路径长度l l n ( n ) l n l n ( n ) ( 3 ) b a 网络的集群系数偏小【1 0 1 ，模拟显示集群系数c 一卸7 5 ( 4 ) b a 网络存在中枢点与富者愈富现象，幂律度分布的重尾特征将导致无标 度网络存在少数具有大量连接边的中枢点，择优连接必然产生富者愈富现象 6第一章绪论 ( 5 ) b a 网络的鲁棒性与脆弱性f 1 2 l ，面对结点的随机失效，网络具有鲁棒性， 但是面对蓄意攻击中枢点时，系统变得十分脆弱，网络很容易陷于瘫痪 ( 6 ) b a 网络具有度相关，择优连接决定了边的增加依赖于网络的局部特性， 这种演化过程导致非平凡相关相依性决定了无标度网络的拓扑结构十分复杂 从此，复杂网络的研究进入了一个新时代随后的几年时间里，网络的理解和 刻画的研究工作非常活跃，无论在现实网络的实证研究范畴还是在建立模型和理论 分析方面，研究成果都是十分丰富的特别地，无标度网络的研究取得了很大的进 展，涌现了大量的学术论文，例如三篇著名的综述文章【l o ，5 4 ，1 3 6 1 及其所引用的 大量参考文献在此，我们只能作一些简要的介绍 b a 模型是可以生成无标度阿络的最简单模型相对于各种复杂的实际阿络， 它有着明显的局限性为了更好地刻画现实网络的主要特性，人们不断探索网络的 演化机理，建立符合实际网络的演化模型，研究无标度网络的结构和功能 ( 1 ) 演化机制 首先，增长是现实网络的主要特征之一，但是网络究竟以什么方式增长，实证 研究表明，不同网络可能遵循不同的增长模式例如，在因特网和万维网中，边的数 量比点的数量增长要快【3 5 ，6 9 】，这种加速增长对网络的拓扑结构会有什么影响? d o r o g o v t s e va n dm e n d e s 5 3 1 研究了加速增长对度分布的影响，引进了一个幂律 增长有向网络模型，系统在时刻t 产生e o f ( 0 0s1 ) 条有向边，理论分析表明这 种加速增长不会改变度分布的无标度特性，但度指数修正为7 = l4 - 南 我们在论文【1 6 0 】和【4 2 】中分别提出对数增长网络模型和对数增长有向网络模 型，网络总边数呈对数t a t 增长，这两个加速增长模型都可以演化成无标度网络 d o r o g o v t s e va n dm e n d e s 5 0 j 研究点具有有限寿命或有限边容量的增长制约 其次，择优连接也是现实网络的主要特征之一，但是连接概率n ( k ) 可能有多 种形式j e o n g 等【8 9 】和n e w m a n 12 8 】通过实际网络测定n ( k ) 的函数形式，支持了 择优连接假说的存在在一般情况下，n ( k ) 具有幂函数形式。 b 9 慨) = 音，a 0( 1 1 3 ) l i “1 在某些阿络中，如因特网和引文网络，幂指数o z 1 ，正是b a 模型的线性择优连 接在其它一些网络中，如神经科学科研合作网络，幂指数n * 0 84 - 0 1 1 时，称为超线性择优连接 k r a p i v s k y 等【1 0 8 】研究了非线性择优连接对网络拓扑结构的影响，理论分析表 明网络的无标度特性被非线性择优连接破坏了特别地，当a 2 时，产生。赢家 2 0 0 5 上海大学博士学位论文 7 通吃。现象，即几乎所有结点都有一条边连接到同一个。凝胶”点网络出现无标 度状态的唯情况是渐近线性择优连接，即当臃一o 。时，仇) 一 第三，人们还提出了一些更加复杂的网络演化机理例如，结点的初始吸引力 和适应力，结点的寿命和连线成本，连线的删除，旧点之间产生连线，复制机制和 层次组织结构等等，它们可能更加贴近某些实际网络 ( 2 ) 构建模型 首先，关于度指数建型b a 网络的度指数为常数3 ，但是实际网络的度指数 不是完全一样的，大多数现实网络的度指数分布在1 到4 之间。那么，如何构造度 指数可随参数变化的无标度网络模型? a l b e r ta n db a r a b a s i 9 】研究了个可调度指数的无标度网络模型，该模型体现 了网络的局部相互作用，即内部边和重新连接 我们在文章【4 1 】中也构建了两个可调度指数的无标度网络模型，提出了一种以 反择优概率删除连线的演化机制 其次，关于集群系数建模高集群是一些现实网络的主要特征之一，而b a 网络 的集群系数随网络规模不断增长而趋于零，明显偏小因此，构建具有高集群的无标 度网络模型显得十分重要。这方面的研究取得了二些进展，例如文献f 8 2 ，1 0 1 ，1 0 2 1 h o l m ea n dk i m s 2 】构建了个可以生成具有高集群的无标度网络模型，该模型保留 了增长和择优连接，增加了个。三元组。的形成机理，使网络中的三角形大量增 加，这种网络必然具有高集群特性 第三，人们还研究了加权网络和层次网络许多实际网络都是加权的，例如i n t e r - n e t 有带宽，细胞网络有反应速率，决定这些权重的演化机制是什么? n e w m a n 1 2 9 ， 1 3 0 着重研究了社会加权网络r a v a s za n db a r a b 如i 等1 1 5 0 ，1 5 1 】构建了具有层次 组织的无标度网络模型 ( 3 ) 动力学过程 许多网络提供了动力学过程的基础，并且拓扑结构对其系统的动力学特性至关 重要可能的动力学过程非常广泛w a t t s 1 8 7 】研究了集群对一些过程的影响，包 括博弈、合作，元胞自动机和同步h o n g 等f 8 4 j 研究了小世界网络的同步现象 汪小帆教授和陈关荣教授【1 8 1 ，1 8 2 】研究了小世界动力网络和无标度动力阿络 的同步问题，探索了非平衡的无标度拓扑结构对动力网络同步的影响 网络结构在决定信息传播和病毒扩散时起着至关重要的作用，研究人员在几 种类型的网络上都对这个问题进行了研究，取得了许多成果，例如小世界网络的 8第一章绪论 f 1 2 6 ，1 4 0 ，1 4 2 ，1 9 叫等，以及无标度网络的f 1 2 ，1 6 9 ，17 0 】等特别地，p a s t o r - s a t o r r a s a n dv e s p i g n a n i 【1 4 5 ，1 4 6 1 研究了网络拓扑对疾病传播的影响，发现在随机图上，只 有当扩散率大于某个临界值时，局域的感染才会扩散到整个网络；但是对于无标度 网络，任意的扩散速率都会导致整个网络的感染，也就是说无标度网络的临界扩散 速率减到了0 ，这是一个非常意想不到的结果 三研究现状 在过去的短短几年内，无论在理论分析还是实际应用上，复杂网络的研究都取 得了惊人的进展当前，复杂网络的研究如火如荼实际上，网络已成为多个学科 的研究热点，甚至成为一种研究方法，各个学科的专家都开始用网络描述各种复杂 系统并加以研究人们着重围绕以下几个方面开展网络的研究工作t ( 1 ) 实证研究 现实世界网络的实证研究不仅是客观需要，而且也是复杂网络理论的思想源 泉复杂网络的理论研究很大程度上得益于实际网络的经验研究的推动事实上， 新发现。新观点和新方法的产生往往来源于实际网络属性的观察 计算机存储和运算能力的增强，为大规模网络的实证研究提供了必要条件目 前，已经建立了许多大规模现实网络的数据库实证研究采用的数据库跨越若干个 不同领域，研究相当活跃的领域在于各种生物系统和社会系统 ( 2 ) 演化机制与构建模型 到目前为止，我们还缺乏能够刻画网络结构一致性和普适性的简单组织原则 通过观察实际网络的演化过程，人们发现了网络的各种演化机理，从而构建了符合 现实网络的多种演化模型 研究人员开发了一些更为精妙的网络模型。这些模型比w s 模型和b a 模型更 能反映实际网络的真实情况网络模型既可以帮助我们理解网络的结构特征，也可 以作为研究发生在网络上的过程行为的基础 ( 3 ) 结构特性与网络功能 目前，人们试图开发新的刻画网络结构的测度，寻找新的表征网络结构和行为 的统计属性研究人员提出了介数和模体等新的网络测度概念，取得了一些进展 研究网络结构的最终目的是为了理解和解释构建于网络之上的系统运作方式 人们正在研究发生在网络上的各种过程行为，例如渗流过程 1 4 2 】网络弹性【3 9 ， 4 6 】，传染过程【1 4 5 ，1 4 6 1 、网络搜索 3 】网络导航【9 7 ，9 翻和网络相变【1 7 8 1 等 2 0 0 5 上海大学博士学位论文 9 ( 4 ) 数学方法与理论分析 复杂网络的理论研究仍处于