（理论物理专业论文）空间网络的搜寻信息特性.pdf

t h e p r o pe r t yo f se a r c h i n f o r m a t i o ni ns p a t i a ln e t w o r k s at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t f o rt h em a s t e rd e g r e ei nt h e o r e t i c a lp h y s i c s b y z h a o t i n g t i n g p o s t g r a d u a t ep r o g r a m c o l l e g eo fp h y s i c a ls c i e n c ea n dt e c h n o l o g y c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：c a ix u a c a d e m i ct i t l e ：p r o f e s s o r s i g n a t u r e a p p r o v e d m a y 2 0 1 1 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工 作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：赵咖亏 日期：2d ，年岁月，7 日 ， 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和 借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其 它复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名： 赵崂磅 b 期：2o 年箩a | 日 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人 的学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程” 中的规定享受相关权益。回童诠室握交卮溢蜃；旦坐生；旦= 生；旦三生筮查! 作者签名：赵磅谚 b 期：2 0 年；其| 日 导师签名： 雷荦 哺o 如誓一| 1 1 l 吒 硕士学位论文 m a s t e r st h e s i s 摘要 在各种复杂系统中，有关活动能得以有效进行，其基础往往决定于系统有序 的网络结构。本论文旨在构建具有搜寻能力的复杂网络模型，从而找到复杂网络 拓扑结构形成的动力因素。论文的工作主要分两个部分： 第一部分，讨论复杂网络的搜寻信息特性。首先，作为实证研究，对城市街道 网络的搜寻能力进行了分析。例如，研究表明武汉之所以比北京难于搜寻，是因 为武汉受长江、汉水、湖泊和山脉等地势因素的限制较多。然后，通过对海豚网、 街道网、蛋白质作用网、电力网及科学家合作网的搜寻能力的实证研究，我们发 现各种真实网络都呈现出极强的搜寻信息正相关性。这一现象与几个常见的网络 模型有较大差别。但是，其中规则格子却具有几近于线性的关联特性。我们由此 推测，局域限制可能是导致这一现象的因素之一。 第二部分，我们构建了二维空间网络，将网络中的节点置于特定的坐标位置。 以空间距离来表示节点问的差异，以作用半径刷折规定的活动范围来反映网络中的 局域限制。进而，我们提出了一类依赖于空问距离的网络连接和演化模型。一方 面，在我们的这几个模型中都得到了与真实网络致的信息关联特性，说明空间 网络确实在搜寻方面具有特殊性；另一方面，研究还发现空间距离在构建度的同 配型网络时起到了关键作用，而异配型网络则必须同时依赖度的优先连接机制和 空间限制。 关键词：复杂网络；搜寻信息；空间网络；空间距离；作用半径；匹配性 l i nac o m p l e xs y s t e m ，aw e l l - o r g a n i z e dt o p o l o g i c a ls t r u c t u r ee n s u r ea l la c t i v i t i e s g oo n w h e e l s i nt h i sp a p e r ，w ea i ma tb u i l d i n gu pan e t w o r km o d e lt h a ti ss e a r c h a b l e ， a n df i n d i n go u tt h ed r i v e rt h a tl e a d st ot h et o p o l o g i c a ls t r u c t u r e t h em a i nr e s e a r c h o fo u rw o r kc a nb ed i v i d e di n t ot w op a r t s ： i nt h ef i r s tp a r t ，d i s c u s s i n gt h es e a r c hi n f o r m a t i o ni nc o m p l e xn e t w o r k s f i r s t ， w es t u d yt h es e a r c ha b i l i t yo fu r b a ns t r e e tn e t w o r k s ，a n df i n dt h er e a s o nt h a ti t i s m o r ed i f f i c u l tt os e a r c hi nw u h a nt h a ni nb e i j i n gi st h a tw u h a nh a sm o r eg e o g r a p h i c b o u n d a r i e s ，s u c ha sy a n gz ir i v e r ，h a nr i v e r ，l a k e sa n dm o u n t a i n s t h e n ，w eg e tt h e r e s u l tt h a tv a r i o u sk i n d so fr e a ln e t w o r k sa p p e a rt ob ep o s i t i v e l yc o r r e l a t e db ys e a r c h i n f o r m a t i o nt h r o u g ht h ee m p i r i c a ls t u d yo fd o l p h i n ，b e i j i n gs t r e e t s ，p r o t e i n - p r o t e i n i n t e r a c t i o ni ny e a s t ，u sp o w e rg r i da n dc o - a u t h o r s h i pn e t w o r k i ti sq u i t ed i f f e r e n t f r o ms o m et y p i c a ln e t w o r km o d e l s h o w c v e r ，t h er e g u l a rl a t t i c ei sa l m o s tl i n e a r l e a r n i n gf r o mt h i s ，w er e a s o nt h a tl o c a lr e s t r i c t i o ns h o u l db eo n eo ft h ef a c t o rt h a t l e a dt ot h i sp h e n o m e n o n i nt h es e c o n dp a r t ，w ec o n s t r u c tt w o - d i m e n s i o n a ls p a t i a ln e t w o r k s ，p u te v e r y n o d eo ft h en e t w o r ko nt h ef i x e dc o o r d i n a t ep o s i t i o n t h es p a t i a ld i s t a n c ei st h e d i f f e r e n c eb e t w e e nt h en o d e s a c t i o nr a d i u srr e f l e c tt h e1 0 c a lr e s t r i c t i o ni nt h e n e t w o r k t h e nw ep r o p o s eac l a s so fm o d e l st h a td e p e n do i ls p a t i a ld i s t a n c e o nt h e o n eh a n d ，w eg e tt h ec o n s i s t e n tr e s u l t so fi n f o r m a t i o nc o r r e l a t i o nw i t ht h er e a lo n e ， w h i c h p r o v et h a ts p a t i a ln e t w o r k sd os h o wp a r t i c u l a r i t yw h i l es e a r c h i n g ；o nt h eo t h e r h a n d ，w ef i n dt h a ts p a t i a ld i s t a n c ep l a y sal e a d i n gr o l ei ng e n e r a t i n ga l la s s o r t a t i v e m i x i n gb yd e g r e e ，w h i l ea d i s a s s o r t a t i v em i x i n gm u s tr e l yo nb o t hd e g r e ep r e f e r e n t i a l a t t a c h m e n ta n ds p a c er e s t r i c t i o ni no u rm o d e l k e y w o r d s ：c o m p l e xn e t w o r k ；s e a r c hi n f o r m a t i o n ；s p a t i a ln e t w o r k s ；s p a t i a ld i s t a n c e ； a c t i o nr a d i u s ；a s s o r t a t i v i t y 硕士学位论文 m a s t e r st h e s i s 目录 摘要i a b s t r a c t i i 1 绪论1 2 复杂网络基础3 2 1 复杂网络的表示及特征量3 2 2 复杂网络的拓扑结构特性6 2 3 复杂网络模型8 3 复杂网络的搜寻信息特性1 2 3 1 信息熵1 2 3 2 搜寻信息1 4 3 3 城市街道网络的搜寻信息特性1 6 3 4 搜寻信息关联特性1 7 3 5 网络尺寸分析1 9 4 空问距离对信息关联的影响2 1 4 1 空间网络2 1 4 2 基于空问距离的连接模型2 4 4 3 基于空间距离的演化模型2 7 4 4 空间距离对网络匹配性的影响2 8 5 工作总结及展望3 0 参考文献3 2 硕士期问发表文章列表3 6 致谢3 7 硕士学位论文 m a s t e r st h e s i s 1 绪论 世界上没有两片完全一样的叶子，这是因为它们的生长历程不尽相同，而且 即便是同一片叶子在不同时期也会有所变化；但是，它们始终都以叶子的形态展 现在世人面前。我们会不禁感慨：究竟是什么力量造就了这纷繁复杂而又内含有 序的万千世界呢? 著名物理学家盖尔曼在夸克与美洲豹一书中曾提到：“美洲豹是那些难以 琢磨的复杂适应系统的一个暗喻【1 | o 我想，对于我们这些有心探索的人来说，美 洲豹和叶子、还有那些富于活力的事物都会是极好的暗喻。而我们多么希望能尽 早解读出其中的奥秘啊! 在本文中，我们并非要讨论生物起源或演化，但它确是使我们对探究复杂系 统产生兴趣的主要原因之一。自上世纪八十年代，对于复杂性科学的研究就犹如 复杂系统本身一样呈现出急速“涌现”的趋势。至今，它的触角几乎涉及到所有的 学科分类一一物理学、生物学、经济学、社会学、计算机科学等等。它之所以能有 如此广的涵盖面，还源于“复杂 二字。我们所认识的世界由那些可为人们所知 的单元构成，最终为我们所见的则是略带些神秘的庞大系统。这些系统不是单元 的机械组合，它们往往具备了单元所不具有的整体功能性。构成社会系统的单元 是人，构成人的单元是细胞，当我们考虑这些复杂系统的时候，单元便是简单 的。这就好比“运动是绝对的”，我们1 七) 表示节点度大于或等于后的概率。这种做法是考虑到统计数据内部总是存在 涨落，尤其是对那些数据量较小的系统而言，采用累积度分布作图可以有效控制 尾部噪音。 相较于分布函数，度度关联更能反应网络邻域特性【2 1 】： 和去争岛， ( 2 4 ) 上式给出的是节点i 的最近邻居节点度之平均。那么对应于节点度为七的节点，则有 函数 ) = 邕措。 ( 2 5 ) 该函数能告诉我们连接度为k 的节点倾向于与连接度为多大的另一节点相连：转 换为数学语言就是，在七已经存在的前提下，与之关联的概率，i l p p ( d l k ) 。公式 4 硕士学位论文 m a s t e r st h e s i s 2 5 也可写为： ( 尼) = k p ( k l k ) 。 ( 2 6 ) 我们可以作出函数k 。( 尼) 的图像来确定度的关联性；也可以通过另一种更为直观 的方法，即直接计算关联系数。常用的一类关联系数是皮尔森关联系数( p e a r s o n p r o d u c t m o m e n tc o r r e l a t i o nc o e f f i c i e n t ) 。n e w m a n 给出了一种表示【2 2 】： r = - h ( ) e 觑岛一i 1 ( ) e ；( + 码) 】2 飘i 磊矗阿再扩孺茬忑磊蕊而 ( 2 7 ) 其中，k , 和k j 分别表示连接网络中相邻节点i 与j 的连接度，f t j 、f e 是对所有的边 求和，m 是网络的总边数，一l r 1 ，我们称该系数为匹配系数。在关联网络 中，如果连接度大的节点倾向于同连接度小的节点相连，那么有一l r 0 ，这 类网络称为度的异配型网络( d i s a s s o r t a t i v em i x i n g ) ；反之，如果连接度大的节点 倾向于同连接度大的节点相连，则0 f 1 ，网络为度的同配型网络( a s s o r t a t i v e m i x i n g ) 2 2 1 。当然也有节点的连接与它们的各自的连接度无关的情况，这时， p ( k 7 i k ) = p ( k ，) ，k n 。( 七) = 七，l d p ( 1 d ) = ( k 2 ) ( 七) 。研究发现，生物，信息，技术 网络等通常表现异配性；而社会网络表现同配性。 2 、最短路径( s h o r t e s tp a t h ) 从网络中任意节点到另一节点，我们总可以找到一条只经过最少节点的路径， 我们称其为最短路径。令节点i 与j 之间的最短路径长度为b ，则网络的直径为： l = m a x i ，j b ) 。 ( 2 8 ) 对于已成规模的复杂网络，其中任意两节点问的最短路径往往不只一条，这就产 生了简并最短路径( d e g e n e r a t es h o r t e s tp a t h ) 的概念。下面我们给出一个形如北 斗七星的简单网络，节点1 与6 之问便存在两条最短路径，即1 2 3 4 5 一 图2 2 ： 5 硕士学位论文 m a s t e r st h e s i s 6 和1 2 3 4 7 6 。简并路径的存在对于真实网络的物质运输和信息传递等 具有重要的意义。 3 、聚集系数( c l u s t e r i n gc o e f f i c i e n t ) 由图2 2 ，我们不难发现，只有当网络中存在“环”时，才能出现路径的简并 现象。类似这样，存在于节点i 邻域范围内的节点所组成的环能够体现该节点的聚 类性，这一特性用聚集系数表征。下面我们给出两种较常见的算法【2 3 】： 一是考虑节点邻居问存在连接的情况， c i2 砥f j 历 ( 2 9 ) 厩是节点i 的邻居问实际相连的边数，觑( 一1 ) 2 是这k i 个邻居间可能的最大连接 数。 二是考虑节点与其邻居组成环的情况， 与点i 相连的三角形的数量 q2 写百葫孺雨正孑酉丽薮量。 ( 2 1 0 ) 这两种方法分别从不同角度反应了同一问题，那就是节点i 的邻居依然是邻居的可 能性。尽管这样的计算方法在多数时候能反应网络的聚类特性，但单从我们给出 的图2 2 就能看出，它们是有局限性的。对于那些不存在三角型环的节点，都会被 认为是“零”聚集力的。这一点与聚集系数能体现网络可传递性( t r a n s i t i v i t y ) 相 悖，于是科学家提出高阶聚集系数【2 4 】，或者将三角形推j “到四边形，在此并不赘 述。网络整体的平均聚集系数为： r c = 了l j it 7 z 。( 2 1 1 ) 2 2 复杂网络的拓扑结构特性 在讨论复杂网络的特性之前，我们有必要用少量篇幅来介绍一下复杂系统的 特征。现在，国内外学者研究比较多的有如下方面【2 5 】：一是非线性，复杂系统各 部分问不是简单的相加，而是存在相互作用，这是复杂系统表现出复杂性的重要 因素；二是涌现性，那些只是系统整体拥有而部分并小拥有的特性便是涌现性的 表现；三是自适应性，系统总是朝着某一方向演化，这个方向保证了系统的存在 以及趋向于更复杂；四是自组织临界性，一种永久偏离平衡，却又被组织在一种 稳定状态中的特性，表现为各种事情都能按照完全确定的统计规律发生【2 6 l ：五是 6 硕士学位论文 m a s t e r st h e s 玛 自相似形，这种相似形可以是不同系统之间的相似，也可以是同一系统中不同层 次所具有的相似性。当然，也还包括其它特征，比如多样性，不可逆性等。 复杂系统能抽象成网络，那么这些网络是怎样“活”起来并具有如上所述的 特征的呢? 虽然我们还没法给出一个答案，但是却能肯定的是网络结构必然起到 了作用。也就是说复杂网络不单单是节点与边的集合，它具有区别于一般网络的 特殊的结构性能。 1 、小世界特性( s m a l l - w o r l dp r o p e r t y ) 小世界的概念来自社会心理学家米尔格兰姆提出的“六度分割理论”1 2 7 】，这 理论告诉我们任意两个陌生人之间只需要通过很少的几个步骤就能产生联系。 而具体步骤的多少则受到联系方式和能力的影响。我们现在常常说：世界各地的 人们越来越近，整个地球己成为名副其实的村落! 大家之所以会有这样的感叹，正 是因为现代科技优化了联系方式、增强了联系能力，从而拉近了人与人的空间距 离。 从物理的角度来看，那些具有相对小的平均路径长度和相对大的聚集系数的 复杂网络便表现出小世界性。 2 、无标度特性( s c a l e - f r e ep r o p e r t y ) 1 9 9 9 年，原本以为会从大量的数据中得到泊松分布的a l b c r t 和b a r a b 五s i 二人 却意外地发现了度的幂律分布， p ( k 1 = k 一7 ，( 2 1 2 ) 并且对于真实网络而言，2 ，y 3 。这个与之前几十年人们所葆有的认识截然不 同的结果是具有划时代意义的。 度的无标度性可以从度分布形式得到。当我们对自变量k 进行放缩，k c k ， 则有p ( c k ) = ( o k ) 一7 = c - 一， k 一1 = c - 1 p ( k ) 。由于c 是常数，度分布函数的形式不变， 与标度无关。无标度性核心意义在于，它表达了复杂网络不受其年龄、功能甚至 作用范围的影响而都具有一种相似结构的特性【2 8 】。 3 、鲁棒性和脆弱性( r o b u s t n e s sa n dv u l n e r a b i l i t y ) 一场激烈的暴风雨过后，旷野中的小草缀着满脸的晶莹雨水姿态依旧，而矗 立在一旁的几株大树则枝折叶落显得格外狼狈。可我们不能因此就说小草是坚强 的，大树是脆弱的，其实它们是各有优势也有弱点。我们知道将一棵小草拔起何 其容易，但是单靠人力挪动大树是难为的。 复杂网络也具有这样的两面性，即鲁棒性与脆弱性。它们作为矛盾双方并不 7 硕士学位论文 m a s t e r st h e s i $ 是分别地独自表现为某个网络的特性，而是复杂网络自身所包含的既对立又统一 的关系。当恶意攻击网络的薄弱点时，网络是很容易就被摧毁的；相反，如果只是 一般情况下随机施加的破坏则一般小会影响到整个网络的功能性一一实际上，在互 联网中，每时每刻都有许多路由器失效，但整个并不会受到大的影响。研究表明 复杂网络的鲁棒性与其无标度特性和异配拓扑结构有密切的关系。 我们说网络由点与边构成，因此对网络进行的破坏活动如上所述包括两类， 一是有目的地删除重要的节点或边，即恶意攻击，二是随机删除节点或边，即随 机出错1 2 9 】。 2 2 复杂网络模型 复杂网络模型只是复杂系统模型的一个方面。复杂网络模型就好比是细胞培 养所需的基底，它构成方式的优劣直接决定了是否能让存在于其中的有机体繁衍 形成一个具有生命力的系统。 1 、规则网络 规则网络模型有最简单的相互作用方式，其周期性的变化规律非常方便于理 论研究。 ( a ) 格子i 。 图2 3 ： ( b ) 格子i i 上面，我们给出了两种格子，一种是常见的欧几里德格网2 3 ( a ) ，这种格子的 特点是结构稀松，局域聚集性弱，所以它明显不具有复杂网络的特性。因此为加 大聚集性，也可以如图2 3 ( b ) 构建格子。 2 、随机网络 随机图的构建方式也是多样的t 8 硕士学位论文 m a s t e r st h e s i s ( 1 ) e r 随机模型，由e r d 5 s 和r 6 n y i 在1 9 5 9 年提出 3 0 1 。 一是给定网络总的节点数和边数m 。通过随机选取两个节点i 和j ，从而确定 一条边( 仇，吩) ，直到构成g ( n ，m ) 。这里gc g ，g 是所有可能产生的随机图的图 集。 二是给定网络总的节点数和连接概率p i 任意两节点问以概率p 产生一条边， 直到构成g ( n ，p ) 。这种方式更有利于数值分析：个节点之间可能产生的总边数 为n ( n 一1 ) 2 ，实际产生边数p n ( n 一1 ) 2 ，总连接度为p n ( n 一1 ) 。如果一个节 点的连接度为k ，则说明整个网络中有k 个节点与之相连，同时也有n 一1 一k 个 节点不与其相连，k 个节点从n 一1 个节点中选出有c 岛一，种可能性，因此，节点度 为k 的概率为： p ( k ) = 嘴一1 p k ( 1 一p ) 。卜七。 ( 2 1 3 ) ( 2 ) 随机网络对于研究真实网络是有实际意义的，它往往被作为常模来进行 比照。在这种情形下，可以给定与真实网络相同的度序列d 或者度分布p ( 七) 。这 时网络中的节点依然随机与其它节点相连，但是每个节点都被限制好了连接度， 也就是说一个节点达到了它应当连接的最大边数后就不再参与连接了。为了将它 与e r 随机网区分开来，可以称其为广义随机网。 3 、小世界网 生成小世界网的主要机制是增加捷径( s h o r t c u t ) 。1 9 9 8 年，w a t t s 和s t r o g a t z 提出w s 小世界模型： 1 从有个节点的一维规则环开始，这个环中的每个节点都与其最邻近的k 个节 点相连( k 为偶数) 。 2 按照概率p 将规则网中的节点的边进行重绕。 重绕的方式极易导致网络分裂成小碎片而失去整体的连通性，这给实际建模 带来许多麻烦，因此n e w m a n 和w a t t s 又提出了另一个简单有效的小世界网构建方 法，他们改变了重绕的做法，直接在一维规则环上按一定的概率p 进行连边。 4 、无标度网 ( 1 ) b a 模型 1 9 9 9 年，b a r a b e s i 和a l b e r t 从大量的实证研究发现了真实网络的无标度特性。 在此基础上，他们提出了第一个具有无标度特性的网络演化模型一一b a 模型，其 算法如下【3 j ： 1 由节点数m o 较小的网络( 随机网或小世界网) 开始，在此后每个时间步都向 网络中添加一个带m 条边的新节点，m m o 。 9 硕士学位论文 m a s t e r st h e s i s 2 新节点与网络中已有节点i 相连概率；仅受连接度k t 影响，并且越大，概率 越高。因此有： n b ( 觑) = e j l k j 。 ( 2 1 4 ) b a 模型向人们传达了网络演化的两大重要机制：一是增长机制，它反映了 系统从建立初期到稳定这一过程的最主要的特征。二是偏好连接机制，在该模型 中，偏好被理解为新加入节点倾向于同节点度较大的节点相连的特性一一在瓦联网 中，规模越大的路由设备往往也具有越强大的宽带；在学术研究中，声望越高科 学家通常也更易吸引其他科学家与其讨论合作这一现象被著名的社会学家k m e r t o n 称为“马太效应”。 根据上面的定义，我们知道在经历了时间步t 后，任意节点i 的连接度关于t 的 动力学方程为 蓑- m n ( 妒m 轰 ( 2 1 5 ) 这里认为确l 大，可以忽略掉m o 的影响，因此有jk j = 2 m r 。则， o k ik i 瓦2 五。 又己知初始条件( 如) = m ，故可得： 坼，= m ( 扩 其中p = j 1 。利用累积度分布，有 跗以) 可m 2 t ) = 1 - 即；警) = 1 一 又， p ( 忌) = o p l ( k i ( 矿t ) 一k ) ， 故得到度分布为 k 2 ( t + t o o ) 。 ( 2 1 6 ) ( 2 1 7 ) ( 2 1 8 ) ( 2 1 9 ) 耶) = 黑而1 。 ( 2 2 0 ) 当too o 时，p ( k ) = 2 m 2 k 3 ，7 = 3 。 ( 2 ) a b 模型 a l b e r t 和b a r a b 缸i 考虑至, j b a 模型的局限性，随后提出a b 模型，将局域影响融 入其中。网络起始于仇。个相互独立的节点，在此以后的每个时间步都按下面三个 步骤进行【3 2 l ： 1 0 硕士学位论文 m a s t e r st h e s i s 1 以概率p 加入m 条新的连边( m ，h = 一1 2l 0 9 2 互1 一互1l 0 9 2 ；= 1 ；但是当有人告诉我们这枚硬币由于经过处理而导致正面向 上的概率是；，那么概率分布变为p ，= ；，i ) ，h = 一i 1l 0 9 2i 1 一；l 0 9 2i 竺0 8 1 。 显然，当我们获取了适当信息之后，我们判断或处理问题就不用按照最大化信息 熵的道路去做，这时候问题简单了，系统的信息熵变小了。 s o l d , 和v a l v c r d c 较早将信息论应用到复杂系统，并描述了网络的不确定性【3 3 】。 他们运用剩余连接度的分布 2 2 1 m ，= 学 1 3 ( 3 7 ) 型 k 脚 一qa 百 一n盎一n 胍 q ( k ) l o gq ( k ) 。 这里，q = g ( 1 ) ，g ( i ) ，g ( ) ) ，进一步给出条件熵 ( 3 8 ) nn 皿( q l q ，) = 一q ( k ) i i ( k l k ) l 。gi i ( k l k ，) o ( 3 9 ) k = lk s = 1 当玩( q iq ，) = o 时，那么必然有( 忌i ) = l 或l i ( k l k ) = 0 ，臣p y i ( k l k ) = 以，f 。因此 可以得到g c ( 后，k 7 ) = g ( ) 民，这时恰好对应了完全同配的网络。 3 2 搜寻信息 入 专z ik 够 缪， 喇例2 瓦1 翮i i ，6 ) 百1 j 。 ( 3 1 。) 1 4 硕士学位论文 m a s t e r st h e s i s 其中，k i 是节点i 的连接度，p ( t ，6 ) 表示的是从i 到6 的简并路径中的一条，歹是该 条路径上出现的节点。那么，能顺利( 即沿最短路径) 将邮件发送的概率 为p ( i ，6 ) p p ( i ，6 ) ) ，p ( i ，是对所有的简并路径求和。然后，他们提出了搜寻 信息( s c a r c hi n f o r m a t i o n ) 这概念，即： 即剐卜。嘟，) q s ( i - - y6 ) 衡量了由t 到6 的困难程度，s ( i - - y6 ) 越大，则所需信息量越大。 整个网络的平均搜寻信息是 ( 3 1 2 ) 其中，为网络的总节点数。 从信息视角来分析一个人在陌生城市中的行走，能更容易理解这一定义。当 我们来到陌生的城市里，只有获取新的信息才能够到达目的地。假定从如图3 1 所 示的i 处去往b 时，我们要通过向别人提出“是不是这条路? ”的问题来获取信息。 那么，s ( i - - yb ) = s ( i - - - yj 2 ) q - s ( j 2 - - yb ) = 一( 1 0 9 2i 1q - l 0 9 2 ；) 就是所需问题的总数。 显然所问问题越多，那么搜寻过程就越困难。 图3 2 ：真实网络与其所对应的随机网络的平均搜寻信息值的对比图。 真实的网络与其所对应的随机网络相比较总是拥有较大的平均搜寻信息( 见 图3 2 ) 。这就意味着，在真实网络中进行搜寻，往往需要较多的信息。那么，这是 刁是表示真实的网络是不可搜寻的呢? 事实上，m r o s v a l l 经证明相对大的s 反 应出网络的社区划分。由于社区的存在，局域范围内个体相互作用将更加活跃。 而根据最大信息熵原理，我们也发现大搜寻信息值还体现了网络连接模式的多样 1 5 吣0 s m耐 一2 1 一 = s 硕士学位论文 m a s t e r st h e s i $ 性。这就好比“条条大路通罗马”所描述的，搜寻呈现出合乎实际的多种选择性。 从这个意义上讲，真实网络本身就是可搜寻的。 3 3 城市街道网络的搜寻信息特性 在大城市中搜寻自己的目的地有多困难? 如果你已经在这个大城市中住了一 段时间，那么你可能对它的路况了如指掌，也就谈不上有任何的困难了。然而，如 果你初来乍到，那么即便只是隔着一条街的地方，也需要指引。比如询问路人下 一步该怎么走，或者你- t 脆手执一张地图。可是无论怎样，你都必须是通过获取 信息才能够到达目的地。否则，在毫不知情的状况下，你就会如无头苍蝇找刁、= 着 北，甚至南辕北辙，白白耗费了时间。那么研究城市街道网的搜寻能力就显得格 外重要了。 选取我国的北京市和武汉市为研究对象，它们分别包含4 1 5 和3 9 9 条主要街道、 1 1 1 6 和1 0 3 6 个交叉路口。我们按照对偶途径将其构建为具有信息功能的城市街道网 络 1 6 , 2 4 。在此情况下，街道被抽象为节点，交叉路口为边。这反映了人在交叉路 口时才需要判断然后做出选择的情形。 图3 3 ：城市街道网络搜寻信息对比图。 图3 3 给出了武汉与北京平均搜寻信息的柱形图。虽然武汉的街道数量略少于 北京，但其平均搜寻信息值却大于北京。即，相较于北京，在武汉这座城市里，人 们是更难于搜寻到目标的。然而，它们各自对应的随机网络的信息值并无太大差 别，那么真实武汉街道网络的节点连接方式一定具有某些特殊性。于是我们结合 地图( 见图3 4 ) 再做进一步分析，并且发现北京与武汉城市街道的连接确实各具 特点：北京街道多是横贯南北朝向，或东西朝向的，它们将城市分割成规整的方 块；武汉则受长江，汉水，湖泊和山脉等天然屏障的限制，其中的街道多依势而 1 6 硕士学位论文 m a s t e r st h e s i s 建。我们认为这必然是导致他们搜寻能力差异的重要原因。 ( a ) 北京 图3 4 ：截取自网站( 3 5 】 ( b ) 武汉 基于武汉地势的特殊性，我们对其城市街道网络做了特别处理一一将六座卧于 江面的桥梁隐藏起来，使整个网络分成三个独立的区域，即汉口，武昌，汉阳。它 们的节点数分别为1 7 2 、1 6 1 和6 0 。然后，我们对三个区的搜寻能力分别进行分析。 首先，由柱形图可以看出整个网络的平均