（运筹学与控制论专业论文）可导航网络模型的研究.pdf

2 0 0 8 年、 ：海人学硕上学位论文 摘要 近些年来，复杂网络研究方兴未艾，已成为个跨学科的领域，覆盖范围包 括了数学、计算机科学、社会科学和生物科学等。在这个领域中，近来大量的工 作主要集中在复杂网络模型的发展上。这些复杂网络模型，能抓住现实网络中观 察到的数据的一些定性的性质，并且可以帮助我们大致地推测出现实网络的组织 方式。复杂网络具有三种重要的结构特性：小世界性、s c a l e f r e e 性和可导航性。 反映这些性质的经典模型分别是：w a t t s s t r o g a t z 模型、b a r a b 瓠i a l b e r t 模型和 k l e i n b e r g 模型。 本文从现实社会中的小世界现象出发，以网络的可导航性为视角展开对复杂 网络的研究，内容涉及可导航网络的形成以及分散搜索算法等。 第一章，简要介绍了可导航网络的基本内容和研究背景，描述了一个著名的 实验，该实验给出了社会网络“六度分隔 现象的首个实证性根据。第二章，讨 论了由该实验产生的可导航网络模型，描述了经典的网络模型及其所引发的新颖 的算法问题和图论问题。第三章，深入研究了网络可导航性的要素，并提出一个 可导航的网络模型。第四章，从理论推理和分散搜索算法方面进一步研究新的增 长的可导航网络模型。第五章，对本文所做工作进行了概括，并对下一步的研究 指明了方向。 本文主要做了三方面的工作：第一，通过对网络可导航性的研究，在经典网 络模型的基础上提出了一个新的增长的可导航网络模型，这个模型同时具有三种 重要特征；并且在这个网络模型上使用贪婪算法时，它与k l e i n b e r g 模型具有相 同的导航效果，有时甚至更加优越。第二，通过计算机模拟和理论推导证明我们 所提出的新的网络模型是可导航的s c a l e f r e e 网络。第三，对各种分散搜索算法 进行比较后得出，对于不同的网络拓扑结构分别有相应匹配的分散搜索算法，相 对于最大结点度算法，增长的可导航网络模型更适合贪婪算法。 总之，本文成功建立了一个增长的可导航网络模型。然而，将其应用于通讯 和信息产业还有很长的路要走。 关键词：复杂网络：小世界性；s c a l e f r e e 性；可导航性；分散搜索算法 v i 2 0 0 8 年上海大学硕士学位论文 a b s t r a c t t h es t u d yo fc o m p l e xn e t w o r k sh a se m e r g e do v e rt h ep a s ts e v e r a ly e a r s 硒a t h e m es p a n n i n gm a n yd i s c i p l i n e s ，r a n g i n gf r o mm a t h e m a t i c sa n dc o m p u t e rs c i e n c et o t h es o c i a la n db i o l o g i c a ls c i e n c e s as i g n i f i c a n ta m o u n to fr e c e n tw o r ki nt h i sa r e ah a s f o c u s e do nt h ed e v e l o p m e n to fc o m p l e xn e t w o r km o d e l st h a tc a p t u r es o m eo ft h e q u a l i t a t i v ep r o p e r t i e so b s e r v e di nl a r g e s c a l en e t w o r kd a t a ，s u c hm o d e l sh a v et h e p o t e n t i a lt oh e l pu sr e a s o n ，a tag e n e r a ll e v e l ，a b o u tt h ew a y si nw h i c hr e a l w o r l d n e t w o r k sa l eo r g a n i z e d t h e r ea l et h r e ei m p o r t a n ts t r u c t u r a lf e a t u r e si nc o m p l e x n e t w o r k s ：s m a l l w o r l de f f e c t ，s c a l e - f r e ep r o p e r t ya n dn e t w o r k sn a v i g a b i l i t y t y p i c a l m o d e l sm i r r o r e ds u c ht h r e ef e a t u r e s ，r e s p e c t i v e l y , a l et h ew a r s - s t r o g a t z sm o d e l ，t h e b a r a b a s i a l b e r t sm o d e la n dt h ek l e i n b e r g sm o d e l b e g i n n i n gw i t ht h es m a l l - w o r l dp h e n o m e n ai ns o c i a ln e t w o r k ，w es u r v e y e do n e p a r t i c u l a rl i n eo fn e t w o r kr e s e a r c hn a v i g a t i n gn e t w o r k s ，c o n c e m e dw i t ht o p o l o g y s t r u c t u r eo ft h en a v i g a t i n gn e t w o r k sa n dd e c e n t r a l i z e ds e a r c ha l g o r i t h m s ，w h i c h i l l u s t r a t e st h i ss t y l eo fa n a l y s i s i nt h ef i r s tc h a p t e r ，t h eb a s i cc o n c e p t sa n dt h eb a c k g r o u n do fn a v i g a t i n g n e t w o r k s w e r ei n t r o d u c e d ，a n daw e l l k n o w ne x p e r i m e n tw a sd e s c r i b e dt h a tp r o v i d e d t h ef i r s te m p i r i c a lb a s i sf o rt h e s i xd e g r e e so fs e p a r a t i o n ”p h e n o m e n o ni ns o c i a l n e t w o r k s i nt h es e c o n dc h a p t e r ，t h en a v i g a t i n gn e t w o r km o d e l sw e r ed i s c u s s e d ，a n d s o m ec l a s s i c a lm o d e l sa n dt h e i rn o v e la l g o r i t h m i ca n dg r a p h - t h e o r e t i cq u e s t i o n sw e r e p r e s e n t e d i nt h et h i r dc h a p t e r , t h ee s s e n t i a l so ft h en a v i g a t i n gn e t w o r k sw e r ed e e p l y s t u d i e d ，a n dv e r yi m p o r t a n t l y , an e wn a v i g a t i n gn e t w o r km o d e lw a sp r o p o s e d i nt h e f o u r t hc h a p t e r , t h en e w g r o w i n ga n dn a v i g a b l en e t w o r k sm o d e lw e r ei n v e s t i g a t e d ，i n t h ev i e wo fm a t h e m a t i c a la n a l y s e sa n dd e c e n t r a l i z e ds e a r c ha l g o r i t h m s i nt h e c o n c l u s i o ns e c t i o n ，w es u m m a r i z e da l lt h ew o r kw eh a v ed o n ei nt h i sp a p e ra n dg a v e t h ef u r t h e rd i r e c t i o n so ft h er e s e a r c h i nt h i st h e s i s ，t h r e em a i nr e s u l t sa b o u tc o m p l e xn e t w o r k sm o d e lw e r er e p o r t e d f i r s t ，o nt h eb a s e so ft h et y p i c a lm o d e l s ，b yi n v e s t i g a t i n gt h en a v i g a b l en e t w o r k s ，a n e wg r o w i n ga n dn a v i g a b l en e t w o r k sm o d e lw e r ed e v e l o p e d ，w h i c hp o s s e s s e dt h e v i i t h r e ei m p o r t a n ts t r u c t u r a lf e a t u r e ss i m u l t a n e o u s l y ；t h er e s u l t so fn a v i g a t i o no b t a i n e d b yag r e e d ya l g o r i t h mo nn e t w o r k so ft h em o d e l w e r es i m i l a rt o ，o re v e ns u p e r i o rt o t h eo n e so ft h ek l e i n b e r g sm o d e l s e c o n d ，u s i n gc o m p u t e rs i m u l a t e sa n dm a t h e m a t i c a n a l y s e s ，t h en e w m o d e lw a sp r o v e dt ob eas c a l e - f r e ea n dn a v i g a b l en e t w o r k t h i r d ， t h e r eh a v eb e e np r o p e rd e c e n t r a l i z e ds e a r c ha l g o r i t h m sf o rv a r i o u sn e t w o r kt o p o l o g y s t r u c t u r e s ；a n di tw a st h eg r e e d ya l g o r i t h m sf i tt h en e wm o d e lb e t t e rt h a nt h em a x d e g r e ea l g o r i t h m s t h ec o n c l u s i o ns u g g e s t e dt h a tt h en e wm o d e lw a sg r o w i n ga n dn a v i g a t i n g ， h o w e v e r , m a n ys t u d i e ss h o u l db ed o n ei no r d e rt oa p p l yi ti nt h ec o m m u n i c a t i o na n d j n f o r m a t i o ni n d u s t r i a l s k e y w o r d s ：c o m p l e xn e t w o r k ；s m a l l w o r l de f f e c t ；s c a l e f r e ep r o p e r t y ；n e t w o r k s n a v i g a b i l i t y ；d e c e n t r a l i z e d r e s e a r c ha l g o r i t h m 2 0 0 8 年l 海大学硕十学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：拉函蝎日期：婴垦：了 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 1 1 1 日期；竺窭笸：2 2 0 0 8 年上海大学硕上学位论文 第一章绪论 近年来，复杂网络已经成为横跨社会科学、自然科学、生命科学和工程科学 等领域的重要研究课题，其在实证方面的研究主要是大规模现实网络，如万维网、 因特网、社会网、生物网等等【1 , 2 , 3 , 4 】的各种拓扑性质。目前，因特网、万维网、 各种通讯网以及信息技术产业正在迅猛发展，因此，快速高效地收集、整理和传 递信息已成为人们不断增长的需求，这里便涉及到复杂网络研究中的一个重要课 题网络的可导航性。 1 1 小世界现象 研究可导航网络不得不提及的就是小世界现象。小世界现象形象地概括了这 样个有趣的概念：“你和地球上任何一个人之间最多只被六个人分隔开来”。几 乎每个人都会有这样的经历：在一次聚会或者某个公共场所遇到一个完全陌生的 人，经过短暂的交流之后会出乎意料地发现彼此认识同一个人，而后一阿惊呼： “这世界可真小! ”小世界现象正是对这种经历的概括，即使两个人之间没有共同 的朋友，他们也可以通过朋友的朋友建立起联系。虽然小世界现象很早以前就为 人们所认识，但相关的理论研究还是从2 0 世纪6 0 年代才开始。p o o l 和k o e h e n p j 运用数学的方法表述了这个问题，并进行了初步的数学分析。他们在小世界现象 的研究上取得了实质性的进展：估计了人们认识的熟人的平均数和任意两个社会 成员之间有由一个或两个中间人所组成的“相识关系链”的概率。他们推测：结构 化程度很高的人群中相识关系链长度的平均值和完全无组织人群中相识关系链 长度的平均值几乎是一样的。 到2 0 世纪6 0 年代后期，小世界现象成为人们进行实验研究的热门问题。在 p o o l 和k o c h e n 提出理论思想的同时，心理学家m i l g r a m 第一次对小世界现象进 行了实验研究。虽然m i l g r a m 成名于他的关于“人们的道德价值明显屈从于权力” 的研究6 1 ，但他之前进行的关于小世界假说的创新性实验【7 1 早已闻名于世。在这 个实验中，m i l g r a m 给内布拉斯加州和堪萨斯州的那些同意参加实验的“起始寄 2 0 0 8 年上海大学硕士学位论文 件人”寄去了大量的包裹，并要求他们将包裹寄给马萨诸塞州的两个指定“目标收 件人”中的一个。m i l g r a m 提供了目标收件人的大概位置和职业，只允许寄件人 将包裹直接寄给他知道名字的人，目标是通过尽可能短的熟人链使得目标收件人 收到这些包裹。因此，在这条链中的每个环节都要求寄件人能够努力地思考他们 认识的人中谁最可能认识，或者至少是更为“接近”目标人从地理位置上、个 人关系以及职业上进行判断。同时，每个环节的参与者都在包裹中记录自身的详 细资料，这使得实验设计者可以追踪包裹的传递情况并得到传递链的人口统计学 性质。 实验结果是：跨越宽广的地理和社会环境而收到这样封信仅仅需要5 个中 间人。这个数字究竟太高还是太低仍然是一件有争议的事。一方面，在任何一个 环节中，寄信人不太可能都选择出最佳的下一个参与者并把信寄给此人，这就使 得所传递的路线比最佳路线更长。另一方面，由于部分参与者不感兴趣，很多链 都没能完成，并且，由于长链比短链更可能终止，所以结果更偏向于较低的数字。 w h i t e t 8 】提出了一个模型来解释这一结果，得到了一个修正估计值约为7 个 中间人。无论如何，m i l g r a m 实验得到的这个数字与美国人1 3 ( 1 9 6 7 年美国人1 3 约为2 亿) 的数量级相比都不算大。m i l g r a m t 9 】使用相同的方法研究了洛杉矶的 白人和纽约的黑白混血人种之间的相识关系链的长度，并且得到了类似的统计数 字。自此，“六度分隔”便扬名天下，激起了人们对小世界网络的研究热情。 此后，小世界现象的研究远远超出社会学和心理学范畴，并遍及其他各个领 域。例如，生物领域里的神经网络、食物链、生态系统等；技术领域里的因特网、 万维网、通讯网络等。近些年来，研究人员主要通过对复杂网络的研究来解释小 世界现象。 1 2 复杂网络 复杂网络是由结点和连线构成的集合，是对现实世界各种系统中普遍存在的 网状结构的一种数学抽象。网络结点表示构成系统的元素，两个结点之间的连线 表示元素之间的相互作用。人们通常把各种具有复杂结构与功能的大规模网络统 称为复杂网络。复杂网络研究的一项重要的工作就是在对现实网络的拓扑性质进 2 2 0 0 8 年 ：海大学硕上学位论文 行研究的前提下，构造出相应的网络模型，并再现现实网络中观察到的性质。近 些年来，复杂网络引起了国际学界的普遍关注，已成为数学、统计物理学、计算 机科学、系统科学、生物科学以及社会学等多个学科的研究热点【i , 3 , 1 0 , 1 1 】。 复杂网络最初以图论的形式展开研究。e u l e r 在1 7 3 5 年解决了著名的“七桥 问题”，这是图论中的第一个严格证明。到2 0 世纪5 0 年代，图论研究已经成为 数学的一个重要分支。 匈牙利数学家e r d 6 s 和r 6 n y i 1 2 , 1 3 1 首先引进了随机图的严格定义并对其展开 了系统的研究。此后，随机图理论成为对无明确设计原理的大规模网络进行建模 的基本工具。随机图理论能够很好地解释一部分现实网络的结构及功能，例如复 杂网络逾渗问题。 2 0 世纪5 0 年代后，随着混沌、分形和非平衡态物理等新兴学科的创立及迅 速发展，人们对现实世界的理论认识达到了全新的广度和深度；更为重要的是， 由于计算机技术的飞速发展和计算能力的提高，使得对大规模网络数据的采集和 分析成为可能，为2 0 世纪9 0 年代末复杂网络研究的突破性进展提供了强有力的 工具。基于计算机仿真和大规模实际网络数据库的支持，大量的实证研究 2 , 3 1 发 现：绝大部分的实际网络( 如因特网和万维网) 都具有时间演化行为和一定的自 组织机制，不能仅仅依靠纯粹的随机性来构造，是一种介于有序与无序之间的中 间模式。但在当时的条件下，可以分析处理的只有两类网络：一种是完全有序的 网络，例如一个d 维规则网络；另一种是完全无序的随机网络。直到1 9 9 8 年 w a t t s 和s t r o g a t z 提出小世界( s m a l l w o r l d ) 网络模型 1 4 1 与19 9 9 年b a r a b 戤i 和 a l b e r t 提出无标度( s c a l e f r e e ) 网络模型【1 5 】，这两种模型与随机图模型相比，较 好地解释了一些实际网络的自组织形成机制，如因特网和科学家合作网的自组织 形成机制，且模拟结果和实际数据比较吻合。下面我们简要描述这三个模型： e r 随机网络：1 9 6 0 年前后，e r d o s 和r 6 n y i 应用概率论方法研究图论问题， 提出了e r 随机图模型【1 2 1 3 1 。 e r d 6 s 和r 6 n y i 将随机图定义为：具有个结点，n 条连线的图，这疗条连 线是从n ( n 一1 ) 2 条连线中随机选取的，这样的图一共有( - 1 ) ，：种，其中每一 2 0 0 8 年上海大学硕士学位论文 种图出现的概率都是相同的，这些图构成了一个概率空间。这种随机图记为 g ( n ，玎) 。 随机图的另一种定义：给定个结点，每对结点之间以概率p 连接，总连 线数刀是一个随机变量，期望值为e ( 甩) = p n ( n - i ) 1 2 。设g o 是一个有个结点 以条连线的图，则g o 出现的概率为：p ( g o ) = ( 1 一p ) 厂，这种随机图记为 g ( n ，? ) 。 小世界网络：1 9 9 8 年，w a t t s 和s t r o g a t z 提出y d , 世界( s m a l l w o r l dn e t w o r k ) 模型( w s 模型) 【1 4 】，它的生成规则是： 1 网络初始化：从具有个结点的环形网络开始，其中每一结点都与两边的 k 个邻近结点相连。 2 网络随机化：网络的每条连线以概率p 随机重连，同时保证结点没有自连 线和重复连线。这一过程产生了p n k 2 条随机连线。随着p 的改变，网络会在 规则网络( p = 0 时) 和随机图( p = l 时) 之间变化。 无标度网络：1 9 9 9 年，a l b e r t ，j e o n g 和b a r a b f i s i 发现因特网的度分布不是 p o i s s o n 分布，而是具有重尾特征的幂率分布，这个特性称为无标度性( s c a l e f r e e p r o p e r t y ) 。同年，b a r a b f i s i 和a l b e r t 提出了b a 模型【1 5 】： 1 增长机制：开始于较少的结点数量o ，在每个时间间隔增加一个具有 m ( m n o ) 条连线的新结点n ，与m 个已存在于网络中的旧结点相连。 2 择优机制：假设新结点n 连接到旧结点f 的概率正比于结点f 的度数包，即 q 刮2 轰。 经过，个时间间隔，b a 模型演化成具有n = m 0 + r 个结点和m t 条连线的网 络。 1 3 网络的可导航性研究 w a t t s 和s t r o g a t z 提出的小世界模型，在模拟具有短直径的实际网络的动力 学特征方面取得了很大的进步，促进了心理学、社会学以及物理学等领域的实际 4 2 0 0 8 年上海大学硕士学位论文 网络的研究这些实际网络都可以用诸如w s 的小世界模型来模拟。然而，值 得注意的是这些模型具有的性质与m i l g r a m 的实验发现的社会网络的特性之间 还存在着巨大差距。 1 3 1国内外研究近况 2 0 0 0 年k l e i n b e r g 通过对m i l g r a m 六度分隔”实验的进一步研究，获得了两 个重要的结论：第一，社会网络中人与人之间存在短路径；第二，人们可以通过 少许信息找到这条短路径。第一个结论是客观存在的，是绝大多数复杂网络具有 的特性。第二个结论是算法方面的：人们只需利用少许信息通过熟人就可以找到 一条到达目标人的短路径。虽然w s 模型能够说明第一个结论，即网络中几乎任 意两个结点之间存在短路径，但却不能找到这条短路径。m i l g r a m 的实验表明了 社会网络具有可导航线索，可以通过局部信息快速地找到一条从起始结点到目标 结点的短路径。自然地，人们会进一步思考社会网络必须具备怎样的特性才能实 现网络可导航性。 k l e i n b e r g 提出了一个可导航网络模型【1 6 1 。与w s 模型相似，可导航网络模 型首先设定在一个标准网格中，然后增加网格结点间的长程连边，网络中两个结 点由一条长程连边连接的概率与它们的网格距离有关，即两个非邻接点x 与y 之 间存在长程连边的概率为 p ( w ) ：竽华 口 其中d ( x ，y ) 为结点x 与y 的网格距离，口为正规化因子，口为参数。k l e i n b e r g 指出只有当口等于网格维数时，网络才具有可导航性。 k l e i n b e r g 从一个新颖的角度来考察小世界现象，开创了复杂网络的另外一 个重要方向网络可导航性研究。迄今为止这项研究开展了七、八年的时间， 但仍处于初级阶段，网络可导航性研究主要集中在两个方面：可导航网络模型的 构造和分散式搜索算法的研究。 在可导航网络模型构造方面，早期比较经典的是k l e i n b e r 9 1 1 7 】和w a t t s ，d o d d s ， n e w m a n 1 8 1 提出的集合系统和分层网络。在此基础上，近来的研究提出了更为复 2 0 0 8 年上海大学硕士学位论文 杂的网络结构，并且把它们作为构造可导航网络的“框架”。f r a i g n i a u d i l 9 l 对“通过 任意的图g 构造出一个网络，能通过贪婪算法达到可导航的效果”的观点提出了 质疑。d u c h o n 等人【2 0 】通过满足某个“有限增长”性质的图否定了上述的观点。 s l i v k i n s 2 1 l 考察了另一种网络框架，将结点置于一个基本的测度空间，同样得出 了否定的结论。a d a m i c 等人【2 2 1 把结点连通度信息运用到可导航网络研究中，提 出了一个具有丰富的高度数结点的模型。分散式搜索算法只能利用结点度信息， 得不到网络上的其他信息，通过模拟发现：对某些模型而言，掌握结点度信息就 可以提高搜索效率。s i m s e k 和j e n s e n 2 3 】建立了一个空间信息和结点度信息相结 合的模型，该模型具有网络可导航性。 对于分散式搜索算法，我们通过一个文件共享系统的实例来说明提出搜索算 法时遇到的困难：在文件共享系统中，每一个用户在各自的计算机中拥有某些文 件，但是没有一个单独的地方存放一份所有文件的清单，那么如果某人要查询一 些文件，如何有效地确定哪位用户拥有他所要的文件呢? 由于缺少了一个中央索 引，用户就处在了一个与m i l g r a m 实验极其相似的集合系统中，用户必须向其邻 接的用户提出询问，把这些邻接的用户看作网络的一个子集，再由这个子集中的 用户向他们的某些邻接点提出询问，依此类推。为了解决分散式搜索的问题，人 们做了许多尝试，比如通过网络协议明确地建立起网络，使得有效的分散式搜索 成为可能。相关的研究包括a s p n e s 和s h a h 2 4 1 、l u a 等人【2 5 】对搜索算法所做的总 结和回顾，h o n g 2 酣，z h a n g 等人( 2 7 1 ，m a l k h i 等人【2 8 j ，以及m a n k u 等人【2 9 1 对于分 散搜索算法和小世界网络的关系进行的更多讨论。m e n c z e r 3 0 】利用k l e i n b e r g 所描 述的分层模型，考察了大规模网络的网页链接模式。此外，还有一些是对携带少 量附加信息的分散式搜索算法所做的研究【3 1 3 引。 在第三章和第四章中，我们将分别对可导航网络模型的构造和分散式搜索算 法的研究系统地进行介绍和分析。 1 3 2 可导航网络研究的重要性 网络可导航性的发现具有偶然性。首先，网络的可导航性研究更像是为了数 学上好奇心的满足，当时m i l g r a r n 并不是研究人与人之间短路径的搜索问题，他 6 2 0 0 8 年，i ：海人学硕士学位论文 所感兴趣的是社会网络的小世界现象世界上的任何两个人之间是否足够 近? 同样地，在许多应用领域，例如疾病传播网中存在短路径是非常重要的事实， 而对于怎样找到这条短路径的研究却不多。其次，以往得出的网络具有短路径的 结论是建立在网络中的结点完全了解整个网络的基本结构3 6 , 3 7 】的基础上的，然 而m i l g r a m 的实验要求参与者根据自己的经验和掌握的信息来选择传递者，参与 者并不知道整个网络的结构，这才是短路径搜索问题的真正前提。 实际上，可导航网络的应用非常广泛。近些年来，因特网、万维网成为我们 生活的一部分，网络搜索引擎、网络导航在通讯网络、因特网中起的作用越来越 大。这些网络中的结点具有更多的不确定性和未知性。随着网络规模的扩大，比 如因特网有数以亿计的网民，要求网络中结点了解网络的全局结构简直是天方夜 谭。然而我们不仅要了解某两个结点之间是否能够通过短路径来传递信息，更重 要的是搜索到这条短路径。从这个意义上说，网络可导航性研究是势在必行且迫 在眉睫的。 1 4 本文研究的问题及成果 可导航网络的研究刚刚起步，我们选择非常基础且具体方面可导航网络 模型来进行研究。我们首先构造出可导航网络模型，其次对模型的可导航性进行 证明，然后阐明适合于该模型的分散搜索算法等。 本文具体对可导航网络模型作了以下三个方面的工作： ( 1 ) 在经典网络模型的基础上提出了一个新的增长的可导航网络模型 引力模型，这个模型同时具有三种重要的网络特性：小世界性、s c a l e - f r e e 性、 可导航性，并且在这个网络模型上使用分散搜索算法进行搜索，发现模型与 k l e i n b e r g 模型具有相同的导航效果，有时甚至更加优越。 ( 2 ) 对模型进行计算机仿真模拟，并从理论上证明引力模型是可导航的。 ( 3 ) 通过对多种分散搜索算法的分析与比较，我们找到更适合于引力模型 的搜索算法。 7 2 0 0 8 年上海人学硕士学位论文 1 4 1 增长的可导航网络模型 本节简要介绍第三章的工作。鉴于w s 模型主要反映小世界性，b a 模型主 要反映s c a l e f r e e 性和k l e i n b e r g 模型主要反映可导航性，它们并不都同时具备这 三种特性。我们所提出的引力模型，能够全面地反映现实网络的三个重要性质： 小世界性、s c a l e 。f r e e 性和可导航性。实现小世界性比较容易，只要如k l e i n b e r g 模型那样做些许修改。s c a l e f r e e 性敏感地依赖参数，的选取，通过模拟发现只有 当，= 】时才能具备s c a l e f r e e 性，这与采用度择优有关，而非线性度择优将破坏 s c a l e f r e e 特性【3 8 1 ，可以采用秩次( r a n k i n g ) 择优【3 9 】来替代度择优，这样可以达 到更佳的效果。关于可导航性，根据模型所具有的局部信息的特征( 既有坐标又 有结点度) ，我们利用结点坐标信息并使用贪婪算法，发现信息在十步左右就可 以到达目标结点。因此，引力模型是一个可导航的同时具备小世界性和s c a l e f r e e 性的网络模型，与现实的情况更加贴近。并且当网络增长到n x 以个结点时，新模 型包括了：( 1 ) 口= 0 ，厂= 0 时为w s ( 修正的n w ) 小世界网络，以小概率增加长 程连边时具有小世界效应；( 2 ) 口= 2 ，= 0 时为k l e i n b e r g 可导航网络。 1 4 2 理论证明与算法研究 这是本文第四章的主要工作。利用不等式方程等方法对模型的可导航性进行 了证明，并通过编写网络生成程序和各种分散搜索算法的程序对模型进行计算机 仿真模拟，考察了引力模型的度分布以及平均最短路径，对结果进行验证和分析。 虽然我们的模型也可以使用最大结点度搜索算法，但是使用贪婪算法的结果会更 加优越。 8 2 0 0 8 年上海人学硕士学位论文 第二章可导航网络 2 1 可导航网络的概念 所谓网络可导航性，是指在复杂网络中几乎任意两个结点之间不仅存在着连 通的短路径，且结点可以根据局部的网络信息，搜索到这样一条短路径。需要指 出的是，网络可导航性研究关注的不是短路径的存在性问题，而是如何找到这条 短路径的问题，这与人们的现实需求是一致的。可导航网络是指利用分散搜索算 法对网络中任意两结点之间的路径进行搜索时，具有可导航性的网络。 关于可导航网络，我们首先要明确几个基本的概念。所谓结点短路径是指长 度是网络规模n 的对数或更一般情况是即的对数多项式的路径。l o g ，? 的多项式 函数将作为本文中短路径确认的“黄金标准”。同时我们将保持“短路径”术语的非 正规性，粗略地认为当结点对之间的路径长度是l o g ，玎的多项式函数时，这条路 径是短的。所谓小世界网络是指几乎所有的结点对的路径是“短路径”的网络。在 这种情况下，路径的长度远远小于网络规模，2 ，是，z 的对数。所谓局部信息是指 网络中的结点仅仅知道很小邻域内结点的信息，即只知道网络的局部结构和信 息，对于网络全局结构无从知晓。 就路径搜索算法而言，以往寻找结点之间短路径的搜索算法都是在了解网络 全局信息的前提下进行的，这些算法称为全局搜索算法，主要有广度优先搜索、 深度优先搜索【4 0 】等。然而，实际网络中的信息获取是不对称的，结点本身不具备 统观网络全局的能力，因此我们强调这些全局搜索算法都不属于网络可导航性的 研究范畴。网络可导航性研究的一项主要工作就是研究分散搜索算法，即随机选 择网络中的两个结点s 和t ，试图以尽可能少的步数找到一条从s 出发到目标f 的 路径，在此过程中信息不断地从当前结点传递至下一个结点( 当前结点的邻接 点) ，于是信息传递的任务在结点间不断下放，从而在网络中形成了一条“隧道”， 这种“打隧道”形式的搜索算法就称为分散搜索算法( d e c e n t r a l i z e da l g o r i t h m s ) 。 如果仔细思考一下，分散搜索算法的提出是有实际作用的。m i l g r a m 的实验 在算法上做了妥当的考虑：由于社会网络中存在短路径，人们通过熟人可以建立 9 2 0 0 8 年上海大学硕士学位论文 起彼此间的联系。m i l g r a m 的实验设想了这样一种传递情况：如果实验者真的希 望找到一条从起始人到目标人的最短路径，那么实验应该要求起始者把信传递给 他或她的所有朋友，再由对方继续以此方式把信传递下去，过程不断反复进行， 直到找到目标人。这种“泛洪式”的传递方式理论上可以找到最短路径，但在实际 操作中显然是不可行的。于是，m i l g r a m 进行了这个更有趣的实验：在网络中， 传递路径上的中间结点根据目标结点的信息选择一个最佳的结点来传递信件，利 用这种方式构建路径，于是信件每次只能传递给一个人即使最短路径存在， 信件的传递过程也可能会失败。 这种分散搜索算法提出了一个根本性的问题：为什么社会网络所产生的结构 可以利用分散搜索算法找到结点间的短路径? 显然网络包含着某种“倾向度”来 引导参与者将信息传递到目标人，这正是我们可以试着建模的地方：试着从这个 模型中提取某种以区分哪种网络可以产生有效的短路径。值得注意的是，这些问 题远远超出了m i l g r a m 实验的社会网络的范畴，这种利用局部信息建立的短路径 同样出现在各种非社会网络中，因此我们要了解有效的分散搜索算法作用下的基 础网络结构。 直到2 0 0 0 年，k l e i n b e r g i i 6 在对m i l g r a m 的实验进行研究时发现：垫金圆终 中任意两结点查闽丕堡易王瑟盛堑堕堡：亘旦塑亘丝逗蕉圈终的凰部焦，皇垫到 i _ _ _ 。- _ - _ 。 _ - - 。- 。- 。4 。一一 一 这条短路径。于是，k l e i n b e r g 抓住利用网络局部信息这一关键点，提出了一个 具有可导航性的网络模型，才从真j 下意义上开辟了网络可导航性的理论研究道 路。下一节我们将重点介绍k l e i n b e r g 模型并从中挖掘出该模型的本质，为提出 我们的模型做准备。 2 2 k l e i n b e r g 模型 w s 模型没有考虑寻找短路径的搜索算法问题，但由于它所具有的小世界特 性，一种自然的设想是如果对w s 模型稍作改进并运用合适的分散搜索算法，那 么w s 模型是否具有可导航性。k l e i n b e r g 希望圈垒送型殴绫枣焦：垦墨塑坌亘麴 且部分未知的显然在m i l g r a m 的实验或者其它的实验框架中，每个结点不仅 知道它的邻域结点的情况，而且清楚地知道网络所植根的全局“参照框架”。w s 1 0 2 0 0 8 年f ：海人学硕上学位论文 模型以一种最简单的方式表征了所有这些特征。但是，k l e i n b e r g 却得出了下面 这样一个消极的结论。 定理2 2 1 1 1 6 , 1 7 】任何分散搜索算法在w s 模型中的传递时间是n ( n 2 7 3 ) 。 若一个函数是q ( 厂( 刀) ) ，即存在一个常数c 使得对于任意大的疗，函数的下 界为( 刀) 。w s 模型及以往类似模型中的网络直径是网络规模的对数，但是定 理2 2 1 则表明了利用分散搜索算法实际找到的路径长度为网络规模的指数。 k l e i n b e r g 指出w s 模型中的随机连边显得太“无结构”，因而无法得到在m i l g r a m 实验中发现的那种分散搜索路径。k l e i n b e r g 就此提出了寻找简单的扩展模型的 问题，使得模型能够通过有效地分散搜索找到短路径。 为了扩展模型，k l e i n b e r g 在格子网基础上引进了结点的坐标以及一个附加 的参数口 0 。结点坐标的作用是在搜索路径的过程中提供信息，由此可以判断 搜索路径上的结点是否接近目标结点；参数口的作用是控制长程连边的分布。 定义2 2 1 一个d 维格子网是带标号、未加权、无方向的简单图，这种简单 图与d 维欧几里得立方格相似。在d 维欧几里得立方格中，任意结点v 都与它的 网格邻接点u i 和w i 相连，u 。和w j 可以通过以下公式描述： u i = 【( v 一尸) + n ( m o d n ) 雌= ( v + i d ) ( m o d n ) 其中，l z k 2 ，1 d d ，而且通常假定k 2 d 。因此，k = 2 的1 维格子网 是一个环，k = 4 的2 维格子网是一个二维方格等。 k l e i n b e r g 模型：以一个2 维格子网作为基础网络，且这个网格为有向网络 ( 如图2 1 a ) 。首先把结点设定在一个摆押的正方形网格交点上，结点坐标为 ( f ，) ：f 1 , 2 ，以 ， 1 , 2 ，刀) ) ，对于两个结点v ( i ，j f ) 和u ( k ，) ，定义网格距 离为p ( v ，u ) = | 七一ii + it 一，i 。对于任给的常数p l ，结点u 与周围网格距离小于 等于p 的结点建立有向边，这些连边称作结点u 的短程连边。对于距离大于p 的 结点，对任意的q 0 ，0 ，结点u 又与q 个结点以概率p ( v ，u ) 建立有向边，这 些连边则称作结点u 的长程连边( 如图2 1 b ) ，其中第f 条长程连边是从结点u 到 结点v 的有向边，它的概率为：尸( u “) = 乏兰善笔。 2 0 0 8 年f ：海大学硕士学位论文 b l o o ooo o oo oooo o o o o o o w 图2 1 ( 引自文献f 4 0 】) ：a ) 一个二维的网格网络，其中疗= 6 ，p = 1 ，q = 0 ；b ) 结 点u 的邻接点，其中n = 6 ，p = l ，q = 2 ，结点v 和w 为它的长程邻接点。 这个模型有一个简单的“几何”描述：结点都位于网格坐标上，并且每个结点 都知道它邻域内的情况，此外结点还具有一些远程连边。若p 1 ，q 0 为给定的 常数，则通过变化指数口得到一族网络模型。当口= 0 时，结点的长程连边满足 均匀分布，即长程连边的分布独立于结点在网格上的位置，此时模型退化为w s 模型。随着口的增加，结点u 的长程连边越来越向结点附近靠拢，基本不产生距 离较远的长程连边。 k l e i n b e r g 模型使长程连接偏向于网格距离较小的结点，偏向的程度由口来 决定。根据参数口的变化，我们有了一族可供研究的模型。当口取值较小时，长 程连边显得“太随机”，不能够使分散搜索算法生效；当口取值较大时，长程连边 会显得“不够随机”，因为它们提供不了足够多的长程跳跃以产生小世界现象。那 么网络是否存在一个最优的参数口，使长程连边的分布保持足够的平衡，从而让 分散搜索算法起作用呢? 实际上，定理2 2 2 表明网格模型中存在一个唯一的口， 使得模型具有可导航性，信息的传递时间能取到网络规模的对数多项式。 定理2 2 2 【1 6 , 1 7 1 ( a ) 当0 口 2 时，模型中的任何分散搜索算法的传递时间为n ( n t 弘2 ) 似。1 ) 。 根据上述定理，我们知道当口= 2 时分散搜索算法是有效的。此时若p = 1 ， 每个结点简单地将信息传递给它的一个邻接点长程的或短程的，被选择的结 1 2 2 0 0 8 年卜海大学硕士学位论文 点与目标结点的网格距离是最小的。对算法的分析表明【1