臺灣博碩士論文加值系統

隨著全球日增的都市發展，交通壅塞已成為一個普遍的問題。解決壅塞中常探討壅塞於何處發生以及生成原因，過去已發展諸多方法在靜態、動態環境中捕捉壅塞發生的地方，然而壅塞發生時所影響的區域卻無所探討，因此無法得知無預期的道路發生壅塞時，受到影響的範圍，並做出交通決策防止進一步的壅塞。過去用於評估影響區域的方法以固定距離法劃定評估範圍，並評估此區域受到的影響，然而此方法適用於評估特定開發案之影響。本研究將評估範圍的定義延伸解釋為有交互作用的地區則會受到影響，並以此概念延伸，藉由建構節點間的連結強度定義子群，子群的特性為內部交互作用大於外部的區域，而這樣的結構特色適於捕捉發生壅塞時的主要影響範圍。
根據研究目的，本研究使用網絡遞移性的理論，建立道路連結關並以連結關係的強弱來定義子群。考量交通流動時的不均流動特性以及資料的限制，以PageRank演算法為基礎發展FBPR(Flow-based PageRank)，並於模式中透過基因演算法協助建立吸引力權重，建立道路間的傳遞關係，並以此關係建立子群。結果顯示，FBPR 藉由遞移能外推的特性建立道路間的流動關係，並以實際流量做為校正，確保FBPR建立之相對流量分布與實際流量分布類似，確立道路之連結關係後。結果顯示道路的流動存在偏向性，並影響路網的流量分布及流量形態。而交通路網的子群結構強烈受到空間及網絡限制，因而有明顯的空間分布特性，在流量較高的地區子群內包含道路較多，顯示了流量高地區的影響範圍較大。
本研究之應用可延伸為兩部分，第一部分為建立道路間的連結，使得未來能以少部分資料推估城市尺度之流量，並將建立之連結關係運用於交通網絡連結分析中。第二部分為確立衝擊區域的範圍，能做為都市規劃者或導航系統做交通決策的參考。

With the growing number of developing cities, traffic congestion has becomes a global issue. To resolve congestion, the first step is to identify where it occurs. Many methods to detect congestion have been developed. However, the geographic extent of the congestion has seldom been discussed. Therefore, when congestion occurs, the roads influencing the problem are unknown, and control strategies cannot be implemented to avoid further congestion. Existing guidelines for conducting traffic impact assessments to determine the extent of impact from congestion define assessment areas based on a certain distance. This study considers other factors that influence the impact area, as distance is not the only factor. This study proposes using Flow-Based PageRank (FBPR) to build link relationships between roads, where the strength of a link relationship represents the intensity of interplay. The community structures index identifies where more interplay occurs, and geographic extent illustrates areas of denser connections, which can indicate impact area. To test the robustness of FBPR, different sizes of data were used.
The findings revealed that the values of link relationships were primarily distributed between 0.1 and 0.4 and indicated the existence of a tendency that regulates the flow pattern in a road network. The community structures index value was 0.94 and confirmed the existence of subgroups within the road network. The distribution of community structures was constrained by spatial and network structure, and large communities were distributed in high-volume areas. This indicates that high-volume areas would have a greater impact.
In conclusion, FBPR can be used to construct link relationships between roads, and this information can be further applied to link analysis of road networks. The communities in a road network represent geographic subgroups within which interplay is higher, which provides management areas for planners.

口試委員審定書 II
謝辭 III
摘要 V
Abstract VI
Figure of content IX
List of content X
Chapter 1 Introduction 1
1.1 Congestion and transportation 1
1.2 Detection of congestion 1
1.3 Identification of congestion impact area 3
1.4 Research objectives 5
Chapter 2 Literature reviews 6
2.1 Link relationships 6
2.1.1 Links and flow in a network 6
2.1.2 Transitive effect 9
2.1.3 Existing methods for constructing link relationships 13
2.2 Identifying areas with dense interactions in a road network 15
2.2.1 Girvan-Newman algorithm 17
2.2.1 Maximum modularity 18
2.2.3 Summary 19
Chapter 3 Data and Method 20
3.1 Framework of method 20
3.2 Data 21
3.2.1 Network Data 21
3.2.2 Volume data 21
3.2.3 Data process 21
3.3 Flow-Based PageRank (FBPR) 28
3.3.1 Constructing the attractiveness of roads 31
3.3.2 Link relationship between roads 32
3.3.3 Calibrating and validating attractiveness and link relationship 35
3.3.4 Optimal attractiveness 35
3.3.5 Visualization and robustness of FBPR 41
3.4 Maximum modularity 42
Chapter 4 Results 44
4.1 Properties of raw data 44
4.2 Robustness of Flow-Based PageRank 47
4.3 Distribution of FBPR scores 49
4.4 Description of attractiveness 52
4.5 Interactions between roads 56
4.6 Geographic extent of impact area 60
Chapter 5 Discussion 62
5.1 Construction of link relationships 62
5.2 Identification of impact area 64
5.3 Contributions of the study 66
5.4 Limitations 67
5.4.1 Simplification of road network 67
5.4.2 Direction of road network 68
5.5 Future suggestions 68
5.5.1 PageRank model 68
5.5.2 Turning tendency 69
Chapter 6 Conclusion 71
REFERENCE 73

Agryzkov, T., Oliver, J. L., Tortosa, L., Vicent, J. F. (2012). An algorithm for ranking the nodes of an urban network based on the concept of PageRank vector. Applied Mathematics and Computation, 219(4), 2186-2193.
Albayrak, M., Allahverdi, N. (2011) Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms. Expert Systems with Applications, 38(3), 1313-1320.
Anez, J., De La Barra, T., Perez, B. (1996) Dual graph representation of transport networks. Transportation Research Part B: Methodological, 30(3), 209-216.
Aynaud, T., Guillaume, J. L. (2010). Static community detection algorithms for evolving networks. In Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2010 Proceedings of the 8th International Symposium on (pp. 513-519). IEEE.
Bagler, G. (2008) Analysis of the airport network of India as a complex weighted network. Physica A: Statistical Mechanics and its Applications, 387(12), 2972-2980.
Bakshy, E., Rosenn, I., Marlow, C., Adamic, L. (2012, April). The role of social networks in information diffusion. In Proceedings of the 21st international conference on World Wide Web (pp. 519-528). ACM.
Barrat, A., Barthelemy, M., Pastor-Satorras, R., Vespignani, A. (2004). The architecture of complex weighted networks. Proceedings of the National Academy of Sciences of the United States of America, 101(11), 3747-3752.
Bauza, R., Gozalvez, J. (2013) Traffic congestion detection in large-scale scenarios using vehicle-to-vehicle communications. Journal of Network and Computer Applications, 36(5), 1295-1307.
Berkman, L. F., Syme, S. L. (1979) Social networks, host resistance, and mortality: a nine-year follow-up study of Alameda County residents. American journal of Epidemiology, 109(2), 186-204.
Blondel, V. D., Guillaume, J. L., Lambiotte, R., Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10), P10008.
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D. U. (2006). Complex networks: Structure and dynamics. Physics reports, 424(4), 175-308.
Brin, S., and L. Page. (1998) The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30, 107-117.
Castillo, E., Menendez, J. M., Sanchez-Cambronero, S. (2008). Predicting traffic flow using Bayesian networks. Transportation Research Part B: Methodological, 42(5), 482-509.
Centola, D., Eguiluz, V. M., Macy, M. W. (2007) Cascade dynamics of complex propagation. Physica A: Statistical Mechanics and its Applications, 374(1), 449-456.
Centola, D. (2011) An experimental study of homophily in the adoption of health
behavior. Science, 334(6060), 1269-1272.
Choi, J. H., Barnett, G. A., CHON, B. S. (2006) Comparing world city networks: a network analysis of Internet backbone and air transport intercity linkages. Global Networks, 6(1), 81-99.
Chen, L., Jin, W. L., Hu, J., Zhang, Y. (2008, October). An urban intersection model based on multi-commodity kinematic wave theories. In Intelligent Transportation Systems, 2008. ITSC 2008. 11th International IEEE Conference on (pp. 269-274). IEEE.
Clauset, A., Newman, M. E., Moore, C. (2004). Finding community structure in very large networks. Physical review E, 70(6), 066111.
Coifman, B. (2003) Identifying the onset of congestion rapidly with existing traffic detectors. Transportation Research Part A: Policy and Practice, 37(3), 277-291.
Colizza, V., Barrat, A., Barthelemy, M., Vespignani, A. (2006) The role of the airline transportation network in the prediction and predictability of global epidemics. Proceedings of the National Academy of Sciences of the United States of America, 103(7), 2015-2020.
De Giovanni, L., Pezzella, F. (2010). An improved genetic algorithm for the distributed and flexible job-shop scheduling problem. European journal of operational research, 200(2), 395-408.
De Montis, A., Barthelemy, M., Chessa, A., Vespignani, A. (2005). The structure of inter-urban traffic: A weighted network analysis.
Erjia Yan, Ying Ding, (2009) Discovering author impact: A PageRank perspective,Information Processing and Management, 47(1),125-134.
Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), 298-305.
Freeman, L. C. (1978) Centrality in social networks conceptual clarification. Social Network 1(3): 215-239.
Gall, A. I., Hall, F. L. (1989) Distinguishing between incident congestion and recurrent congestion: a proposed logic. Transportation Research Record, (1232).
Girvan, M., Newman, M. E. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12), 7821-7826.
Guimera, R., Mossa, S., Turtschi, A., Amaral, L. N. (2005). The worldwide air transportation network: Anomalous centrality, community structure, and cities'' global roles. Proceedings of the National Academy of Sciences, 102(22), 7794-7799.
Hillier, B., Iida, S. (2005) Network and psychological effects in urban movement. In Spatial information theory (pp. 475-490). Springer Berlin Heidelberg.
Holme (2011) found that high clustering with median between-ness made more traffic jam in simulation network.
Hu, Y., Zhu, D. (2009) Empirical analysis of the worldwide maritime transportation network. Physica A: Statistical Mechanics and its Applications, 388(10), 2061-2071.
Hu, M. B., Jiang, R., Wu, Y. H., Wang, W. X., Wu, Q. S. (2008) Urban traffic from the perspective of dual graph. The European Physical Journal B, 63(1), 127-133.
Jassbi, J., Makv, P., Ataei, M., Sousa, P. A. (2011). Soft system modeling in transportation planning: Modeling trip flows based on the fuzzy inference system approach. African Journal of Business Management, 5(2), 505-514.
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).
Jin, W. L. (2012). A kinematic wave theory of multi-commodity network traffic flow. Transportation Research Part B: Methodological, 46(8), 1000-1022.
Josang, A, Elizabeth. G, Michael. K. (2003) Analyzing topologies of transitive trust. In Proceedings of the First International Workshop on Formal Aspects in Security and Trust, FAST2003, 9-22.
Josang, A, Elizabeth. G, Michael. K (2006) Simplification and analysis of transitive trust networks.Journal Web Intelligence and Agent Systems, 4(2), 139-161.
Kaluza, P., Kolzsch, A., Gastner, M. T., Blasius, B. (2010). The complex network of global cargo ship movements. Journal of the Royal Society Interface, 7(48), 1093-1103.
Kernighan, B. W., Lin, S. (1970). An efficient heuristic procedure for partitioning graphs. Bell system technical journal, 49(2), 291-307.
Kerner, B. S. (1999), “Congested Traffic Flow: Observations and Theory,” Transportation Research Record, No. 1678, pp. 160-167.
Krumm, J. (2010). Where will they turn: predicting turn proportions at intersections. Personal and Ubiquitous Computing, 14(7), 591-599.
Kwon, J., Petty, K., Varaiya, P. (2007). Probe Vehicle Runs or Loop Detectors?: Effect of Detector Spacing and Sample Size on Accuracy of Freeway Congestion Monitoring. Transportation Research Record: Journal of the Transportation Research Board, 2012(1), 57-63.
Kwon, J., Mauch, M., Varaiya, P. (2006) Components of congestion: delay from incidents, special events, lane closures, weather, potential ramp metering gain, and excess demand. Transportation Research Record: Journal of the Transportation Research Board, 1959(1), 84-9
Koumousis, V. K., Katsaras, C. P. (2006) A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance. Evolutionary Computation, IEEE Transactions on, 10(1), 19-28.
Krumm, J. (2010). Where will they turn: predicting turn proportions at intersections. Personal and Ubiquitous Computing, 14(7), 591-599.
Lakas, A., Shaqfa, M. (2011) Geocache: sharing and exchanging road traffic information using peer-to-peer vehicular communication. In Vehicular Technology Conference (VTC Spring), 2011 IEEE 73rd (pp. 1-7). IEEE.
Lind, P. G., da Silva, L. R., Andrade Jr, J. S., Herrmann, H. J. (2007) The spread of gossip in American schools. EPL, 78(6).
Ling, X., Hu, M. B., Jiang, R., Wu, Q. S. (2010) Global dynamic routing for scale-free networks. Physical Review E, 81(1).
Litman, T. (2012) Land use impacts on transport. Victoria Transport Policy Institute.
Louch, H. (2000) Personal network integration: transitivity and homophily in strong-tie relations. Social networks, 22(1), 45-64.
Lu, J., Cao, L. (2003). Congestion evaluation from traffic flow information based on fuzzy logic. In Intelligent Transportation Systems, 2003(1), 50-53.
Magyar, G., Johnsson, M., Nevalainen, O. (2000) An adaptive hybrid genetic algorithm for the three-matching problem. Evolutionary Computation, IEEE Transactions on, 4(2), 135-146.
Mao, B., Cao, J., Wu, Z., Huang, G., Li, J. (2012) Predicting Driving Direction with Weighted Markov Model. In Advanced Data Mining and Applications (pp. 407-418) Springer Berlin Heidelberg.
Miller, B. L., Goldberg, D. E. (1995). Genetic algorithms, tournament selection, and the effects of noise. Complex Systems, 9(3), 193-212.
Mitchell, M., Crutchfield, J. P., &; Das, R. (1996, May). Evolving cellular automata with genetic algorithms: A review of recent work. In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA’96).
Mukai, N. (2013). PageRank-based Traffic Simulation Using Taxi Probe Data. Procedia Computer Science, 22, 1156-1163.
Newman, M. E. (2004) Analysis of weighted networks. Physical Review E, 70(5), 056131.
Newman, M. E., Girvan, M. (2004). Finding and evaluating community structure in networks. Physical review E, 69(2).
Pinney, J. W., Westhead, D. R. (2006). Betweenness-based decomposition methods for social and biological networks. Interdisciplinary Statistics and Bioinformatics, 87-90.
Pongpaibool, P., Tangamchit, P., Noodwong, K. (2007) Evaluation of road traffic congestion using fuzzy techniques. In TENCON 2007-2007 IEEE Region 10 Conference (pp. 1-4). IEEE.
Puzis, R., Altshuler, Y., Elovici, Y., Bekhor, S., Shiftan, Y., Pentland, A. (2013) Augmented betweenness centrality for environmentally aware traffic monitoring in transportation networks. Journal of Intelligent Transportation Systems, 17(1), 91-105.
Read, J. M., Keeling, M. J. (2003) Disease evolution on networks: the role of contact structure. Proceedings of the Royal Society of London. Series B: Biological Sciences, 270(1516), 699-708.
Ranjini, K., Kanthimath, A., Yasmine, Y. (2011). Design of Adaptive Road Traffic Control System through Unified Modeling Language. International Journal of Computer Applications, 14(7), 36-41.
Sarroub, L. K. (2002). In-betweenness: Religion and conflicting visions of literacy. Reading Research Quarterly, 37(2), 130-148.
Samira Jaeger (2010) Inference of Surface Membrane Factors of HIV-1 Infection through Functional Interaction Networks.
Scott, J., Carrington, P. J. (2011). The SAGE handbook of social network analysis. SAGE publications.
Schroedl, S., Wagstaff, K., Rogers, S., Langley, P., Wilson, C. (2004). Mining GPS traces for map refinement. Data mining and knowledge Discovery, 9(1), 59-87.
Shu-Bin, L., Jian-Jun, W., Zi-You, G., Yong, L., Bai-Bai, F. (2011) The analysis of traffic congestion and dynamic propagation properties based on complex network.
Sivanandam, S. N., &; Deepa, S. N. (2008). Genetic Algorithm Optimization Problems (pp. 165-209). Springer Berlin Heidelberg.
Small, L., Mason, O. (2013). Information diffusion on the iterated local transitivity model of online social networks. Discrete Applied Mathematics, 161(10), 1338-1344.
Sun, H. J., Zhang, H., Wu, J. J. (2012) Correlated scale-free network with community: modeling and transportation dynamics. Nonlinear Dynamics, 69(4), 2097-2104.
Sun, S., Zhang, C., Yu, G. (2006). A Bayesian network approach to traffic flow forecasting. Intelligent Transportation Systems, IEEE Transactions on, 7(1), 124-132.
Tang, Jie, Sven Seuken, and David C. Parkes. (2010) Hybrid transitive trust mechanisms. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, Vol. 1, May 10-14, 2010, Toronto, Ontario, Canada, 233-240. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems.
Tawfik, A. M. A., Rakha, H. (2012) A Real-World Route Choice Experiment to Investigate Drivers Perceptions and Choices. In Transportation Research Board 91st Annual Meeting (No. 12-3927).
Tsubota, T., Bhaskar, A., Chung, E., Geroliminis, N. (2013). Real time information provision benefit measured by macroscopic fundamental diagram.
Turner, A. (2005) Could a road-centre line be an axial line in disguise. In Proceedings of the 5rd Space Syntax Symposium (Vol. 1, pp. 145-159).
Turner, A. (2007) From axial to road-centre lines: a new representation for space syntax and a new model of route choice for transport network analysis. Environment and Planning B: Planning and Design, 34(3), 539-555.
Tian, Z., Urbanik, T. (2007). System partition technique to improve signal coordination and traffic progression. Journal of Transportation Engineering, 133(2), 119-128.
Ueberschaer, M. H. (1971) Choice of routes on urban networks for the journey to work. Highway Research Record (369).
Vickrey, W. S. (1969). Congestion Theory and Transport Investment. American Economic Review, 59(2), 251–260.
Wei Chien Benny Chin, 2013.Geographically Modified PageRank Algorithms: Measuring the Importance of Nodes in a Geospatial Network.
Whitley, D. (1994) A genetic algorithm tutorial. Statistics and computing, 4(2), 65-85.
Xing, W., and A. Ghorbani. (2004) Weighted PageRank Algorithm. Paper presented at the 2nd Annual Conference on Communication Networks and Services Research, NB, Canada.
Xu, Z., Harriss, R. (2008) Exploring the structure of the US intercity passenger air transportation network: a weighted complex network approach. GeoJournal, 73(2), 87-102.
Yaniv Altshuler, Rami Puzis, Yuval Elovici, Shlomo Bekhor, Alex(Sandy),Pentland.(2013) Journal of Intelligent Transportation Systems:17(1).
Yao L, Guan H, Yan H. (2008) Trip Generation Model Based on Destination Attractiveness, Tsinghua Sci. Technol., 13(5): 632-635.
Yang, X., Liu, J., Vaidya, N. F., Zhao, F. (2004) A vehicle-to-vehicle communication protocol for cooperative collision warning. In Mobile and Ubiquitous Systems: Networking and Services, 2004. MOBIQUITOUS 2004. The First Annual International Conference on (pp. 114-123). IEEE.
Yu, G., Hu, J., Zhang, C., Zhuang, L., Song, J. (2003). Short-term traffic flow forecasting based on Markov chain model. In Intelligent Vehicles Symposium, 2003. Proceedings. IEEE (pp. 208-212). IEEE.
Zhang, C., Sun, S., Yu, G. (2004). A Bayesian network approach to time series forecasting of short-term traffic flows. In Intelligent Transportation Systems, 2004. Proceedings. The 7th International IEEE Conference on (pp. 216-221). IEEE.