（地图学与地理信息系统专业论文）中国铁路加权网络研究.pdf

中国铥填 加权网络研究 中国铁路加权网络研究 专业：地图学与地理信息系统 硕士生：卢彬源 导师：张青年副教授 摘要 许多实际网络都是加权网络，加权网络引入了顶点之间相互作用的强度，刻 画了连接的多样性，增加了网络的抽象刻画能力；同时，边权的引入也极大地丰 富了网络的统计性质。除了由边决定的连接外，对于加权网络还必须关注与权重 有关的统计性质，特别是权重与拓扑的相关性，这为理解相应系统的组织结构提 供了一个新的视角。 本文以中国铁路网为对象，将其抽象为铁路地理网和铁路车流网两个结构来 描述，在此基础上分析其加权性质。铁路地理网的构成是以铁路站点为节点，连 接各站点之间的铁路线为边，以站点间的里程作为权值；铁路车流网是以铁路站 点为节点，通过两个站点的列车为连线构建，以两个站点间的车流量作为权值。 在构建模型的基础上利用g i s 组件开发求解对这两个抽象网络的点强度分布、 平均路径长度、聚集系数等网络模型统计特征值，根据统计值分析各抽象网络的 加权网络性质。结果表明加权车流网是树状结构，而非无标度和小世界网络；加 权车流网是标度网络而t 1 1 4 , 世界网络。在此基础上分析总结得到中国铁路网的加 权网络结构特征，其结果可对铁路网络规划和测评起到良好的辅助作用。 关键词：中国铁路网、地理网、车流网、加权网络、网络拓扑性质 m 中国铁路媳罔络研究 s t u d y o fc h i n e s ew e i g h t e d r a i l w a yn e t w o r k m a jo r ：c a r t o g r a p h y g i s a u t h o r ：l ub i n y u a n s u p e r v i s o r ：a s s o c i a t ep r o f z h a n gq i n g n i a n a b s t r a c t m o s to ft h er e a ln e t w o r k sa r ew e i g h t e dn e t w o r k s w e i g h t e dn e t w o r ki n t r o d u c e t h ei n t e r a c t i n gs t r e n g t hb e t w e e nn o d e s , w h i c he n h a n c et h ea b s t r a c td e p i c t 堍a b i l i t yo f n e t w o r k s ；a l s o ，i n t r o d u c t i o no fw e i g h tc a l le n r i c ht h es t a t i s t i cp r o p e r t i e so fn e t w o r k s e x c e p tt h ec o n n e c t i o n sa s c e r t a i n e db ye d g e s , w em u s tp a ya t t e n t i o nt ot h es t a t i s t i c p r o p e r t i e sa b o u tw e i g h t ，e s p e c i a l l yt h er e l a t i v i t yb e t w e e nw e i g h ta n dt o p o l o g y , w h i c h c a np r o v i d ean e ww a yt oc o m p r e h e n dt h eo r g a n i z i n gs t r u c t u r eo f s y s t e r n s t h i st h e s i si s g o i n gt or e s e a r c ho nt h ew e i g h t e dn e t w o r kp r o p e r t i e so ft h e c h i n e s er a i l w a yn e t w o r kw h i c hc a nb ea b s t r a c ti n t or a i l w a y g e o 蓼a p h i cn e t w o r ka n d r a i l w a yt r a f f i cn e t w o r k t h er a i l w a yg e o 笋a p m cn e t w o r ki sc o m p o s e do fr a i l w a y s t a t i o nj u n c t i o n sa n dr a i l r o a d se d g e s ，w e i g h t e db yt h el e 蟛ho fr a i l w 哆r a i l w a y t r a 伍cn e t w o r ki sc o m p o s e do f r a i l w a ys t a t i o n j u n c t i o n sa n dt r a i n s t r a c k st h o s et r a v e l a c r o s st h ej u n c t i o n sa se d g e s ，w e i g h t e db yt h et r a i nf l u x b a s eo nt h o s et w om o d e l s ， w ec a nf i n do u tt h es t a t i s t i c se i g e n v a l u e ss u c ha sw e i g h td i s t r i b u t i o n , s h o r t e s tp a t h l e n g t ha n dw e i g h t e dc l u s t e r i n gc o e f f i c i e n tu s i n gg i sm e t h o d s t h ec o n c l u s i o ni st h e w c i g h t e dr a i l w a yg e o m e t r i cn e t w o r ki sn e i t h e ras m a l lw o r l dn e t w o r kn o r as c a l e 丘 n e t w o r ka n dt h ew e i g h t e dr a i l w a yt r a f f i cn e t w o r ki sas c a l e 丘n e t w o r kb u tn o ta s m a l lw o r l dn e t w o r k t h ew e i g h t e dn e t w o r k p r o p e r t i e si sa n a l y z e d ，a n dt h es t r u c t u r a l c h a r a c t e r i s t i co fc h i n e s e r a i l w a yn e t w o r ki se x p l o r e di nf u r t h e ra n a l y s i sw h i c hc a nb e 中国铁路加权罔络研究 u s e dt oa i dt h ep l a n n i n ga n de v a l u a t i o no f r e a ln e t w o r kw e l l k e yw m d s ：c h i n e s er a i l w a yn e t w o r k , r a i l w a yg e o m e t r i cn e t w o r k , r a i l w a yt r a f f i c n e t w o r k , w e i g h t e dn e t w o r k s ，n e t w o r kt o p o l o g yp r o p e r t i e s v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名： 尹硼豫 日期：一罗年莎月7 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规 定，即：学校有权保留学位论文并向国家主管部门或其指定 机构送交论文的电子版和纸质版，有权将学位论文用于非赢 利目的的少量复制并允许论文进入学校图书馆、院系资料室 被查阅，有权将学位论文的内容编入有关数据库进行检索， 可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：步彬涿导师签名：；艮务伍 日期：妒男年歹月7 日日期：枷口幂年石月1 日 f 中国铁路加权同络研究 第一章绪论 中国是一个典型的大陆性国家，经济联系和交往跨度大，需要有一种强有力 的运输方式将整个国家和国民经济联系起来，同时引导和促进其他运输方式的发 展。铁路最显著的特点是载运质量大、运行成本低、能源消耗少，既在大宗、大 流量的中长以上距离的客货运输方面具有绝对优势，而且在大流量、高密度的城 际中短途旅客运输中具有很强的竞争优势，是最适合中国经济地理特征和人们收 入水平的区域骨干运输方式。尽管从2 0 世纪9 0 年代以来，中国高速公路和航空 业获得了巨大发展，对铁路运输形成了越来越明显的竞争，但是，铁路在国民经 济中的支柱作用和在中国综合运输网络中的担纲作用是其他运输方式难以替代 的叫。 2 0 0 6 年全国铁路完成货运总发送量( 包括行包运量) 2 8 8 2 8 5 万吨，比上年 增长7 1 。其中：国家铁路完成2 4 5 4 7 6 万吨，比上年增长5 9 ；合资铁路完成 2 3 1 5 4 万吨，比上年增长1 7 8 9 6 ；地方铁路完成1 9 6 5 4 万吨，比上年增长1 0 4 口1 。 全国铁路完成货运总周转量( 包括行包周转量) 2 1 9 5 4 4 6 亿吨公里，比上年增 长5 9 。其中：国家铁路完成2 0 5 5 7 1 6 亿吨公里，比上年增长5 2 ；合资铁路 完成1 2 9 1 5 9 亿吨公里，比上年增长1 8 1 ；地方铁路完成1 0 5 7 1 亿吨公里， 比上年增长6 6 。2 0 0 6 年国家铁路完成运输收入2 3 6 4 5 亿元，比上年增加3 1 8 亿元，增长1 5 5 。其中：完成货物运费收入1 2 8 1 亿元，比上年增加1 7 1 9 亿 元，增长1 5 5 ；完成客票收入7 2 8 亿元，比上年增加6 7 1 亿元，增长1 0 2 。 实现运输利润7 8 亿元h 1 。 2 0 0 7 年1 - 3 月，中国铁路货运量累计为7 5 0 亿吨，比上年同期增长1 1 6 ；货物周转量为5 6 7 4 4 9 亿吨公里，比上年同期增长了1 1 3 ；客运量为3 4 1 亿人次，比上年同期增长了8 3 ；旅客周转量为1 9 9 4 9 9 亿人公里，比上年同 期增长了8 1 。截止到2 0 0 7 年4 月，中国铁路完成货物运输总发送量1 0 0 8 7 5 万吨，比上年同期增长1 1 3 ；完成货运总周转量7 6 0 2 2 5 亿吨公里，比上年 同期增长了1 0 0 ；完成旅客发送量4 3 5 3 8 万人，比上年同期增长4 6 ；完成 中国铁路加权网络研究 固定资产投资4 1 3 2 11 3 万元，比上年略有下降尘1 。 由此可见，铁路交通在国民经济中占有重要地位，但铁路现状与国民经济 和社会发展的需要相比，中国铁路无论是规模还是质量都还有很大的差距。从数 量上看，铁路路网密度仍处于较低的水平，远落后于发达国家的平均水平；主要 运输通道客货运输能力严重不足，制约了国民经济的发展。从质量上看，铁路的 技术装备水平和管理水平与发达国家有较大的差距，便捷性、舒适性、准时性、 安全性等还远远不能满足旅客和用户的要求隅1 。 2 0 0 6 年至2 0 1 0 年，中国的重工业化步伐可能会减慢，但是这一过程还将会 继续，固定资产投资增速保持1 5 左右的增速将是常态。因此，“十一五 期间， 为了适应中国经济增长，铁路投资必须保持3 0 至4 0 左右的增速，才能较快地 缓解铁路运输的紧张状态嘲。2 0 0 6 年1 0 月底，中国铁路“十一五 规划发布， 确定了未来五年中国铁路建设的主要目标。 本文在分析现有的铁路网数据基础上，应用加权网络的研究方法，建立对应 的加权网络模型，研究中国铁路网的一些加权网路统计特征，在网络的角度上揭 示现有路网的一些结构特征，其结果可以对中国铁路的发展提供一些良性的辅助 作用。 2 中国铁路加权网络研究 2 1 网络科学 第二章加权网络研究综述 正是在世纪之交，1 9 9 8 - 1 9 9 9 年，科学家冲破了长期的传统图论，特别是随机 图论的局限性束缚，在复杂网络的研究中取得了突破性进展，其主要里程碑的标 志是二项重要的发现：小世界网络1 刀和无标度网络n 引。大有“忽如一夜春风来， 千树万树梨花开 ，激起了国内外复杂网络的研究热潮。最近，无标度网络的先驱 和发现者之一，美国圣母( n o t r ed a m e ) 大学物理系的b a r a b d s i 教授正是因为他 在无标度网络等方面的开创性贡献而荣获了2 0 0 6 年美国计算机学会为与计算机 相关的杰出科学技术成就而颁发的y o nn e u m a n n ( 冯纽曼) 计算金奖( c o m p u t i n g m e d a l ) n 9 】，该奖从1 9 7 6 年设立至今才颁发给三位杰出科学家，可见这个奖对于复 杂网络的新发现与计算机相关科学有多么密切关系和极端重要性，这象征着复杂 网络研究真正进入了一个新时代，由此诞生了一门崭新的交叉科学：网络科学。 2 1 1 网络科学的发展 网络科学的发展首先是得益于图论和拓扑学等应用数学的发展。历史上，多 位杰出数学家各自独立地建立和研究过图论，他们的贡献功不可没。早在一百多 年前，关于图论的文字记载最早出现在欧拉1 7 3 6 年的论著中，他所考虑的原始问 题具有很强的实际背景。在数学上，关于哥尼斯堡七桥问题、多面体的欧拉定理、 四色问题等都是拓扑学发展史的重要问题翰。 3 中国铁路加权网络研究 ( 1 ) ( 2 ) 图2 1k o n i g s b e r g 七桥问题图示：从( 2 ) 中任意一点出发，经过每一条边一次后返回原点 的回路是否存在? 另一个对图论( 网络科学理论) 作出具有里程碑的贡献是两个匈牙利著名的 数学家e d o s ( 爱多士) 和r e n y i ，他们在2 0 世纪5 0 年代末和6 0 年代建立了著名 的随机图理论忉，用相对简单的随机图来描述网络，简称e r 随机图理论，他们的最 重要发现是e r 随机图中许多重要性质都是随着网络规模的增大突然涌现的。确 实，用图论的语言和符号可以精确简洁地加以描述各种网络，图论不仅为数学家 和物理学家提供了描述网络的共同语言和研究平台，而且至今图论的许多研究成 果、结论和方法技巧仍然能够自然地应用到现在复杂网络的研究中去，成为网络 科学研究的有力方法和工具之一。可见在长达4 0 年的e r 随机图对于图论理论的 影响之大和如此广泛。 一直到1 9 9 8 年，科学家迎来了复杂网络的又一次突破性进展，首先冲破了e r 理论的框框的人是，美国康奈尔( c o r n e l l ) 大学理论和应用力学系的博士生 w a t t s 及其导师s t r o g a t z 在 n a t u r e 杂志上发表了题为“小世界 网络的群 体动力行为的论文阳3 ，提出了小世界网络模型。 接着，1 9 9 9 年美国圣母( n o t r ed a m e ) 大学物理系的b a r a b d s i 教授及其博士 生a l b e r t 在 s c i e n c e 杂志上发表了题为随机网络中标度的涌现一文1 ， 提出了一个无标度网络模型，发现了复杂网络的无标度性质，并和m n e w m a n n ，d j w a t t s 共同编辑了“网络的结构与动力学( t h es t r u c t u r ea n dd y n a m i c s ， 普林斯顿大学出版社，普林斯顿，2 0 0 3 年) 专著，该书在国际上产生了广泛的影响， 引起了全世界的高度重视。 网络科学的二大发现，以及随后许多真实网络的实证研究表明，真实世界网 络既不是规则网络，也不是随机网络，而是兼具小世界和无标度特性，具有与规则 网络和随机图完全不同的统计特性。这在全世界学术界激起了千重浪，复杂网络 4 中国铁路加权网络研究 文章铺天盖地，网络科学的综述和专著不断涌现n 们，从物理学到生物学，从社会科 学到技术网络，从工程技术到经济管理等众多领域，受到了人们的空前的广泛关 注和重视，正在突飞猛进。 2 1 2 网络科学的研究特点 网络科学是专门研究复杂网络系统的定性和定量规律的- n 崭新的交叉科 学，研究涉及到复杂网络的各种拓扑结构及其性质，与动力学特性( 或功能) 之间 相互关系，包括时空斑图的涌现、动力学同步及其产生机制，网络上各种动力学行 为和信息的传播、预测( 搜索) 与控制，以及工程实际所需的网络设计原理及其应 用研究，其交叉研究内容十分广泛而丰富。 目前网络科学，不仅用数学上图论的语言、符号和理论来精确而简洁地描述， 而且以统计物理等诸多现代科学为理论基础。一般复杂网络具有如下几个特征和 研究内容n 盯： ( i ) 网络规模大，节点数可能成千上万，甚至数亿以上。网络的行为特性需要统计 处理。 ( i i ) 网络结构具有复杂性和多样( 元) 性：大多数现实世界网络结构，既非完全规 则，也非完全随机，而是随机性与确定性的两种混合结构。由于网络系统由大量子 系统或单元所组成，结构庞大而复杂。因此，复杂网络是一类最典型的复杂系统。 不仅需要应用图论、非线性一复杂性科学等现代数学理论方法进行研究，而且需要 应用和开拓现代统计物理方法( 平衡态与非平衡态理论) ，利用许多已有的科学知 识成果来深入地研究复杂网络的特殊性和普适性n 刳。 ( i i i ) 网络的节点各种各样，取决于具体研究对象，特别是涉及到非线性的动态演 化：节点之间的相互作用错综复杂，体现在权重多样性和结构的非均匀性，连接可 以是稀疏的，一个有n 个节点的具有全局耦合结构的网络的节点连接数目为 o ( n 2 ) ，而实际存在的大型网络的连接数目通常只有o ( n ) 。网络结构及其拓扑特性 是首要的研究内容。 ( i v ) 网络具有时空复杂性，可以是静态的，而通常复杂网络是动态的演化，随着空 间和时间而变化，能够展示丰富多彩的时空复杂行为。在网络生长和演化的整个 过程中一方面网络的节点不断地增加着，另一方面节点之间的连接方式和权重在 5 中国铁路撒网络研究 不断地变化，网络的拓扑特性和动力学性质随时空进行着复杂演化。如果节点是 非线性单元如混沌系统和其他特殊系统，节点之间的复杂相互作用可导致分岔、 阵发混沌、混沌，出现网络系统的动力学行为，特别是同步( 包括完全同步，广义同 步，或部分同步，或集团同步) 和时空斑图涌现等现象。非线性动态网络系统必然 会带来新的变化规律。探索这些庐山真面是极具挑战性的研究课题。 ( v ) 复杂网络存在不同的层次，既可从微观、宏观到宇观，又可从粒子、分子、生 理、生态到社会不同层次进行研究。研究复杂网络不同层次的规律将有助人类更 深刻的认识客观世界和自身的发展规律啪1 。 ( v i ) 鉴于网络科学与众多科学( 图论、统计物理、非线性理论、复杂性理论和不 同具体学科的理论) 广泛交叉，更需要在继承和发展已经有的科学成就和体系的 基础上，进行综合研究，进而才能形成和发展本学科崭新的独立的完整科学体系 n 羽。网络科学作为复杂系统的一般描述方式和规律，将为其他交叉科学的研究开 拓了新的视野，提供了全新的视角，特别是有助于深入揭示复杂系统的结构、功能 和动力学性质之间的关系，随着网络科学理论和应用研究的深入，它必将揭示客 观世界更多的奥秘，并应用于造福人类。因此，网络科学的研究成果将对探索其他 复杂系统及交叉科学具有前瞻性、启发性、指导性、应用性和推动作用：网络科 学必然在广泛的交叉研究中不断地开拓创新，在未来形成一门完整的独立的科学 体系，有着广阔的应用前景汹1 。 2 1 3 复杂网络相关研究 复杂网络研究与数学、物理科学、复杂性科学、非线性科学、计算机与信息 科学、生物科学、系统科学、社会科学等众多学科广泛交叉，引起了国内外不同 学科对网络科学的高度重视和普遍参与，它不仅将为人们提供了认识真实世界的 复杂性的全新的科学知识和视角，而且将成为改造客观世界的新的方法论和有力 武器。目前，它已成为- n 国内外最热门科学之一n k 驯。 近些年，国内外不仅召开了一系列复杂网络的专题学术会议，如，国内从 2 0 0 4 年起至今我国连续三年召开了三届“全国复杂动态网络论坛 ，“复杂系统 学术论坛”以及2 0 0 5 年一2 0 0 7 年连续三年召开“全国复杂网络会议 ，三年之内， 全国性会议一次最多参加人数超过3 0 0 人，这个规模已经与我国8 0 年代开始的 6 中国铁路加权月络研究 。全国凝聚态理论和统计物理会议一2 6 年来的发展规模相媲美，研究工作与国际 上同步进展。国际上美国、欧洲( 如。罗马会议”( 2 0 0 3 ) ) 、亚洲( 包括中国、韩 国、新加坡等) 和澳大利亚等都不断召开一系列网络会议。即使是国际非线性科 学、复杂性科学和交叉科学等各类会议上，都已经把复杂网络排在突出的位置， 成为与会者最感兴趣的最活跃的重要专题，这种总趋势正在继续迅猛发展中，推 动着网络科学的研究在不断向更高层次发展。我国国家自然科学基金委员会和科 技部门都认识到其重大意义，不仅从十五年纲要( 2 0 0 6 2 0 2 0 年) 和十一五 规划明确研究任务，而且明显地加大了基金项目、重点基金项目、重大项目和 9 7 3 项目在复杂系统或网络方面研究的资助力度口7 1 。另外，国内外已经从不同方 面发表了和出版了许多复杂网络的综述评论和专著，为进一步深入研究打下良好 基础。我国已经有一大批年轻人大量进入了这个新兴的领域，特别是许多硕士生 和博士生加入了网络科学的研究行列，选择了复杂网络的各类研究课题，出现了 生动活泼和拼搏奋进的局面。这些可喜的事实充分表明：网络科学的理论和应用 研究极富吸引力和挑战性，开辟了广阔的研究天地，有着巨大应用前景n 。 2 1 4 经典网络模型 1 随机( 无规) 图模型( r a n d o g r a p hm o d e l ) 随机网络中的节点是按照一定的随机方式连接在一起的。2 0 世纪5 0 到6 0 年代之间，匈牙利著名数学家e r d o s 和r 6 n y i 发表了一系列论文，提出和发展了随 机图( 网络) 理论，被称为经典的e r d o s - r 6 n y i ( e r ) 随机图模型n 劓。他们提出了两 个随机图模型，其一模型假定有n 个节点，每一对节点连接( 或非连接) 的概率为 p ( 或1 - p ) ，该模型称为瓯 g 瓯，是所有具有m 条边及m 条边出现的概率为 p i ( 卜p ) h 的图的集合，这里m = n ( n 一1 ) 2 是最大可能边数。e r d o s 和r e n y i 定义 的第二模型称为g n 。的相关模型，该模型是具有n 个节点，m 条边的图的集合，由这 样的n 个节点、m 条边组成的图( 网络) 共有c 箸，肛l ，2 种，构成一个概率空间， 每一个可能图出现的概率是相同的。 7 中国铁路加权网络研究 l 铂援分蠢 图2 2 随机图图示：节点的度分布相对比较均匀，节点度服从泊松分布。 e r 随机图能够反映现实世界网络的部分主要性质，然而在其它方面，随机图 的性质与现实世界网络的性质并不匹配，它的群聚系数比较低：不管它们是否有 一个公共的邻居，节点连接的可能性为p ，因此集聚系数c = p ，而且在大网络系统 规模取极限下n 叱会趋向零1 。它完全具有随机混合模式，在相邻节点的度数之间 没有相互关系，没有相通结构，因此在随机图中不能使用局域算法，而且在现实网 络模拟中也没有采用它。 2 小世界网络 1 9 9 8 年发现了小世界效应( 现象) 啪1 ，指的是小世界网络同时具有小的平均 路径距离和高的群聚系数两个特点。虽然规则网络有高的群聚系数却没有小的平 均路径距离，e r 随机图模型也有小的平均路径距离，但是缺乏大的群聚系数t 显 然这两种类型的网络都不是小世界网络，它们的特性不完全符合真实世界的小世 晃特性1 。真实世界的大多数网络是介于这两者网络之间，如图2 3 所示三种网 络，对于规则网络随机连接概率p = 0 ，而随机网络p = 1 。1 9 9 8 年w a t t s 和 s t r o g a t z 提出的小世界网络模型，简称w s 模型，介于完全规则网络和完全随机 网络之间，有一定的少量的随机连接的概率p 不为零。该模型构造方法是：从一个 规则网络开始，它是具有n 个节点的规则圆环，圆环上每一个节点与两侧各有m 条边相连，然后以连接概率p 对每条边进行随机化重连，但是必须除去自我连接 和重边，这些随机重连的边叫“长程连接，正是依靠随机地“长程连接 才大大 地减小了网络的平均路径长度，从而提高了网络的群聚系数。 8 中国铁路加权网络研究 一一磐小如界一络 帆一络 o 桊 ，- o 一，。i 图2 3 三种类型的网络结构图及其随着随机概率增加的比较图n 印 3 无标度网络 1 9 9 9 年，b a r a b d s i 和a l b e r t ( b a ) 第一个提出随机的无标度网络模型旧1 ，形成 无标度网络的主要机制有二条规则：增长性和择优性。他们通过追踪万维网的动 态演化过程，发现了许多复杂网络具有大规模的高度自组织特性，即多数复杂网 络的节点度服从幂律函数分布，这表明该网络没有特征长度，因此把具有幂律度 分布的网络称为无标度网络幽3 h 捌。在b a 模型生成的初始时刻，假定系统中已有 少量节点，在以后的每一个时间间隔中，新增一个节点，并与网络中已经存在一定 数目的不同节点进行连接。当在网络中选择节点与新增节点连接时，规定被选择 的节点与新节点连接的概率与被选节点的度成正比，人们将这种连接称为择优连 接或偏好连接。因此，新节点n 与老节点i 的随机优先连接概率正比于节点度k 大小： p 蛆一 jnl b a 网络最终演化成标度不变状态，即节点度服从度指数等于3 的幂律分布。 图2 4 示出b a 模型演化示意图和幂律分布。b a 模型的平均路径距离很小，群聚 系数也很小b 3 3 4 ，但比同模随机图的群聚系数要大，不过当网络规模趋于无穷大 时，这两种网络的群聚系数均近似零。常见的三种产生无标度特性的实际网络例 子是演员合作网，万维网和电力网删。 9 袁， 中国铁路加权网络研究 屯杯度一络 一i 。b a r a b a s i r i b e r t s c ic n c e2 8 6 5 0 9 ( 1 9 9 9 ) 图2 4b a 模型的网络增长和择优连接形成无标度特性 图2 5 无标度网络实例：美国航空网络 2 2 加权网络实证研究 最近几年复杂网络的研究在各个领域得到了蓬勃发展，但是先前的工作都只 是把实际系统抽象为无权网去进行研究，但是大多数实际系统的个体之间的相互 作用是有差异的，在抽象为网络时应该把相互作用的差异性考虑在内，即用权重 来描述这个差异性m 3 。2 0 0 1 年以来在无权网络广泛研究的基础上，有权网络很快 成为国内外复杂网络研究的最重要的挑战性的研究课题之一，不论是有权网的实 证研究，还是理论探索，都受到高度重视和广泛关注瞳。 国内外已经开展了许多实证研究，大量观察到加权网络中存在幂律分布等统 l o 中国铁路加权罔络研究 计性质。科学家合作同、移动通信网和电影演员合作网等都有比较多的研究。在 加权网络的演化模型研究上，为描述整个网络边的异质性，y o o k ，j e o n g 和b a r a b o s i 首次对有权的演化网络理论进行了探讨1 ，在无权网络的基础上，他们提出 个初步的有权网络理论模型，按照节点度之间的关系给边赋予权值而形成的有 权网络。为了更贴近实际，国内学者也提出了一些改进方法，如考虑了节点的适应 度。以一定的随机性给边赋权值：引入“适者变富”机制等。虽然这些模型揭示 了现实世界的某些重要性质，但是模型的群聚系数仍然很小，与现实并不符合。总 的来说，复杂加权网络实证研究已有很大进展，但复杂加权网络模型有待进一步 继续深入研究。 本文是加权网络的实证研究，所以对一些已有的加权网络的实证工作进行综 述。目前研究较多的加权网络包括各个学科领域，研究发现刻画不同连接的权展 示了各种不同分布和幂律行为等复杂统计特征，权和拓扑之间的相关性为观察这 类系统组织结构提供了互补的视角油5 。 生物网络：目前，细胞网络拓扑的重要性是众所周知的，细胞网络是由基因、 蛋白质和其他调节细胞行为的分子之间通过相互作用产生的复杂网络。最近研究 发现进一步的重要信息蕴含于相互作用的强度中。a l m a a s 等把e 大肠杆菌的新陈 代谢反应作为加权网络研究，其中权w ；，表示从代谢物i 到j 的流量。观察到的代谢 物体现出高度的异质性，共存的代谢物张成几个数量级：在最优生长条件下，权分 布很好地符合幂律q ( w ) 箧瓴+ w ) 吖。，其中w o = 0 0 0 0 3 ，y = 1 5 。另外发现 平均边权随两端点的度数变化即：( w 。，) ( k 。，k j ) 9 ，o = 0 1 5 障。在全部流 量分布中观测到的大量异质性也存在于低层次的代谢物个体。对于有利于琥珀酸 盐和谷氨酸盐吸收的e 大肠杆菌的代谢，研究发现其入度和出度都服从( k ) k 一 0 2 7 。这是位于y ( k ) = 常数和y ( k ) k q 这两种极端中间的情况，表明消耗( 生产) 给定代谢物的反应数目越多，单独反应携带大多数代谢物的情况越有可能。 t i e r i 等把人体免疫系统细胞之间的通讯作为有向加权网络来研究，其中点 是不同类型的细胞，权w 。，等于细胞i 分泌的且影响细胞j 的不同可溶性介质的数 目。结果表明免疫细胞构成高度异质网络，其中只有少数可溶性介质在作为不同 类型细胞间反应的媒介起着中心的作用哺1 。 社会网络：合作网是目前拥有广泛数据库的社会网络。科学家合作网类似于 中国铁路加权同络研究 电影演员合作网，由科学家构成，其中节点代表科学家，如果两位科学家合著一 篇文章则两个节点之间有边相连即两人之间存在相互作用。在b a r a b a s i 汹瑚1 等人 关于合作者网络的动态演化性质的研究工作中，他们选择了数学和神经科学领域 的科学家网络作为研究对象。首先文章以年为时间单位讨论了顶点( 即研究者) 数随时间演化情况，总文章数随时间演化情况。然后讨论了度分布的时间演化稳 定性以及平均度值随时间的变化，并且统计了不同时间点的网络的平均最短距离 和平均集聚程度，做了演化曲线。随后对网络最大集团的相对大小也做了随时演 化行为的分析。在这两个网络中平均最短路径长度分别为d 越。= 9 5 和d 。；= 6 ， 集聚系数分别为c = 0 5 9 和c 。耐= 0 7 6 ，度分布服从幂律分布，其度指数分别 为r 盥。= 2 1 和、r o i = 2 5 。不过在这两个网络中没有考虑科学家之间的相互作 用强度，只是看做无权网来研究的。 n e w m a n m l 在五年内研究了四个数据库，涉及物理、生物医学研究，高能物理 学和计算机科学领域。所有这些网络都显示出平均路径长度小，但集聚系数大的 特性。高能物理学合作网络的度分布几乎完全符合幂律分布，而其他领域的度分 布在其尾部具有较大指数的幂律分布。n e w m a n 还在文章中提出了一个在科学家合 作网中如何区分科学家之间合作强度的方法，第一步假定在一篇文章中共有n 个 作者，则第一作者就有n 1 个合作者，并假定第一作者和每个合作者的合作次数 为1 ( n 一1 ) ，即在n 一1 个合作者之间平均分配他的工作时间：然后假定有过多次 合作的科学家之间比只有少量合作次数的科学家之间更加了解，为了描述科学家 之间的熟悉程度把每对科学家在不同的文章中的合作强度累加到一起。如果科学 家i 是文章k 中的一个合作者则甜= l ，否则祥= o ，w 。，代表科学家i 和科学家j 之间 的合作强度 p6 ：6 ： w ：f = 莉 - 1 1 ) 在合作强度的基础上可以定义任意两个科学家之间的距离为d ；j _ 1 w 然后 就可以计算加权的科学家网络的平均最短距离。 利用n e w m a n 提出的权的定义，b a r r a t 等研究了n = 1 2 7 2 2 位在1 9 9 5 年至1 j 1 9 9 8 年之间给凝聚态物理提交论文草稿的科学家的相互关系网络1 。实证观察得到分 1 2 中国铁j 苔加权月络研究 布r ( s ) 和p ( k ) 都是重尾的。权与拓扑结构无关，这是由于平均强度s ( k ) ( 作为度 数k 的函数) 表现出当拓扑上的权是随机分布时所体现出的线性行为s ( k ) = ( w ) k 。集聚系数的统计表明拥有少数合作者的作者比度数大的作者更可能在一个工 作组内，组内所有的科学家都互相合作。在度大于1 0 时，加权聚集系数c ( k ) 比无 权聚集系数c ( k ) 大。这意味着有许多合作者的作者趋于与其它相关合作组的作者 合作发表更多的文章，这可以解释为：有影响的科学家组成稳定的研究组就能产 生大量的文章。无权相关性k 。( k ) 和加权相关性k 。( k ) 都随着k 呈幂律增长，表 明此网络展示了社会网络的典型特征同类匹配性n 1 3 。 国内北京师范大学复杂性研究中心的李梦辉、狄增如等人研究了经济物理学 科学家合作网络：8 1 9 作者，8 0 0 多篇文章。他们将科学家合作网抽象成加权有向 网络的静态网络，以三种相互作用方式进行加权：合著、引文、讨论，作用的强 度w 。，为：次数。其结果也表明点权的分布符合幂律，加权后的网络兼有小世界和 无标度特征哑1 。 技术网络：重要的基础网络( 如因特网、铁路、地铁和航空网络) 中有关交通 通讯的流量可以很自然地用权来表示。b a r r a t 等嘲视世界航空网为加权网进行 了分析，权w 。，为由飞机场i 直达机场j 的航班的有效座位数。和从不同数据库所观 察的结果一样，拓扑图展示出了小世界和无标度属性。特别地，度分布形式为p ( k ) = k - , f ( k k 。) ，其中y 2 0 ；f ( k k 。) 是指数断开函数，原因是单个机场能提 供的最大数目连接的实际限制。 点的强度为s 的概率是重尾的，且权与度之间存在非平凡关联：边的平均权和 两端点的度数之间关系为( w 。，) = ( k l k ，) 。且指数e = o 1 5 侣羽。度数为k 的点的强 度服从幂律分布s ( k ) a k 8 且指数1 3 = 1 5 l 。这表明机场越大，可处理的运输 量越大。考虑聚集系数和平均最近邻度数，世界航空网的加权分析提供了比科学 合作网更丰富的情节。在k 的整个取值范围上，加权聚集系数c 。( k ) 有更多有界变 化。这意味着度数高的机场间易形成具有高运输量的相关组以平衡减少的拓扑聚 集。由于高流量连接在网络中枢上，所以有高度数的点趋于和具有同样度数或更 高度数的点结成派系的现象，称为“富人俱乐部现象 。拓扑k 。( k ) 只在小度数 情况下表现同类匹配性。k 1 0 时，k 。( k ) 逼近一个常数，揭示了一个无关联结 构( 即度数不同的点有相似的邻居) 这一事实。倘若另一不同网络，高度数的机场 1 3 中国铁路加权网络研究 对其他大型机场( 大部分交通流是有向的) 的亲和力较大，网络加权k - 。( k ) 分析 展示了在k 的全部变化过程中显著的相称性。 g a n e s hb a g l e r h 钔分析了印度航空网，包括7 9 个机场和4 4 2 条有向的航线，并 且把机场间的航线数作为网络中连接的权重，印度航空网的度分布以及边权分布 均具有幂律分布的特征，并且具有小世界网络的特征，平均最短路径长度为d = 2 2 5 9 3 ，集聚系数为c = o 6 5 7 4 。 国内的李炜等嘲1 研究了中国的航空网络，其中包括1 2 8 个机场和1 1 6 5 条航线， 他把整个中国航空由周一到周日划分为了七个具有相同的节点而连接不同的子 网，把机场间的航班数作为该连接的权重参数。 2 际n e t 2 l 2 n i j t 是机场i 和j 之间在第t 天的航班数。中国航空网的度分布和航线上的权分 布的累积分布都符合幂律分布，而整个航空网的集聚系数都不小于0 5 7 6 。 近几年关于加权网络的研究工作发展迅速。2 0 0 6 年b o c c a l e t t i 等在p h y s i c r e p o r t s 上发表了最新的关于复杂网络研究的综述文章，在该文的引言中提到， 对加权网络研究的进展是他们编写新的综述文章的动因之一咖3 。目前对加权网络 的研究工作主要集中在网络静态统计性质、网络上的物理模型和网络演化等几个 方面。关于加权网络静态统计性质的研究，主要关注在引入权重以后网络几何量 的定义和实证分析等方面的工作n 钔。 1 4 中国铁路加权罔络研究 第三章加权网络的统计性质 为了刻画复杂网络全面性质，科学家已经提出了复杂网络的许多基本概念、 特征量和度量方法，用于表示复杂网络的拓扑结构特性和动力学性质。基本概念 和主要特征量包括：节点度分布、强度分布和边权分布，群聚系数和平均路径长度， 这些是最重要的特征量。另外，网络还有其它特征量，如：介数及其分布、最大连 通分支的规模分布、度一度关联性( 相称性系数) 、群聚度关联性、模块性等啪1 。 本文主要计算的是加权网络的强度分布、群聚系数和平均路径长度。 3 1 边权的赋予方式 把一个实际系统抽象为加权网络的过程并不都是平庸的，因此，加权网络研 究面对的第一个问题就是边权的赋予方式。边权代表个体间相互作用的强度，既 有现实存在的物理权重，也有抽象权重。当实际问题中存在物理权重时，如电阻 网络边上的阻值、i n t e r n e t 网络的带宽、邮递员问题中的距离关系、航空网络 中的里程和座位数以及化学反应网络中的反应速率等等，问题相对容易处理一 些，直接把相关物理量看作边权即可，但是对于其他包含相似关系、亲密程度等 社会关系的网络，就需要把两点间相互作用的某种属性转化为权重。尤其是当系 统中包含多个层次的相互作用关系的时候，就必须仔细研究其加权方式了啪1 。 权重原则上应分为相异权( d i s s i m i l a r i t yw e i g h t ) 和相似权( s i m i l a r i t y w e i g h t ) 两种。相异权与传统意义上的距离相对应，权值越大表示两点间的距离 越大，关系越疏远；而相似权则恰恰相反，权值越大表示两点间的关系越亲密， 距离越小u 钔。 3 2 加权网络上的统计量 加权网络可以由集合g ：( n ，w ) 描述，包括n 个节点，以及一组带有权重 1 5 中国铁路加权网络研究 的边w ；通常可以用加权邻接矩阵w 表示加权网络，其中矩阵元w ( 眠， 0 ) 代 表相邻两点间的边权。通常情况下，相似权w 。， 0 ，) ，如果w ；，= 0 ，则表示 两点之间无连接；而相异权w ；。( o ，) ，w ；，= o o 时相当于两点间无连接。当 每一条边的数值都是一样时，可以将其归一化为1 ，加权网就退化成无权网，即 无权网是加权网的特例。在以下讨论中，仍将采用邻接矩阵a 描述与加权网络对 应的无权网( 顶点i ，j 之间有边存在时a 。，= 1 ，否则a 。，= 0 ) 。显然，加权网 络有一个特殊的统计特征：边权分布p ( w ) ，即任取一条边时，改变的权重为w 的概率。下面介绍一些加权网中与无权网相对应的物理量和统计性质。 3 2 1 点强度，强度分布，单位权和差异性 在加权网中，与节点度k 。相对应的自然推广就是点强度或点权s 。船羽，其定 义为： s i 一嘞 ( 3 2 1 ) 1 j n t 其中n 。是节点i 的近邻集合。点强度既考虑了节点的近邻数，又考虑了该 节点和近邻之间的权重，是该节点局域信息的综合体现。当边权与网络的拓扑结 构无关时，点强度与度的函数关系一般为s ( k ) 帐，其中 为边权的平均 值。当边权与拓扑结构具有相关性时，点强度与度的函数关系一般为s ( k ) a k 9 ， 或者b = 1 但a ，或者b l 。在点权的基础，还可以引入单位权( u n i tw e i g h t ) u i 4 0 ，对顶点的连接和权重情况做更细致的刻画，单位权定义如下： 所2 i 2 2 ) 表示顶点连接的平均权重。但是，即使顶点具有相同的度值和点强度，单位权相 同，也可能会情况迥异。例如，在单位权相同的情况下，可能是每条边的权重都 接近于单位权u ；的的数值，也可能是一条边或少数几条边上的权重处于优势。 顶点所连接的边上权重分布的差异性( d i s p a r i t yi nt h ew e i g h t ) 可以用y ；表 示蜘： e = 磊c 詈，2 2 1 6 中国铁路加权网络研究 其中n ，是节点i 的近邻集合。由上面的定义可知，y 。描述了与顶点i 相连的边上 权重分布的离散程度，且依赖于节点的度值k ；。对于顶点i 的k 。条边，如果所 有权重值