跳到主要內容

臺灣博碩士論文加值系統

(44.211.24.175) 您好!臺灣時間:2024/11/11 05:04
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳威全
研究生(外文):Wei Chien Benny Chin
論文名稱:考量地理特性的PageRank演算法:評估地理網絡節點之重要性
論文名稱(外文):Geographically Modified PageRank Algorithms: Measuring the Importance of Nodes in a Geospatial Network
指導教授:溫在弘溫在弘引用關係
指導教授(外文):Tzai-Hung Wen
口試委員:林楨家黃崇源
口試委員(外文):Jen-Jia LinChung-Yuan Huang
口試日期:2013-06-21
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:地理環境資源學研究所
學門:社會及行為科學學門
學類:地理學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:99
中文關鍵詞:距離遞減效果引力模型PageRank地理空間網絡網絡遞移效果
外文關鍵詞:Distance decaygravity modelPageRankgeospatial networknetwork transitive effect
相關次數:
  • 被引用被引用:0
  • 點閱點閱:456
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
地理空間網絡是指以網絡方式再現空間單元之間關係的網絡。在社會網絡分析領域中,已有相當完善的研究在討論網絡核心性、小世界與無尺度網絡等各種網絡拓撲結構特性。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作為分析方式。

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.

國立臺灣大學碩士學位論文口試委員會審定書 i
謝辭 ii
摘要 iii
Abstract iv
Table of Contents vi
Table of Figures viii
Table of Tables x
1. Introduction 1
1.1. Background 1
1.2. Research objective 9
2. Related works 11
2.1. The geospatial network 11
2.1.1. Connection network 11
2.1.2. Interaction network 12
2.1.3. Summary 13
2.2. Network centrality metrics 14
2.2.1. Degree centrality 14
2.2.2. Closeness centrality 17
2.2.3. Betweenness centrality 20
2.2.4. Flow Betweenness centrality 23
2.2.5. Summary 26
2.3. The Existing PageRank algorithms 27
2.3.1. PageRank (PR) 27
2.3.2. Weighted PageRank (WPR) 34
2.3.3. Summary 38
3. Geographically modified PageRank algorithms 39
3.1. Inverse-Distance PageRank (IDPR) 39
3.2. Geographical PageRank (GPR) 44
3.3. Summary 48
4. Experiment 1 – Inter-city network 49
4.1. Preface 49
4.2. Datasets preparation 51
4.2.1. Geospatial network 51
4.2.2. Data of intensity of human activity 52
4.3. Data visualization 53
4.3.1. Geospatial network 53
4.3.2. Spatial distribution of the intensity of human activity 58
4.4. Calculation results 63
4.5. Correlation analysis 68
4.6. Sensitivity analysis 71
5. Experiment 2 – Taiwan High Speed Rail System 81
5.1. Preface 81
5.2. Data preparations and calculations 84
5.3. Results 85
6. Discussions 90
6.1. The key features of the PageRanks algorithms 90
6.2. Experiment 1 91
6.3. Experiment 2 92
7. Conclusions and suggestions for future studies 94
Reference 96


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.
Commoner, M. 1971. The Closing Circle: Nature, Man, and Technology. New York.
Derudder, B., L. Devriendt, and F. Witlox. 2007. Flying where you don’t want to go: An empirical analysis of hubs in the global airline network. Tijdschrift voor Economische en Sociale Geografie 98(3): 307-324.
Ducruet, C., D. Ietri, and C. Rozenblat. 2011. Cities in worldwide air and sea flows: A multiple networks analysis. Cybergeo : European Journal of Geography: Systems, Modeling, Geostatistics (article 528).
Ducruet, C., S. W. Lee, A. K. Y. Ng. 2010. Centrality and vulnerability in liner shipping networks: revisiting the Northeast Asian port hierarchy. Maritime Policy & Management 37(1): 17-36.
El-Geneidy, A., and D. Levinson. 2011. Place Rank: Valueing spatial interactions. Networks and Spatial Economics 11(4): 643-659.
Freeman, L. C. 1978. Centrality in social networks conceptual clarification. Social Network 1(3): 215-239.
Fotheringham, S. 1981. Spatial structure and distance-decay parameters. Annals of the Association of American Geographers 71(3): 425-436.
Gargiulo, F., M. Lenormand, S. Huet, and O. Baqueiro Espinosa. 2012. Commuting network models: Getting the essentials. Journal of Artificial Societies and Social Simulation 15(2): 13
Guimera, R., S. Mossa, A. Turtschi, and I. A. N. Amaral. 2005. The worldwide air transportation network: Anoalous centrality, community structure, and cities’ global roles. PNAS 103(22): 7794-7799.
Institute of Transportation, Ministry of Transportation and Communications. 2009. The Demand model of intecity transportation systems under national sustainable development in Taiwan (4/4). ISBN: 978-986-01-8085-5.
Jiang, B. 2009. Ranking spaces for predicting human movement in an urban environment. International Journal of Geographical Information Science 23(7): 823-837.
Jiang, B., J. Yin, S. Zhao. 2009. Characterizing human mobility patterns in a large street network. Physical Review E 80(2).
Jiang, B., T. Jia. 2011. Agent-based simulation of human movement shaped by the underlying street structure. International Journal of Geographical Information Science 25(1): 51-64.
Josang, A., E. Gray, M. Kinateder. 2006. Simplification and analysis of transitive trust networks. Web Intelligence and Agent Systems 4(2): 139-161.
Josang, A., R. Ismail, C. Boyd. 2007. A survey of trust and reputation systems for online service provision. Decision Support Systems 43(2): 618-644.
Newman, M. 2010. Networks: An Introduction. Oxford University Press.
Noh, J. D., and H. Rieger. 2004. Random walks on complex networks. Physical Review Letters 92(11): 118701-1-118701-4.
Reggiani, A., P. Bucci, G. Russo. 2011. Accessibility and network structures in the German commuting. Networks and Spatial Economics 11(4): 621-641.
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.
Reily, W. J. 1931. The law of retail gravitation. New York.
Scholz, A. B. 2011. Spatial network configurations of cargo airlines. Working Paper Series in Economics 20.
Stephenson, K., and M. Zelen. 1989. Rethinking centrality: Methods and examples. Social Networks 11: 1-37.
Stewart, J. Q. 1950. The development of social physics. American Journal of Physics 18: 239-253.
Symeonidis, P., E. Tiakas, and Y. Manolopoulos. 2010. Transitive node similarity for link prediction in social networks with positive and negative links. Paper presented at the 4th ACM conference on Recommender Systems, NY, United States of America.
Tinbergen, J. 1963. Shaping the world economy. The International Executive 5(1):27-30.
Tobler, W. 1970. A computer movie simulating urban growth in the Detroit region. Economic Geography 46(2): 234-210.
Tobler, W. 2004. On the first law of geography: A reply. Annals of the Association of American Geographers 94(2): 304-310.
Wang F., A. Antipova, S. Porta. 2011. Street centrality and land use intensity in Baton Rouge, Louisiana. Journal of Transport Geography 19(2): 285-293.
Xing, W., and A. Ghorbani. 2004. Weighted PageRank Algorithm. Paper presented at the 2nd Annual Conference on Communication Networks and Services Research, NB, Canada.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top