留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

加权网页排序算法在道路网自动选取中的应用

马超 孙群 陈换新 徐青 温伯威

马超, 孙群, 陈换新, 徐青, 温伯威. 加权网页排序算法在道路网自动选取中的应用[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1159-1165. doi: 10.13203/j.whugis20160127
引用本文: 马超, 孙群, 陈换新, 徐青, 温伯威. 加权网页排序算法在道路网自动选取中的应用[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1159-1165. doi: 10.13203/j.whugis20160127
MA Chao, SUN Qun, CHEN Huanxin, XU Qing, WEN Bowei. Application of Weighted PageRank Algorithm in Road Network Auto-selection[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1159-1165. doi: 10.13203/j.whugis20160127
Citation: MA Chao, SUN Qun, CHEN Huanxin, XU Qing, WEN Bowei. Application of Weighted PageRank Algorithm in Road Network Auto-selection[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1159-1165. doi: 10.13203/j.whugis20160127

加权网页排序算法在道路网自动选取中的应用

doi: 10.13203/j.whugis20160127
基金项目: 

国家863计划 2012AA12A404

国家自然科学基金 41571399

国家自然科学基金 41201391

国家自然科学基金 41071297

国家自然科学基金 41201469;

地理信息工程国家重点实验室自主研究课题 SKLGIE2018-ZZ-7

详细信息
    作者简介:

    马超, 博士, 主要从事多源空间数据融合处理与数字地图制图研究。jielong018@126.com

  • 中图分类号: P208

Application of Weighted PageRank Algorithm in Road Network Auto-selection

Funds: 

The National High Technology Research and Development Program (863 Program) of China 2012AA12A404

the National Natural Science Foundation of China 41571399

the National Natural Science Foundation of China 41201391

the National Natural Science Foundation of China 41071297

the National Natural Science Foundation of China 41201469;

the Open Fund of the State Key Laboratory of Geo-information Engineering SKLGIE2018-ZZ-7

More Information
    Author Bio:

    MA Chao, PhD, specializes in the multi-sourced spatial data fusion and digital mapping. E-mail:jielong018@126.com

图(7) / 表(2)
计量
  • 文章访问数:  1384
  • HTML全文浏览量:  99
  • PDF下载量:  344
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-09-14
  • 刊出日期:  2018-08-05

加权网页排序算法在道路网自动选取中的应用

doi: 10.13203/j.whugis20160127
    基金项目:

    国家863计划 2012AA12A404

    国家自然科学基金 41571399

    国家自然科学基金 41201391

    国家自然科学基金 41071297

    国家自然科学基金 41201469;

    地理信息工程国家重点实验室自主研究课题 SKLGIE2018-ZZ-7

    作者简介:

    马超, 博士, 主要从事多源空间数据融合处理与数字地图制图研究。jielong018@126.com

  • 中图分类号: P208

摘要: 针对现有算法在计算道路网节点重要度时忽略节点间的相互影响以及道路密度引起的重要度异常等问题,提出了一种基于加权网页排序算法的道路网自动提取方法。首先将道路连接成路段,以路段为网络节点,道路交叉作为节点连线,路段长度作为边的权重,将道路网抽象成有向有权图;然后利用加权网页排序算法计算有向有权图节点的重要度,并利用链接作弊检测的方法修正由道路密度引起的节点重要度异常,得到道路节点的最终重要度排序,从而完成道路网的提取。通过真实路网数据进行实验分析,结果表明,相对基于网络中心性的方法,该算法的提取结果能够更好地保留原始路网的密度差异和整体结构。

English Abstract

马超, 孙群, 陈换新, 徐青, 温伯威. 加权网页排序算法在道路网自动选取中的应用[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1159-1165. doi: 10.13203/j.whugis20160127
引用本文: 马超, 孙群, 陈换新, 徐青, 温伯威. 加权网页排序算法在道路网自动选取中的应用[J]. 武汉大学学报 ● 信息科学版, 2018, 43(8): 1159-1165. doi: 10.13203/j.whugis20160127
MA Chao, SUN Qun, CHEN Huanxin, XU Qing, WEN Bowei. Application of Weighted PageRank Algorithm in Road Network Auto-selection[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1159-1165. doi: 10.13203/j.whugis20160127
Citation: MA Chao, SUN Qun, CHEN Huanxin, XU Qing, WEN Bowei. Application of Weighted PageRank Algorithm in Road Network Auto-selection[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8): 1159-1165. doi: 10.13203/j.whugis20160127
  • 道路网的选取是道路数据综合的关键步骤,也是制图综合的核心内容[1]。目前道路网选取方法研究从传统的基于语义信息的选取逐渐转向依据道路的几何特征选取,尤其以图论、复杂网络等模型的方法居多。文献[2]以节点的度、接近中心性、中介中心性和道路链长度为指标,计算道路的重要度,通过节点连通度的计算保持选取后的道路连通性。文献[3]提出了一种基于层次随机图的道路选取方法,利用累计权重数度量道路的重要性, 实现道路的选取,但是该模型比较复杂。文献[4]以道路stroke为单位进行选取,定义了等级约束和空间邻近关系约束两种选取约束条件, 但是该模型没有考虑不同路网密度对选取结果的影响,在考虑邻近道路的影响时也只考虑了1阶邻居节点的影响。文献[5]引入了1~m阶邻居节点的重要度贡献,并以邻居节点的距离度量这种影响。文献[6]首先以道路stroke中介中心性为依据,划分不同层次的stroke,然后以stroke长度、中介中心性和层次间的连通关系为指标计算stroke的重要性,利用骨架的影响消结构完整,但是依然没有排除道路密度的影响。此外,还有基于案例推理的选取[7]、基于启发式算法的选取[8]、基于道路网眼密度的分析[9]等方法。除道路边缘的影响。该模型一定程度上能够保持道路整体的

    总体而言,基于图论和复杂网络理论的选取方法能够较好地保持路网形态,但是现有研究在计算节点的重要性时没有很好地解决不同道路之间相互链接对道路本身重要性的影响,虽有学者考虑了邻居节点的影响,但是模型不够完善。此外,目前的方法也少有考虑道路网密度对选取结果的影响。

    基于此, 本文提出了一种基于加权网页排序(PageRank)的算法计算道路的重要性。Page-Rank算法是搜索引擎领域的基本算法之一,利用网页之间的链接计算网页的重要性程度。本文借鉴了PageRank算法计算节点重要度的民主投票思想,充分考虑节点之间的相互关系。

    • 将网页抽象成一个节点,网页之间的链接作为一条有向边,则可以将互联网抽象为一个包含网页节点和节点之间链接的有向图,称为Web图,如图 1所示。由于节点之间的链接没有权重,因此网页Web图实质是一种有向无权图模型。对于网页A来说,指向其他网页的链接称为A的出链,而指向A的链接称为A的入链。图 1中,A有4个入链和2个出链。

      图  1  网页Web图示例

      Figure 1.  Example of Webpage Graph

    • PageRank是构建于1997年的谷歌早期搜索系统原型的网页链接分析算法,很多重要的链接分析算法都衍生于此[10]。PageRank通过分析网页的链接对网页的重要性进行排序,对于一个网页的PageRank值基于数量假设和质量假设, 网页的入链数量越多, 网页的入链质量越高,该网页重要度越高。

      基于上述假设,PageRank算法认为网页的重要性是由入链的数量和质量决定的,同时每个页面又将自己的重要度通过出链平均分配给其指向的节点。由于PageRank值的排序与初始值无关,因此开始时每个页面设置相同的PageRank值,通过迭代递归计算来更新每个页面的得分,PageRank值不断更新。若干轮计算后,各个网页的PageRank值会进入一个稳定的状态,即最终的PageRank值,该值越大, 表明该网页越重要[10]。PageRank值计算式为:

      $${\rm{PR}}({p_i}) = \frac{{1-d}}{N} + d \cdot \sum\limits_{{P_j} \in {\rm{inpu}}{{\rm{t}}_{{p_i}}}} {\frac{{{\rm{PR}}({p_j})}}{{{{\left| {{p_j}} \right|}_{{\rm{output}}}}}}} {\rm{ }} $$ (1)

      式中,pi表示网页节点;inputpi表示pi的所有入链集合;|pj|output表示pj的出链数量;PR(pi)表示节点pi的PageRank值;d为阻尼系数,可消除链接陷阱对结果的影响;N为网络节点的总数。以图 1中各个网页的PageRank值计算为例,设置各个网页节点初始重要度为1,经过20次迭代的结果见表 1

      表 1  节点PageRank值计算结果

      Table 1.  Result of Node's PageRank

      迭代次数 节点
      A B C D E F
      1 2.83 0.33 0.33 0.50 1 1
      2 1.33 0.16 0.16 1.41 1 1.91
      3 1.30 0.47 0.47 0.66 1.91 1.16
      4 2.12 0.22 0.22 0.65 1.16 1.61
      5 1.24 0.21 0.21 1.06 1.61 1.64
      6 1.59 0.35 0.35 0.62 1.64 1.42
      7 1.73 0.20 0.20 0.79 1.42 1.62
      8 1.39 0.26 0.26 0.86 1.62 1.58
      9 1.63 0.28 0.28 0.69 1.58 1.50
      10 1.60 0.23 0.23 0.81 1.50 1.60
      11 1.49 0.27 0.27 0.80 1.60 1.55
      12 1.61 0.26 0.26 0.74 1.55 1.54
      13 1.56 0.24 0.24 0.80 1.54 1.58
      14 1.54 0.26 0.26 0.78 1.58 1.55
      15 1.59 0.26 0.26 0.77 1.55 1.56
      16 1.55 0.25 0.25 0.79 1.56 1.57
      17 1.55 0.25 0.25 0.79 1.56 1.57
      18 1.56 0.26 0.26 0.77 1.57 1.55
      19 1.57 0.25 0.25 0.78 1.55 1.56
      20 1.55 0.26 0.26 0.78 1.56 1.56

      表 1可知,当迭代到第20次后,各个节点的PageRank值进入稳定状态,不再发生变化,网页重要度依次为A=E=F>D>B=C。观察图 1可知,节点A有4个入链,所以具有较高的重要度,DE具有重要度较高的入链A,重要度也较高,E仅有一个出链F,因此E的重要度等于FBC仅有入链D,故B=C

    • 道路网中路与路的交叉连接与网页的相互链接类似,因此可以以道路为节点,道路之间的交叉作为节点之间的连线将道路网抽象成为Web图模型。道路stroke是表示视觉上连续的多段道路的组合[11-13],按照stroke为单位对路网进行选取,能够保持道路的连通性和整体结构,故本文以stroke为道路的基本选取单位。将道路网的路段连接成stroke以后,将道路stroke抽象为图中的点,道路之间的交叉抽象成不同节点之间的连接,构成道路网的Web图模型,如图 2所示。图 2(a)中的道路网一共有5条stroke,抽象成Web图如图 2(b)所示。

      图  2  道路网与道路Web图

      Figure 2.  Road Network and Road Web Graph

      无权图表明节点之间链接的重要性是相同的,但实际上不同道路之间的链接的重要性并不相同。如图 2(a)中,5号道路为一条小路,而4号道路是城市主干道,两条路的重要度不可能相等。因此,道路网节点之间的链接应该有权重,节点本身的重要度越高,从其他道路获得的重要度也应该越高,这有利于区分道路的层次结构。

      综上所述,道路网的模型是一种有向有权图模型,各个节点从同一出链获取的重要度不同,重要度越高的节点,其获得的重要度越高。道路stroke长度是道路的重要的几何特征之一,本文以道路的stroke长度作为节点间链接的权重,构成道路网的有向有权图模型。

    • PageRank算法的精华在于将网页的重要性排序问题转化成了一个公共参与、以群体民主投票的方式求解的问题,网页之间的链接即被认为是投票行为。同理,在计算道路的重要度时,也应该考虑这种道路之间的相互交叉对其重要度的影响,即从整体上计算各条路的重要度。

      PageRank算法适用于有向无权图模型的节点重要度计算。而本文道路网模型是有向有权的模型,需要对传统的算法加以改进,将边的权重加入到PageRank迭代公式中[11]

      pi(i=1, 2, 3…N)为道路网中的节点,outputpj表示节点pj的出链集合,length(pi)表示节点pi的stroke长度,则节点pi获取来自节点pj重要度时的权重weight(pi, j)为:

      $$ {\rm{weight}}({p_{i, j}}) = \frac{{{\rm{length}}({p_i})}}{{\sum\limits_{{p_j} \in {\rm{outpu}}{{\rm{t}}_{{p_j}}}} {{\rm{length}}({p_j})} }} $$ (2)

      将式(2)代入式(1)得:

      $$ \begin{array}{l} {\rm{PR}}({p_i}) = \frac{{1-d}}{N} + d \cdot \sum\limits_{{p_j} \in {\rm{inpu}}{{\rm{t}}_{{p_i}}}} {({\rm{PR}}({p_j})\cdot} \\ \;\;\;\;\;\;\;\;\;\;\;{\rm{weight}}({p_{i, j}})) \end{array} $$ (3)

      图 2的道路网为例,利用加权的PageRank公式计算各个道路的重要度。设图 2中5条道路的stroke长度分别为10、10、8、8、4,分别代入式(1)和式(3),结果如图 3所示。

      图  3  改进前后结果对比

      Figure 3.  Comparison of Two PageRank Algorithms

      图 3可知,在应用基本PageRank算法时,5号道路与3、4号道路的权重是一样的,与实际不符,改进后的算法5号道路的PageRank值低于3、4号道路的,符合实际情况。

    • 进行道路选取时,除了要顾及道路网的连通性外,还要考虑路网的密度特征,保持选取前后路网的整体结构和密度差异。在路网密集区域,由于相互交叉连接的道路较多,其PageRank值可能会积累较高;反之,道路稀疏区域的PageRank值会相对较低,这会影响道路真实的重要度。如图 4中,5号道路由于与众多短路链接,其Page-Rank值已经超过了3号道路。因此,需要消除道路密度对PageRank值造成的影响,以保证选取结果的合理性。

      图  4  道路网及其PageRank值

      Figure 4.  Road Network with Its PageRank

      将道路连接成stroke以后,可能会存在从城市中心一直延伸到城区边缘的道路,这样的stroke跨越了路网从密集到稀疏的区域。然而道路网的密度是一个局部的概念,这种情况下无法直接将道路网的密度作为影响因子代入到重要度的计算中。

      在搜索引擎领域,与众多PageRank值较低链接的网页称为Spam网页,对应链接为Spamlink[12, 14]。Spamlink对节点重要度的影响需要消除。Benczur等[15]提出了SpamRank的概念,可以有效地识别和消除Spamlink的影响[16-18]。假设每个页面具有一个初始的SpamRank值,如果某个页面指向一个Spam页面,则该页面也可能是Spam页面,即会从出链上获得一定的SpamRank值,通过迭代计算,整个网络的SpamRank会进入一个稳定状态。SpamRank值越高,表明该节点的PageRank值越异常。道路网选取将具有众多低PageRank入链的道路定义为异常道路,通过计算道路的SpamRank值来度量异常道路,并修正对道路PageRank值造成的影响。SpamRank的计算公式如下[16]

      $$ \begin{array}{l} {\rm{SR}}({p_i}) = \left( {1-d} \right) \cdot S({p_i}) + \\ \;\;\;\;\;\;\;\;\;\;\;\;d \cdot \sum\limits_{{p_j} \in {\rm{outpu}}{{\rm{t}}_{{p_i}}}} {\frac{{{\rm{SR}}({p_j})}}{{{{\left| {{p_j}} \right|}_{{\rm{input}}}}}}} \end{array} $$ (4)

      式中,SR(pi)表示pi的SpamRank值;S(pi)表示pi的初始SpamRank值;outputpi表示pi的出链集合;|pj|input表示pj的入链数量。获取SpamRank值以后,需要对道路的PageRank值进行降权处理,以消除Spamlink的影响。为了保证消除的效果,本文采用线性消除的方法:

      $$ {\rm{PR}}({p_i}) = a \cdot {\rm{PR}}({p_i}) + \left( {1-a} \right) \cdot \frac{1}{{{\rm{SR}}({p_i})}} $$ (5)

      式中,a为(0, 1)的常数。利用式(4)计算图 4中各条道路的SpamRank值,并利用式(5)进行PageRank值修正,结果如图 5所示。

      图  5  道路网修正前后的PageRank值对比

      Figure 5.  Comparision of PageRank, SpamRank and Modified PageRank

      图 5可知,5号道路的原始PageRank值高于3号道路,且其SpamRank值较高,表明其PageRank值异常较为严重,经过SpamRank的降权处理后,得到了合理的PageRank值,此时5号道路的PageRank值小于3号道路,符合正常的道路选取要求。

    • 为了验证算法的正确性,本文开发了道路选取实验原型系统,并选取郑州市的道路网进行实验。图 6(a)为郑州市城区道路示意图,对原始数据进行拓扑处理并提取stroke,一共获得215条道路stroke。以stroke为基本选取单位,构建道路的有向有权图模型如图 6(b)所示,一共有215个节点,1 442条边。

      图  6  郑州市的道路网

      Figure 6.  Road Network of Zhengzhou with Its Graph

      依据式(4)~(6)计算节点的PageRank值和修正后的PageRank值。式(4)中,d=0.85,为谷歌推荐值。式(6)中,按PageRank值与SpamRank值同等重要处理,取a=0.5,计算结果见表 2

      表 2  郑州市城区道路PageRank值(部分)

      Table 2.  PageRank of Zhengzhou Road Network(Part)

      道路ID stroke长度/km PageRank 修正后PageRank
      1 4.3 0.813 0.765
      2 6.7 1.223 1.107
      3 1.3 0.276 0.312
      4 2.5 0.701 0.668
      5 2.7 1.005 0.984
      6 4.6 1.472 1.208
      7 5.1 1.135 1.275
      215 5.2 1.103 1.004

      为了验证本文方法的有效性,针对原始道路网进行不同程度的道路选取实验,并与基于网络中心性方法(节点重要度指标为stroke长度、节点度、接近中心性、中介中心性)的选取结果进行对比。图 7给出了本文方法,未经过SpamRank修正方法和网络中心性方法在选取比例为5%、10%和15%时的道路选取结果。

      图  7  依据本文方法、未经过SpamRank修正方法和网络中心性方法选取结果对比

      Figure 7.  Comparison of the PageRank Method, Unmodified PagePank and the Network Centrality

      比较不同比例的选取结果可以发现:①由于均采用stroke为基本的选取单位,无论何种选取比例,两种方法的选取结果在整体上都能够保持道路网的连通性;②从选取的结果来看,本文方法在选取比例较小时,主要选取的是能够反映道路网分布的骨架道路,如贯通城市的主干道路和环城道路。随着选取比例的提高,除了继续选取道路稀疏区域的骨架道路外,也选取了部分市区内的主干道路,选取结果较为合理;③未经过SpamRank修正的方法在选取比例较小时,主要选取stroke较长的路段,由于选取比例较小,道路密度的影响不大,随着选取比例的提高,道路密度的影响逐渐明显,并选择了较多道路密集区域的非主干道路;④基于网络中心性的方法在道路稀疏区域只选取了道路stroke较长、连接城市中心到郊区的道路,道路密集区域选取了一些次要的道路,整体结构保持方面有所不足。

      为了体现本文方法在保持道路网整体结构和密度分布上的优势,统计分析了选取比例为15%时不同方法的结果。本文方法和基于网络中心性的方法中, 道路网的连通度分别为332、314,完整网眼数量分别为134、132,悬挂路段数分别为16、23,不完整网眼数量分别为3、7。可以看出,在相同选取比例下,本文方法选取结果的连通度要高于基于网络中心性的方法,说明本文方法选取的stroke连通性较好,相互连接更加紧密;两种选取方法的完整网眼数量基本一致,这是由于网络中心性的方法在道路密集区域选取了较多的短stroke,形成较多的低等级的道路网眼,但是本文方法不完整网眼和悬挂路段较少,说明本文方法能够较好地保持道路边界轮廓拓扑结构的完整性和道路网的整体结构。

    • 道路网的选取问题是道路网综合的重点和难点[15]。本文将PageRank算法引入计算道路节点的重要度中,取得了很好的效果。但是,单纯依靠道路stroke长度作为边的权重不利于处于桥接位置的短stroke,且这些道路往往是重要的交通枢纽,基于网络中心性的方法能够较好体现这些道路的重要度。此外,选取结果还会受到stroke连接质量的影响。因此,本文方法适用于方格状的道路网。在下一步的研究中,需要进行更广泛、深入的实验,探索更为合理的边权重设置,尝试以道路stroke长度与节点的网络中心性相结合的边权重设置方案,并进一步研究道路选取结果的量化评价机制。

参考文献 (18)

目录

    /

    返回文章
    返回