基于复杂网络的道路网拓扑结构信息度量-张红.pdf

《基于复杂网络的道路网拓扑结构信息度量-张红.pdf》由会员分享，可在线阅读，更多相关《基于复杂网络的道路网拓扑结构信息度量-张红.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第33卷第2期2017年3月地理与地理信息科学Geography and Geo-Information ScienceV0133 No2March 2017doi：103969jissn16720504201702 001基于复杂网络的道路网拓扑结构信息度量张红1，何晶12，杨婕1，吴荣光1，曾映敏1，吴殉1(1西南交通大学地球科学与环境工程学院，四川成都611756；2南宁市国土测绘地理信息中心，广西南宁530021)摘要：地图是空间信息传输的重要工具，地图拓扑结构信息的有效度量对地图更新、多尺度表达、制图综合等十分重要。信息熵已被用于描述地图信息，但对地图拓扑结构信息熵的研究多局限于单一

2、层次或尺度，缺乏系统、多层次、多尺度刻画地图结构复杂性的方法。该文以道路网为例，基于复杂网络理论，从整体与局部两个层次，考虑网络的集聚性、连通性、可达性及邻域完整性特征，构建地图拓扑结构信息熵指标，将其用于不同模式道路网及其对应同等规模的随机网络的结构特征定量描述。结果表明该方法能揭示道路网内在的小世界与无标度网络结构特征，并可有效刻画不同模式道路网的结构差异，可用于制图综合、多尺度表达、地图更新设计等。关键词：道路网；拓扑结构；信息熵中图分类号：P208 文献标识码：A 文章编号：1672-0504(2017)02-0001-060引言地图是空间信息传输的重要工具，也是对现实世界的抽象再现。

3、地图要素的选择及其组合方式在某种程度上决定了地图所传达的信息量的多少1。地图有时还需不断更新以满足用户对现势性的要求。而何时更新、怎样更新以及更新结果是否满意等问题均依赖于对地图所含信息量的准确测度2。分形可有效描述随观测尺度的变化，地理要素宏观结构的动态变化，以及地理要素本身细节的微结构动态变化，因此，分形学已被用于地图信息定量评估及自动化制图综合3。除分形以外，Shannon所提出的信息熵4，也被广泛用于地图综合效果的评估5。但该方法仅统计了符号数量，忽略了地图最本质的空间位置特征信息。随后，Neumann提出了基于地图符号邻接关系的拓扑信息熵6。Bjoke进一步考虑了地图符号的邻近关系、

4、分布位置和顺序等特征，提出了拓扑、几何与位置信息熵7。Li等8认为地图信息既包括统计信息，也包括几何信息、拓扑信息和专题信息，进而提出了基于Voronoi图的地图信息熵度量方法。这也是现有的对地图信息的最佳量测方法9。刘慧敏、Mohajeri、韦丽丽等将其分别应用于等高线、道路网、城市地图的信息度量中10叫2|。颜言等13则探讨了不同性别地图使用者在电子地图信息传输过程中的认知差异，李志林等更系统梳理了地图信息论的发展历程，并指出其发展方向L1J。经过近50年的发展，地图信息论已成为现代地图学的一个核心研究领域。遗憾的是，当前对地图信息的研究多局限于语法层次(即地图上地物或现象的时空状态与组合

5、的存在方式)，而对于其语义信息(即此种组合存在方式的含义)的研究涉及较少1。同时，现有对地图信息的探讨多局限于单一尺度或层次，缺乏系统、多层次、多尺度描述地图信息的指标或方法。本文使用复杂网络分析方法，从全局与局部两个层次，综合考虑网络的连通性、可达性、邻域完整性及集聚性特征，构建地图拓扑结构信息层次化度量指标，用于区分不同网络。1地图拓扑结构信息的组成与度量指标11地图拓扑结构信息的构成分析地图的拓扑结构特征可从全局和局部两个层次进行刻画。在全局层次上，重点关注网络的集聚性特征，因其直接反映出地图要素两两间关联或邻近的程度；在局部层次上，地图拓扑结构特征可通过节点的连通性、可达性和邻域完整性

6、特征来刻画。它们分别对应于与某要素直接关联或邻近的要素数目、某要素在给定范围内(通常取3步长范围)能关联到的其它要素的数目、某要素的邻域间彼此关联或邻近的可能性(表1)。12地图拓扑结构信息的度量指标现有信息熵度量方法多基于Shannon信息论，收稿日期：201606一18；修回日期：2016_1118基金项目：国家自然科学基金面上项目“基于结构特性的数字地图多尺度表达研究”(41471383)；国家自然科学基金青年基金项目“基于复杂网络理论的道路网自组织结构和协同生长机理研究”(41101361)作者简介：张红(1981一)，女，博士，副教授，研究方向为空间分析、制图综合。Email：zha

7、ngh2011swjtueduca万方数据第2页 地理与地理信息科学 第33卷表1地图拓扑结构信息层次化度量指标及含义Table 1 Measurements and meanings for quantifying the topologicalstructural information of a map层次描述角度 描述指标连通性 度值局部 可达性 深度值邻域完整性 集聚系数全局 集聚性 平均最短路径网络特征含义与某节点直接相连的节点总个数某节点3步长范围内所能到达的其它节点总个数某节点的直接邻域结构完整性程度从某节点到其它所有节点所需的最短路径的平均值即信息是事物运动状态或存在方式的不

8、确定性描述4。信息熵刻画的正是事物的这种不确定性程度，公式为4：H(p)一一蚤Alog(p：) (1)式中：Pi为第i个随机事件发生的概率，REp：一1。(1)连通性信息熵。网络中节点的连通性程度通常用度值(与某节点直接相连的其它节点数目)k描述，公式为：k；一SA。 (2)J；1。式中：若节点i与歹问存在连线，则Ai一1；反之，A4一O。节点的度值体现了该节点与周围节点问联系的紧密程度，一定程度上反映出该节点的重要性。节点i的连通性信息熵为：Hti=-惫k(轰) 忌i 、二岛7式中：行为节点总个数。整个网络的连通性信息熵等于各节点连通性信息熵之和，即：Hk=取一蓦(麦1092(轰) i一一(

9、l百J) (4)P 2 z=、V L 、)： 7，(2)可达性信息熵。网络中节点i=lHk10921I的k可达性特征通过节点的深度值来刻画。节点i的深度值d乡：等于节点在给定拓扑距离范围内所能到达的节点总个数，通常取拓扑距离为3，公式为：地一蚤M (5)式中：N；为当S一1拓扑距离s时，节点i所能到达的其它节点的数目。显然，节点i的d夕i值越大，表明节点i在局部层次上影响的节点越多。节点i的可达性信息熵可表示为：。一轰dp b(羡) 。 ， 、兰d户i 7同理，整个网络的可达性信息熵等于各节点可达性信息熵之和，即：一跳一耋(羲崦z(美)(3)邻域完整性信息熵。度值和深度值仅考虑了单个节点在给定

10、步长范围内与其它节点连通的能力，忽略了节点邻域间的连接情况。集聚系数CC是描述节点邻域完整性的重要指标，数值上等于与某节点直接相连的节点(称为节点i的邻居)之间存在的实际连线数与所有可能的连线数的比值。CC的最大值为1，表示与某节点直接相连的所有节点彼此间也都相连；cc：O则表示与节点i直接相连的所有节点彼此均不相连。节点的集聚系数为：一最 式中：Ei为节点i的邻居之间实际存在的连线数；k为节点i的度值。对应地，节点i的邻域完整性信息熵为：K一景CC。(麦) i 、互7iI 4整个网络的邻域完整性信息熵等于各个节点邻域完整性信息熵之和，公式为：H。一H。 圣(最CC蛔。(菱)_1。 、兰7Il

11、 。(10)(4)集聚性信息熵。平均最短路径长度s乡为网络中某节点到其它所有节点的最短路径的平均值。该指标在全局意义上直接刻画了各节点与其它所有节点彼此间联系的紧密程度或集聚程度。节点i的s户值越小，相对于其它节点而言，它在整个网络中的集聚能力就越强。节点i的邻域完整性信息熵为：Hspi=_轰sp魄z(羲) ， ， 、苫sA 7整个网络的集聚性信息熵等于各个节点集聚性信息熵之和，公式为：一轧一耋(羲啦(蠡)，(5)拓扑结构信息熵的标准化。为消除网络规模对计算结果的影响，需对各原始信息熵进行标准化处理。根据Shannon信息熵的性质，当九个事件等概率出现(即P：一)时，信息熵达到最大值。即：x一

12、一蚤A1。92Pi一-蚤音1。gz(音) (13)使用文献E14中所提出的方法对信息熵进行标准化处理：耳一HHT。， (14)2 道路网拓扑连通关系对偶图及其对应的随机网络图的构建考虑到道路网形态与模式的差异，本文共收集万方数据第2期 张红，何晶，杨婕，等：基于复杂网络的道路网拓扑结构信息度量 第3页了北京、成都、重庆、纽约曼哈顿和莱克星顿5座国内外城市道路网数据(图1)。其中，纽约曼哈顿呈狭长格网状；重庆地形复杂，道路破碎化程度较高，道路网呈自由式；北京受历史、政治和地形的影响，路网呈格网状和环形(长方形)放射状；成都道路网与北京道路网类似，呈环形(偏圆形)放射状，局部格网状填充；而莱克星顿

13、道路网为格网状、星状与环状的混合，一条近似圆形的道路蜿蜒穿越整座城市的外围。(a)北京 l b)成都 r)重厌 (d)纽约曼冶顿 (ej采克星顿图1 5座城市的样本道路网Fig1 Five sampled urban road networks21路划及其拓扑连通关系对偶图 街道段连接、合并成的一条较长的道路。如图2所当前道路网结构表征方法多样，包括街道段、路 示，图2b为以60。作为拐角阈值时提取的路划地图；划、命名的街道等多种。其中最常见的是路划1 5|，它 图2c为基于路划的道路网拓扑连通关系对偶图，其是基于Gestalt认知原则中的认知连续性原则，根据 中的节点表示路划，节点间的连线表

14、示对应的两条事先设定的拐角阈值(通常为30。70。16)，将相邻 路划彼此交叉。a)原始的街道段地图 (b)路划地图 (c)拓扑连通关系对偶图图2基于街道段地图提取的路划及其拓扑连通关系对偶图Fig2 An illustration of the derivation of strokes from road sepnents and its dual graph of topologic connectivity relationships22道路网结构特征描述和随机网络的生成如前所述，可从全局与局部两个层次描述网络的结构特征。例如，通过总的节点个数和连线条数概述网络的规模，通过特征路径长度

15、(即网络中任两个节点间最短路径长度的平均值)刻画网络的紧密性。此外，还可根据网络中所有节点的度值是否符合幂律分布分析其无标度特性和异质性1 6I。当一个网络同时具有规则网络较高的集聚系数值和随机网络的较短的平均路径长度时，该网络为小世界网络1 7|。为进一步揭示真实道路网的结构特陛，使用Pajek软件18生成了与各道路网路划拓扑连通关系对偶图相同节点总数的4类随机网络，即无标度、小世界、泊松和完全连通网络。各随机网络在生成时需要输人一些参数值。例如，无标度模型需要输入节点总个数、连线总条数、节点平均度值、初始连线概SIO率、幂律分布系数值等；而小世界模型则需输入节点总个数、节点两侧连向的节点数

16、目、断链重连的概率等；泊松分布网络需考虑节点总个数及节点的平均度值。将表2所示的真实道路网中的有关特征值作为参数值输入，并不断调整其它参数数值，以得到与真实道路网特征最为接近的随机网络。对于完全连通图，仅节点个数与真实道路网一致，每个节点均与其它所有节点直接相连。3道路网拓扑结构信息度量方法的有效性评估下文将从两方面评估连通性、可达性、邻域完整性及集聚性拓扑结构信息熵的有效性。一方面，可比较道路网的结构信息熵及其对应同等规模的随机网络的结构信息熵，判断结果是否能反映出基于路划的道路网内在的小世界与无标度特征1 7|。另一方万方数据第4页 地理与地理信息科学 第33卷表2 5座城市道路网及其对应

17、的同等规模的随机网络的网络特征值Table 2 Network parameters for reallife road networks and their corresponding random networks真实道路网 3 310 5 074 3066 0248 5699 269随机一无标度网络 3 310 5 028 3038 0006 5473 308莱克星顿 随机一泊松网络 3 310 4 971 3004 000085 7224 一随机一小世界网络 3 310 6 620 4000 0015 6059 一塞全连适圈鳖 !；! i!i! i i! !：!塑 !：!塑 =面，可直

18、接比较不同形态和模式的道路网结构信息熵的差异，看其是否能揭示道路网间的结构差异。5座城市道路网及其对应的随机网络的标准化结构信息熵如表3所示。表3 5座城市道路网及其对应的随机网络的标准化结构信息熵Table 3 The standardized structural entropies of five urban roadnetworks and their corresponding random networks31道路网与对应的随机网络的拓扑结构信息熵的比较将5座城市道路网的结构信息熵与其对应的同等规模的随机网络的拓扑结构信息熵进行比较，排序结果如表4。由表4可知，对于4类信息熵而言，

19、5座城市道路网与随机网络比较的结果几乎呈完全相同的趋势。例如，对于可达性信息熵，均有道路网无标度泊松小世界完全连通。在4类随机网络中，5座城市道路网均与无标度网络最为接近，这表明道路网具有无标度网络的一些结构共性，如度值的高异质性、不同度值节点连接的多样性等。此外，大部分城市道路网的连通性、可达性和集聚性信息熵均低于各随机网络，意味着道路网在连通性、可达性和集聚性方面倾向于更加无序、多样，这与现实道路网等级层次不断加强、通过修小路来增加捷径、不断修建不同级别的交通枢纽、强化中心与中心、中心与外围间连接的趋势相吻合。对于邻域完整性信息熵而言，道路网的邻域完整性信息熵较高，仅次于完全连通网络，且与

20、小世界网络的指标值最为接近，这与大量研究揭示出的真实道路网的小世界特性结论一致1 6J。同时表明在5个城市道路网中，无论路划所处位置如何，各路划的局部连通程度都较好。这可能是因为道路网中普遍存在跨等级的捷径，即高等级的道路同时与高等级和较低等级的道路相连。万方数据第2期 张红，何晶，杨婕，等：基于复杂网络的道路网拓扑结构信息度量 第5页表4 5座城市道路网及其对应的随机网络的拓扑结构信息熵比较Table 4 The ranking orders of structural entropies of five urban road networks and their corresponding

21、 random networks综上，与4种随机网络的结构信息熵相比较，道路网在连通性、可达性及集聚性特征方面与无标度网络相近，在邻域完整性特征方面更接近于小世界网络。这与现有研究发现的大量现实道路网所具有的小世界、无标度特征一致，从侧面验证了结构信息熵在刻画道路网结构特征方面的有效性。32 不同模式道路网拓扑结构信息熵的比较由信息熵的定义可知，信息熵值越大，说明网络某方面结构特征的数值分布越均匀；信息熵值越小，说明网络某方面结构特征值的分布越异质。表5列出了对5座城市道路网信息熵排序的结果。表5各城市道路网的拓扑结构信息熵排序结果Table 5 The ranking order of st

22、ructural entropy of urban road netwods可达性 莱克星顿重庆北京成都纽约曼哈顿邻域完整性 莱克星顿成都重庆纽约曼哈顿北京集聚性 纽约曼哈顿成都重庆一莱克星顿北京：垦堑堕塑垡宣煎 重压S盛叠SjI塞S堑垫星堕堡S苤塞星堡在连通l生信息熵方面，自由式的重庆道路网的连通性信息熵值最高，表明其路划的度值的分布最为均匀，而格网状的纽约曼哈顿道路网连通性特征差异最大。这与实际情况一致。纽约曼哈顿呈狭长带状，其内部发育的方格式道路网，在东北一西南走向上易形成度值较高的路划，而在西北一东南走向上的路划度值则普遍较低。重庆市是典型的山城，道路曲折蜿蜒，路网发育破碎，难以发育较

23、高级别的路划，大多数路划的度值较接近，故其连通性信息熵值最高。在可达性信息熵方面，纽约曼哈顿道路网拥有最高的可达性信息熵值，而莱克星顿最低。这说明格网状道路网中路划的可达性数值分布最为均匀。事实上，在规则格网中，从任一条路划出发，经过o3次中转，所能到达的其它路划的数目非常接近。而莱克星顿的道路网同时发育有格网状、星状和环状路划，其中一条近似圆形的环状和从中心发散出的树状路划形成了全局意义上的“捷径”，并由此导致路划3步长范围内能到达的其它路划条数有别于局部格网状道路，即路划深度值的数值更加多样、不均匀。同理，对于邻域完整性信息熵而言，莱克星顿和成都道路网的数值最低，环形放射状的北京道路网的邻

24、域完整性熵值最高，自由式的重庆道路网熵值居中。邻域完整性信息熵的计算基于集聚系数，描述的是与某路划直接交叉的其它路划彼此间连通的可能性。显然，格网状道路更易于路划彼此间交叉连通形成闭合单元，从而各路划的集聚系数值都普遍较高；而环状和树状更难使得路划间交叉连通，其路划的集聚系数值分布较不均匀。从表5可知，5座城市道路网的集聚性信息熵几乎相等，差值在00012以内，说明各路网中，从任一路划到其它各路划都非常方便，这或许与真实道路网所具有的小世界与无标度特征相关1 6。4结论与展望信息熵已被引入地图学，并成功用于地图信息定量描述及地图更新。当前对地图拓扑结构信息熵的研究较少，多局限于单一尺度或层次。

25、本文使用复杂网络分析方法，从全局和局部两个层次，定义了网络集聚性、连通性、可达性及邻域完整性信息熵指标。以道路网为例，计算了5座现实城市道路网及其对应的随机网络的结构信息熵。对信息熵计算结果的比较表明，本文所提出的4类信息熵可反映出现实道路网的小世界和无标度特征，并能有效区分不同模式道路网的结构差异。本文提出的方法也可拓展用于其它单要素和多要素地图的信息量算。将拓扑结构与几何、语义等其它类型信息熵相结合，可用于制图综合、多尺度表达、地图更新质量控制等。此外，信息熵随尺度变化的规律也值得探讨。参考文献：1李志林，刘启亮，高培超地图信息论：从狭义到广义的发展回顾口测绘学报，2016，45(7)：7

26、57767万方数据第6页 地理与地理信息科学 第33卷23陈惠荣，谭美景，郑义东，等基于变化信息量的海图改版需求评估口海洋测绘，2010，30(3)：67693IVR)LLER J C Fractal end automated line generalizationJ1TheCartographic Journal，1987，24(1)：27344SHANNON c E A mathematical theory of communicationJThe Bell System Technical Journal。1948(27)：379423，6236565 SuKHOV V L Appl

27、ication of information theory in generalization of map contentsJInternational Yearbook of Cartography，1970，10(1)：41-476NEUMANN JThe topological information content of a map：An attempt at a rehabilitation of information theory in cartographyJCartography，1994，31(1)：263473 BJDKE J T-Framework for entro

28、py-based map evaluationJCartography and Geographical Information Systems，1996，23(2)：78958LI z L，HUANG P ZQuantitative measures for spatial informarion of mapsJInternational Journal of Geographical Information System，2002，16(7)：6997099张辉地图信息度量的方法及其应用J测绘与空间地理信息，2010，33(3)：236239103刘慧敏，邓敏，樊子德，等地图信息度量方法

29、及其应用分析Jl，地理与地理信息科学，2012，28(6)：1611 MOHMERI N，FRENCH J R，BATTY MEvolution and entropy in the organization of urban street patternsJAnnalsof GIS，2013，19(1)：11612韦丽丽，罗绍辉地图变化信息量评价模型在地图更新中的应用J。城市勘测，2014，2(1)：666913颜言，龙毅，沈倩茹，等顾及性别差异的电子地图空间认知分析J地理与地理信息科学，2011，27(4)：4851141 WANG S，DU Q，WANG Z A quantitative

30、 measurement approach for metric information of maps based on spatial cognitionAInternational Conference on Natural ComputationcIEEE Computer Society，2008235-239isl THoMs0N R CRICHARDSON D EThe good continuationprinciple of perceptual organization applied to the generalization of road networksA1Proc

31、eedings of 19th InternationalCartographic ConferenceCOttawa：ICA，199912151223161 ZHANG H Uncovering Road Network Structure Through Cornplex Network AnalysisDHong Kong：The Hong Kong Poly-technic University，201017JIANG B，ZHAO S J，YIN JJSelf-organized natural roads forpredicting traffic flow：A sensitivi

32、ty studyJJournal of Statistical Mechanics：Theory and Experiment，2008，2008(7)：P07008181 DE NOOY W，MRVAR A，BATAGELJ VExploratory SocialNetwork Analysis with Pajek：Revised and Expanded SecondEditionMNew York：Cambridge University Press，2011Quantitative Measurements oil Topological Structural Information

33、of Road Networks Based on Complex Network AnalysesZHANG Hon91，HE Jin91”，YANG Jiel，WU Rong-guan91，ZENG Yingminl，WU Xunl(1Faculty of Geosciences and Environmental Engineering，Southwest Jiaotong University，Chengdu 611756；2Nanning Land Resources Center of Surveying，Mapping and Geoinformation，Nanning 530

34、021，China)Abstract：Map has been thought as one of the most powerful tools to transmit spatial informationThe development of effectivemeasurements for describing the topological structural information of a map is very important to map updates，the multi-scalerepresentation，map generalization etcEntrop

35、y has been found to be a valid way to quantitatively describe the information of amapHowever，current studies on the topological structural information are limited to one level or a single scaleThere is a laekof approaches which can accurately describe the structural information of a map in a systema

36、tical，multilevel and multiscaleway,Taking road networks as an example，this paper comprehensively considers the structural properties of networks includingclustering，connectivity，accessibility and completeness of node neighbors with the help of complex network analysesFour kindsof measurements of ent

37、ropy have been developed and been applied to measure the structural properties of road networks of diverse patterns and the random networks of the same sizes as corresponding road networksResults indicate that approaches developed in this paper carl reflect the internal small-world and scale-free pr

38、operties of road networksThey can also depict thestructural differences between networks with different patternsThe four kinds of topological structural entropies we proposedcan be further applied to map generalization，multi-scale representation，design of map update etcKey words：road network；topological structure；information entropy万方数据