加权网页排序算法在道路网自动选取中的应用
|
摘要
针对现有算法在计算道路网节点重要度时忽略节点间的相互影响以及道路密度引起的重要度异常等问题,提出了一种基于加权网页排序算法的道路网自动提取方法。首先将道路连接成路段,以路段为网络节点,道路交叉作为节点连线,路段长度作为边的权重,将道路网抽象成有向有权图;然后利用加权网页排序算法计算有向有权图节点的重要度,并利用链接作弊检测的方法修正由道路密度引起的节点重要度异常,得到道路节点的最终重要度排序,从而完成道路网的提取。通过真实路网数据进行实验分析,结果表明,相对基于网络中心性的方法,该算法的提取结果能够更好地保留原始路网的密度差异和整体结构。
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.
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.
引文
[1]Chen Bo,Wu Fang,Qian Haizhong.Study on Road Networks’Auto-selection Algorithms[J].Journal of Image and Graphics,2008,13(12):2 388-2 393(陈波,武芳,钱海忠.道路网自动选取方法研究[J].中国图象图形学报,2008,13(12):2 388-2 393)
[2]Luan Xuechen,Yang Bisheng,Zhang Yunfei.Structural Hierarchy Analysis of Streets Based on Complex Network Theory[J].Geomatics and Information Science of Wuhan University,2012,37(6):728-732(栾学晨,杨必胜,张云菲.城市道路复杂网络结构化等级分析[J].武汉大学学报·信息科学版,2012,37(6):728-732)
[3]Li Muzi,Xu Zhu,Li Zhilin,et al.A Hierarchical Random Graph Based Selection Method for Road Network Generalization[J].Journal of Geo-Information Science,2012,14(6):719-727(李木梓,徐柱,李志林,等.基于层次随机图的道路选取方法[J].地球信息科学学报,2012,14(6):719-727)
[4]Yang Min,Ai Tinghua,Zhou Qi.A Method of Road Network Generalization Considering Stroke Properties of Road Object[J].Acta Geodaetica et Cartographica Sinica,2013,42(4):581-587(杨敏,艾廷华,周启.顾及道路目标stroke特征保持的路网自动综合方法[J].测绘学报,2013,42(4):581-587)
[5]Liu Gang,Li Yongshu,Yang Jun,et al.Auto-selection Method of Road Networks Based on Evaluation of Node Importance for Dual Graph[J].Acta Geodaetica et Cartographica Sinica,2014,43(1):97-104(刘刚,李永树,杨俊,等.对偶图节点重要度的道路网自动选取方法[J].测绘学报,2014,43(1):97-104)
[6]He Haiwei,Qian Haizhong,Liu Hailong,et al.Road Network Selection Based on Road Hierarchical Structure Control[J].Acta Geodaetica et Cartographica Sinica,2015,44(4):453-461(何海威,钱海忠,刘海龙,等.道路网层次骨架控制的道路选取方法[J].测绘学报,2015,44(4):453-461)
[7]Guo Min.Research on Intelligent Road-Network Selection Method Based on Cases Reasoning[D].Zhengzhou:Information Engineering University,2013(郭敏.基于案例学习的道路网智能选取方法研究[D].郑州:信息工程大学,2013)
[8]Deng Hongyan,Wu Fang,Zhai Renjian,et al.A Generalization Model of Road Networks Based on Genetic Algorithm[J].Geomatics and Information Science of Wuhan University,2006,31(2):164-167(邓红艳,武芳,翟仁建,等.基于遗传算法的道路网综合模型[J].武汉大学学报·信息科学版,2006,31(2):164-167)
[9]Hu Yungang,Chen Jun,Li Zhilin,et al.Selective Omission of Road Features Based on Mesh Density for Digital Map Generalization[J].Acta Geodaetica et Cartographica Sinica,2007,36(3):351-357(胡云岗,陈军,李志林,等.基于网眼密度的道路选取方法[J].测绘学报,2007,36(3):351-357)
[10]Page L,Brin S,Motwani R,et al.The PageRank Citation Ranking:Bringing Order to the Web[OL].http://www.ilpubs.stanford.edu:8090/422/1/1999-66.pdf,1999
[11]Thomson R C.The Stroke Conception Geographic Network Generalization and Analysis[J].Progress in Spatial Data Handing,2006,11:681-697
[12]Tian Jing,He Qingsong,Yan Fen.Formalization and New Algorithm of stroke Generation in Road Networks[J].Geomatics and Information Science of Wuhan University,2014,39(5):556-560(田晶,何青松,颜芬.道路网stroke生成问题的形式化表达与新算法[J].武汉大学学报·信息科学版,2014,39(5):556-560)
[13]Luan Xuechen,Yang Bisheng.Generating Strokes from City Road Networks[J].Geography and GeoInformation Science,2009,25(1):49-56(栾学晨,杨必胜.城市复杂道路网的Stroke生成方法[J].地理与地理信息科学,2009,25(1):49-56)
[14]Chen Xiaofei,Wang Yitong.A Link-Based Web Spam Flitting Method[J].Journal of Computer Research and Development,2010,47(Supp):8-14(陈小飞,王轶彤.一种基于链接结构的Spam网页过滤算法[J].计算机研究与发展,2010,47(Supp):8-14)
[15]Benczur A,Csalogany K,Sarlos T,et al.SpamRank-Fully Automatic Link Spam Detection[C].The 1st International Workshop on Adversarial Information Retrieval on the Web,Chiba,Japan,2005
[16]Qian Gongwei,Ni Lin,Miao Yuan,et al.Extended PageRank Algorithm Based on Web Link and Content Analysis[J].Computer Engineering and Applications,2007,43(21):160-164(钱功伟,倪林,Miao Yuan,等.基于网页链接和内容分析的改进PageRank算法[J].计算机工程与应用,2007,43(21):160-164)
[17]Zhou Bin,Pei Jian,Tang Zhaohui.A Spamicity Approach to Web Spam Detection[C].SIAM Int Conf on Data Mining,Atlanta,Georgia,USA,2008
[18]Xu Zhenhu.Research on Algorithms for Detecting Web Link Spam[D].Chengdu:Southwest Jiaotong University,2009(徐桢虎.链接作弊垃圾网页的检测算法研究[D].成都:西南交通大学,2009)
[2]Luan Xuechen,Yang Bisheng,Zhang Yunfei.Structural Hierarchy Analysis of Streets Based on Complex Network Theory[J].Geomatics and Information Science of Wuhan University,2012,37(6):728-732(栾学晨,杨必胜,张云菲.城市道路复杂网络结构化等级分析[J].武汉大学学报·信息科学版,2012,37(6):728-732)
[3]Li Muzi,Xu Zhu,Li Zhilin,et al.A Hierarchical Random Graph Based Selection Method for Road Network Generalization[J].Journal of Geo-Information Science,2012,14(6):719-727(李木梓,徐柱,李志林,等.基于层次随机图的道路选取方法[J].地球信息科学学报,2012,14(6):719-727)
[4]Yang Min,Ai Tinghua,Zhou Qi.A Method of Road Network Generalization Considering Stroke Properties of Road Object[J].Acta Geodaetica et Cartographica Sinica,2013,42(4):581-587(杨敏,艾廷华,周启.顾及道路目标stroke特征保持的路网自动综合方法[J].测绘学报,2013,42(4):581-587)
[5]Liu Gang,Li Yongshu,Yang Jun,et al.Auto-selection Method of Road Networks Based on Evaluation of Node Importance for Dual Graph[J].Acta Geodaetica et Cartographica Sinica,2014,43(1):97-104(刘刚,李永树,杨俊,等.对偶图节点重要度的道路网自动选取方法[J].测绘学报,2014,43(1):97-104)
[6]He Haiwei,Qian Haizhong,Liu Hailong,et al.Road Network Selection Based on Road Hierarchical Structure Control[J].Acta Geodaetica et Cartographica Sinica,2015,44(4):453-461(何海威,钱海忠,刘海龙,等.道路网层次骨架控制的道路选取方法[J].测绘学报,2015,44(4):453-461)
[7]Guo Min.Research on Intelligent Road-Network Selection Method Based on Cases Reasoning[D].Zhengzhou:Information Engineering University,2013(郭敏.基于案例学习的道路网智能选取方法研究[D].郑州:信息工程大学,2013)
[8]Deng Hongyan,Wu Fang,Zhai Renjian,et al.A Generalization Model of Road Networks Based on Genetic Algorithm[J].Geomatics and Information Science of Wuhan University,2006,31(2):164-167(邓红艳,武芳,翟仁建,等.基于遗传算法的道路网综合模型[J].武汉大学学报·信息科学版,2006,31(2):164-167)
[9]Hu Yungang,Chen Jun,Li Zhilin,et al.Selective Omission of Road Features Based on Mesh Density for Digital Map Generalization[J].Acta Geodaetica et Cartographica Sinica,2007,36(3):351-357(胡云岗,陈军,李志林,等.基于网眼密度的道路选取方法[J].测绘学报,2007,36(3):351-357)
[10]Page L,Brin S,Motwani R,et al.The PageRank Citation Ranking:Bringing Order to the Web[OL].http://www.ilpubs.stanford.edu:8090/422/1/1999-66.pdf,1999
[11]Thomson R C.The Stroke Conception Geographic Network Generalization and Analysis[J].Progress in Spatial Data Handing,2006,11:681-697
[12]Tian Jing,He Qingsong,Yan Fen.Formalization and New Algorithm of stroke Generation in Road Networks[J].Geomatics and Information Science of Wuhan University,2014,39(5):556-560(田晶,何青松,颜芬.道路网stroke生成问题的形式化表达与新算法[J].武汉大学学报·信息科学版,2014,39(5):556-560)
[13]Luan Xuechen,Yang Bisheng.Generating Strokes from City Road Networks[J].Geography and GeoInformation Science,2009,25(1):49-56(栾学晨,杨必胜.城市复杂道路网的Stroke生成方法[J].地理与地理信息科学,2009,25(1):49-56)
[14]Chen Xiaofei,Wang Yitong.A Link-Based Web Spam Flitting Method[J].Journal of Computer Research and Development,2010,47(Supp):8-14(陈小飞,王轶彤.一种基于链接结构的Spam网页过滤算法[J].计算机研究与发展,2010,47(Supp):8-14)
[15]Benczur A,Csalogany K,Sarlos T,et al.SpamRank-Fully Automatic Link Spam Detection[C].The 1st International Workshop on Adversarial Information Retrieval on the Web,Chiba,Japan,2005
[16]Qian Gongwei,Ni Lin,Miao Yuan,et al.Extended PageRank Algorithm Based on Web Link and Content Analysis[J].Computer Engineering and Applications,2007,43(21):160-164(钱功伟,倪林,Miao Yuan,等.基于网页链接和内容分析的改进PageRank算法[J].计算机工程与应用,2007,43(21):160-164)
[17]Zhou Bin,Pei Jian,Tang Zhaohui.A Spamicity Approach to Web Spam Detection[C].SIAM Int Conf on Data Mining,Atlanta,Georgia,USA,2008
[18]Xu Zhenhu.Research on Algorithms for Detecting Web Link Spam[D].Chengdu:Southwest Jiaotong University,2009(徐桢虎.链接作弊垃圾网页的检测算法研究[D].成都:西南交通大学,2009)