그래프 분할을 이용한 서울 수도권 지하철역들의 분류
Classification of the Seoul Metropolitan Subway Stations using Graph Partitioning
1
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
수도권 지하철 시스템은 지하철 역을 결절점으로 하고 이들을 연결하는 선로를 간선으로 구성한 그래프로 표현할 수 있다. 본 논문에서 서울 수도권 지하철 시스템의 통행흐름을 바탕으로 그래프를 거의 비슷한 그룹들로 분할하여 지하철역들의 분류와 지하철 승객들의 통행 특성을 연구한다. 그래프의 각 간선을 통과하는 승객수를 교통카드 트랜잭션 데이터베이스에서 추출하여 그 간선의 가중치로 둔다. 그래프 분할 문제는 NP-완전 문제에 속하기 때문에, 본 논문에서 지하철 시스템의 그래프를 분할하기위하여 휴리스틱 알고리즘을 제안한다. 그 휴리스틱 알고리즘은 두 개의 선택 가능한 목적함수들 중에서 하나를 사용하는 데, 첫 번째 목적함수는 다른 그룹들에 속한 결절점들을 연결하는 간선들의 가중치의 합을 최소화하는 것이고 두 번째는 전체 지하철 승객들에 대해 승차역과 하차역이 같은 그룹에 속한 승객들의 비율을 최대화하는 것이다. 실험결과에서 각 그룹에 속한 지하철역들과 간선들을 색깔로 구분하여 지도상에 표시하고 그룹별 기종점 행렬로 지하철 승객들의 통행 특성을 분석한다.
Abstract
The Seoul metropolitan subway system can be represented by a graph which consists of nodes and edges. In this paper, we study classification of subway stations and trip behaviour of subway passengers through partitioning the graph of the subway system into roughly equal groups. A weight of each edge of the graph is set to the number of passengers who pass the edge, where the number of passengers is extracted from the transportation card transaction database. Since the graph partitioning problem is NP-complete, we propose a heuristic algorithm to partition the subway graph. The heuristic algorithm uses one of two alternative objective functions, one of which is to minimize the sum of weights of edges connecting nodes in different groups and the other is to maximize the ratio of passengers who get on the subway train at one subway station and get off at another subway station in the same group to the total subway passengers. In the experimental results, we illustrate the subway stations and edges in each group by color on a map and analyze the trip behaviour of subway passengers by the group origin-destination matrix.
참고문헌 (18)
- 박종수, "교통카드 트랜잭션 데이터베이스에서 지하철 탑승 패턴 분류", 한국콘텐츠학회 논문지, 10(12), pp.91~100 (2010), 한국콘텐츠학회
- 박종수, "교통카드 트랜잭션 데이터베이스에서 통행 패턴 탐사와 통행행태의 분석", 한국경제지리학회지, 10(1), pp.44~63 (2007), 한국경제지리학회
- 박종수, "서울 대도시권 지하철망의 구조적 특성 분석", 한국경제지리학회지, 11(3), pp.459~475 (2008), 한국경제지리학회
- 박종수, "Pickup Point 최적입지선정을 위한 Greedy Heuristic Algorithm 개발 및 적용 : 서울 대도시권 지하철 시스템을 대상으로", 한국경제지리학회지, 14(2), pp.116~128 (2011), 한국경제지리학회
- 이금숙, "수도권 광역도시철도 하루 시간대별 이용 빈도에 의해 구분된 역 집단과 통행자의 통행 연쇄 패턴 간 관계", 대한지리학회지, 45(5), pp.592~608 (2010), 대한지리학회
- 이금숙, "서울시 대중교통 이용자의 통행패턴 분석", 한국경제지리학회지, 9(3), pp.379~395 (2006), 한국경제지리학회
- "서울 메트로 노선도 서비스"[URL]
- AssunÇão, R.M., "Efficient Regionalization Techniques for Socio-Economic Geographical Units Using Minimum Spanning Trees", International Journal of Geographical Information Science, 20(7), pp.797~811 (2006)
- Chen, C., "Diurnal pattern of transit ridership: a case study of the NewYorkCitysubwaysystem", Journal of Transport Geography, 17, pp.176~186 (2009)
- Graph Partitioning with Natural Cuts, "Delling, D.", Microsoft, ~, pp.MSR-TR-2010-164 (2010)
- Goh, S., "Modification of the gravity model and application to the metropolitan Seoul subway system", PHYSICAL REVIEW E, 86(2), pp.26102~0 (2012), AMER PHYSICAL SOC[DOI]
- Guo, D., "Flow Mapping and Multivariate Visualization of Large Spatial Interaction Data", IEEE Transactions on Visualization and Computer Graphics, 15(6), pp.1041~1048 (2009)
- "METIS: A Software Package for Partitioning Unstructured Graph, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices, Version 5.0"[URL]
- Karypis, G., "A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs", SIAM Journal on Scientific Computing, 20(1), pp.359~392 (1988)
- 이금숙, "Relationship between Diurnal Patterns of Transit Ridership and Land Use in the Metropolitan Seoul Area", 한국경제지리학회지, 15(1), pp.26~41 (2012), 한국경제지리학회[DOI]
- 이금숙, "Master equation approach to the intra-urban passenger flow and application to the Metropolitan Seoul Subway system", JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 44(11), pp.115007~ (2011), Institute of Physics
- Roth, C., "Structure of Urban Movements: Polycentric Activity and Entangled Hierarchical Flows", PLoS ONE, 6(1), pp.e15923~ (2011)
- Tan, P.-N., "Introduction to Data Mining", pp.548~555 (2006), Addison-Wesley