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

Application of Weighted PageRank Algorithm in Road Network Auto-selection

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

The auto-selection of road network is the core content of the road data generalization.Aiming at the shortage of current researches which ignores the effect from the neighbor node and the road density when calculating the road node importance degree.This paper proposes a method based on weighted PageRank algorithm.Firstly,the road stroke is generated and treated as the basic calculation unit.Then the road network is treated as a weighted directed graph that the road stroke as the node of the graph,as well as the road junctions are treated as the link between the nodes.The stroke length is selected as the link weight between two graph nodes.When the road graph is built up,the weighted PageRank algorithm is used to calculate the importance degree of the node which stands for the road importance degree and take the effect from the neighbor node into account.Next,thinking about the influence of the road density,the SpamRank method is selected.The SpamRank is just contrary to the PageRank and could be used to modify the importance degree exception caused by the road density.After revised by the SpamRank it will get the latest PageRank on which the road selection is based.Finally,using the Zhengzhou road data for experimental verification,the results show that this method can effectively maintain the original road connectedness and the whole structure compared with the network century method.