考量地理特性的PageRank演算法:評估地理網絡節點之重要性

Geographically Modified PageRank Algorithms: Measuring the Importance of Nodes in a Geospatial Network

陳威全(Wei Chien Benny Chin)

指導教授 ： 溫在弘

國立臺灣大學/理學院/地理環境資源學研究所/碩士(2013年)

https://doi.org/10.6342/NTU.2013.00187

摘要

地理空間網絡是指以網絡方式再現空間單元之間關係的網絡。在社會網絡分析領域中，已有相當完善的研究在討論網絡核心性、小世界與無尺度網絡等各種網絡拓撲結構特性。PageRank (PR) 是基於網頁間連線結構的網絡分析方法，其是Google 搜尋引擎排列搜尋結果的演算法。透過分析地理網絡拓撲結構，可以獲取地理網絡中節點的重要性資訊。然而，大部分網絡分析方法著重於討論網絡拓撲結構，這些方法所依據的原理並未考慮地理結構的特性，包括節點間距離遞減效果。所以，本研究將距離遞減效果及引力模型(即同時整合距離遞減效果及吸引效果)，並發展出兩個以地理特性及引力模型修改的PR演算法，包括Inverse-Distance PageRank (IDPR) 及 Geographical PageRank (GPR)。為測試此2種演算法，本研究進行2個測試。其一為建立台灣城市間的1小時交通可及性網絡，經計算後與人口分佈及城際交通流量 (作為實際資料) 作斯皮爾曼等級相關分析 (Spearman Rank Correlation)，並與PR 及Weighted PageRank (WPR)演算法作比較討論；其二是以上述一小時交通網絡為基底狀態，討論在加入台灣高速鐵路系統之後，節點重要性的變化。本研究第一個測試的結果顯示IDPR及GPR與實際資料間的相關性最高，而第二部分測試結果顯示WPR及GPR的重要性變化具有網絡的遞移效果。因此，本研究認為IDPR及GPR較為適合用在地理空間網絡中，節點重要性的測定，而若遞移效果是關鍵的特性，則應考慮使用GPR作為分析方式。

關鍵字

距離遞減效果 ； 引力模型 ； PageRank ； 地理空間網絡 ； 網絡遞移效果

並列摘要

A geospatial network represents the spatial relationships with the network perspective. Within the scope of social network analysis, the network topology characteristics, including network centrality, small world and scale-free properties, have been well studied, and these concepts can also provide important implications on measuring the important of places in the geospatial network. PageRank (PR), which is an important link analysis algorithm, is what Google uses to determine how important a page is on the web. However, most measures of network analysis were designed to understand network topological structures rather than geographical structures. Therefore, these measures have not considered the geographical relationships as their main concern, including geographical distance decay effect between nodes. This study incorporates geographic properties, including distance-decay and spatial interactions among nodes, and proposes two modified PR algorithms, Inverse-Distance PageRank (IDPR) and Geographical PageRank (GPR). To test the performance of the index of importance (including IDPR and GPR), this study did two experiments with the inter-city network of Taiwan. In the first experiment, this study calculated the index of importance, and this study used the population data and inter-townships car flow data as observed data to check the Spearman Rank Correlation, and compared the correlation results with existing algorithms: PR and Weighted PageRank (WPR); in the second experiment, this study explore the changes of node’s importance between before and after the construction of Taiwan High Speed Rail System. Our findings in the first experiment showed that IDPR and GPR are better correlated to the observed data, and our findings in the second experiment showed that the GPR and WPR could capture the transitive effect. Since IDPR and GPR take the distance decay effect into account, results using the algorithms can capture more geographical properties. In conclusion, IDPR and GPR are better metrics to be used in geospatial network analysis; but, if the transitive effect is an important feature in the analysis, GPR is a better metric.

並列關鍵字

Distance decay ； gravity model ； PageRank ； geospatial network ； network transitive effect

參考文獻

Reggiani, A.,S. Signoretti, P. Nijkamp, A. Cento. 2009. Network measures in civil air transport: A case study of Lufthansa. Tinbergen Institute Discussion Paper, Tinbergen Institute, Amsterdam, The Netherlands.

Alderson, A. S., and J. Beckfield. 2004. Power and position in the world city system. American Journal of Sociology 109(4): 811-851.

Batten, D. F. 1995. Network cities: creative urban agglomerations for the 21st century. Urban Studies 32(2): 313-327.

Bonacich, P. 1987. Power and centrality: A family of measures. The American Journal of Sociology 92(5): 1170-1182.

Brin, S., and L. Page. 1998. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems 30: 107-117.