| 논문 정보 | |
| 제목 | Exploiting the graph representation of a real road network: a framework for analysis and routing |
| 저자 |
Chiara Bachechi1 and Laura Po1
|
| 소속 | ’Enzo Ferrari’ Engineering Department, University of Modena and Reggio Emilia, Modena, Italy |
| 저널 | Advances in Databases and Information Systems(ADBIS 2022) Conference |
| DOI | 10.1007/978-3-031-15740-0_7 |
| 주제 | Database, Information System |
| 논문제출일 | 2022.08 |
| 인용수 | 3회 (2025.02.05 기준) |
도로 네트워크를 Neo4j Graph Database에 넣고
교차로 중심성 분석과 같은 여러 가지 분석을 실행한
논문이 있어 읽어보고 정리해보려고 한다
ADBIS 2022에 제출된 Conference Paper이며
다른 논문들에서는 그냥 단순히 primal graph의 형태로
도로 네트워크를 구축했다면
본 논문은 primal graph와 dual graph 두 가지를 이용해서
복합적으로 분석했다는 것이 달랐고
도로 네트워크들과 각 POI들을 매칭한 방법도
소개해주고있어 흥미로운 논문이었다
Introduction
도로 네트워크는 가중치를 가진 다중 방향 그래프로 표현할 수 있다
다양한 연구에서 도로 네트워크를 그래프로 표현하고
단순화하여 모델링하는 연구에 대해 진행하였다
도로 교통 모델링에는 크게 2가지가 있는데
1. primal graph
2. Dual graph
가 있다
Primal graph는 교차로를 node로
도로를 edge로 표현하는 방법이고
dual graph는 이와 반대로
도로를 node로 교차로를 edge로 표현하는 방법이다
dual graph의 경우 도로의 위치 정보와
기하학적 구조를 잃을 가능성이 있어
대부분의 연구에서 primal graph를 이용하지만
dual graph는 도로의 특징을 분석하기에
좋은 구조를 갖고있다
따라서 본 논문에서는
primal graph와 dual graph를 동시에 생성하는
방식을 이용하였다
이를 통해 dual graph의 단순화된 도로 연결 관계를 분석하면서
primal graph의 도로의 실제 기하학적 구조를 보존하는
결합형 모델(combined model)을 구축하였다
본 논문에서는 오픈 소스 지리 데이터를 사용하여
graph database 형식으로 변환하는
framework를 제안한다
본 framework에서는 도로, 교차로, 관심 지점(POI), 교통량 데이터를 포함하며
다양한 조건에서의 최적 경로를 찾을 수도 있고
중심 교차로 및 교통 혼잡 발생 지역 분석과
개방 도로, 폐쇄 도로에 대한 시뮬레이션도 적용할 수 있다
본 연구는 이탈리아 모데나(Modena)시의
도로 네트워크를 사례로 분석하였다
Related Work
Liu, T., Jiang, A., Miao, X., Tang, Y., Zhu, Y., Kwan, H.K.: Graph-based dynamic modeling and traffic prediction of urban road network. IEEE Sensors Journal 21(24), 28118–28130 (2021) https://doi.org/10.1109/JSEN.2021.3124818
Graph-Based Dynamic Modeling and Traffic Prediction of Urban Road Network
Based on various on-road sensor observations, dynamic modeling and analysis of urban road networks becomes an important task of an intelligent transportation system. The major difficulty of this task is that traffic states vary dynamically in both spatial
ieeexplore.ieee.org
위 논문에서는 primal 접근법을 적용한
교통 센서 관측 데이터를 넣은 도로 그래프를 구축하였다
해당 도로 그래프는 모두 무방향 그래프로 구축되었으며
인접한 교통 교차로간의 상관관계에 따라 가중치가 부여된다
그러나 이 방법은 모든 교차로에 교통 센서가 필요하다는 단점이 있다
Jorge, A.A.S., Rossato, M., Bacelar, R.B., Santos, L.B.L.: Gis4graph: a tool for analyzing (geo)graphs applied to study efficiency in a street network. In: GEOINFO (2017)
위 논문에서는 PostgreSQL 데이터베이스를 사용하여
osm 데이터를 분석할 수 있는 기하학적 객체로 변환하였지만
위 논문들에 따르면 graph algorithm은
relational database보다 graph database에서 실행할 때
더 우수한 성능을 보인다
이에 따라 본 논문에서는 Neo4j Graph Database를 사용하였다
위 논문에서는 osm 도로 네트워크를 활용할 수 있는
osmnx 라이브러리를 소개하였다
본 논문에서는 osmnx 라이브러리를 사용하여
primal graph를 생성한 뒤
교통 데이터, POI 노드, 도로 폐쇄 여부, dual graph와 같은
추가적인 데이터들을 연결하였다
위 논문들에서 도시 교통의 흐름을 설명하기위해
다양한 중앙성(centrality) 지표와
교통 흐름 간의 상관관계를 활용하는 방법을 논의하였다
보통 Primal graph에서 진행하였지만
본 연구에서는 dual graph를 활용하여 상관관계를 추가적으로 분석하였다
Road Network Graph Modelling
본 논문에서는 osm 오픈소스 데이터를 활용하였다
osm은 위상적 데이터 구조(topological data structure)를 사용하며
노드(nodes): 크기가 없는 point
경로(ways): node list로 구성되며 polyline 혹은 polygon형태
위 2가지 요소로 구성된다
가장 단순하게 osm 데이터를 그래프로 변환하는 방식은
osm node를 graph의 node로 생성하고
ways를 relationship으로 정의하는 것이다
이러한 방식을 통해 primal graph를 구축한다
이와 같이 그래프를 구축하면 경로 탐색에 유리하지만
node와 relationship의 개수가 너무 많고
네트워크 밀도가 낮다는 한계가 있다
이를 해결하기 위해 dual graph를 적용할 수 있다
도로를 node로 표현하며 각 node는 osm identifier로 구분된다
이렇게 생성된 primal graph와 dual graph는
동일한 graph database에 함께 저장되며
두 그래프 간의 연결 관계를 유지한다
이를 통해 두 가지 접근법의 장점을 모두 이용할 수 있는
통합적인 도로 네트워크 모델을 구축할 수 있다
Primal Graph
Primal Graph는 교차로간의 point-to-point 관계를 나타낸다
osmnx 라이브러리를 사용하여 데이터를 추출한 후
graphml 형식으로 변환하여
APOC 라이브러리를 이용해 Neo4j Cypher query를 작성하여
Neo4j graph database에 인스턴스를 생성하였다
Node
교차로(junction) 노드는 Node로 라벨링
동일한 way를 구성하는 node는 OSMWayNode로 라벨링
Relationship
교차로 노드간의 관계 라벨은 ROUTE로 설정하고
아래와 같은 속성을 포함하였다
고속도로 유형, 도로명, osm identifier, 도로 길이, 도로 상태(active, closed)
POI
OverpassAPI6을 사용하여 식당, 바, 펍, 학교 등의
편의시설(amenities) 데이터를 다운로드하였다
그리고 이를 PointOfInterest 노드로 추가하였다
추가 정보는 Tag라는 노드를 추가하여 연결하였다
POI는 가장 가까운 OsmWayNode와
MEMBER라는 관계로 연결되었다
연결 예시는 아래 Fig1과 같다
여기서 동일한 way를 구성하는 노드를
OSMWayNode로 설정했다는 말이 잘 이해가 안되어서
이것저것 검색해보았다
osm road network 데이터는
node가 단순 junction이 아니라
junction과 junction 사이들에도
여러 node들이 연결되어있고
ways는 따라서 여러 node들이 연결되어있는 형태라고한다
따라서 원래 primal graph에서는 junction을 node로
junction과 junction을 잇는 도로를 edge로 표현하기 때문에
osm 데이터의 node 중 junction은 그냥 'Node'로 라벨링하고
junction과 junction 사이의 여러 다른 노드들은
'OSMWayNode'로 라벨링을 하여
연결해주었다는 뜻이었다
(osm 데이터가 그냥 junction-junction만 이은 데이터인줄알았다..)
아무튼 Italy의 Modena의 primal graph는 아래와 같이 구축되었다
교차로 노드: 19,607개
POI 노드: 841개
‘ROUTE’ 관계: 33,571개
평균 무방향 차수(undirected degree): 3.41
평균 입출력 차수(in-degree, out-degree): 1.71
그래프 밀도(density): 8 x 10^(-5) (도로 네트워크 그래프 특성상 낮은 밀도)
Dual Graph
osm데이터에서 road를 RoadOsm이라는 node로 변환하고
RoadOsm node를 'CONNECTED'라는 관계로 표현하였다
dual graph의 표현방식은 도로 간의 관계를 쉽게 이해하고
도로 네트워크에서 중요한 도로를 식별하는데 유용하다
아래 Fig3은 primal graph와 dual graph의 표현 방식이다
Junction Graph가 primal graph
Road Section Graph가 dual graph이다
왼쪽 junction graph에서 주황색 부분은
road section graph에서는 1개의 node와
3개의 relationship으로 표현된다
동일 지역의 dual graph는 아래와 같이 구축되었다
• 도로 노드(RoadOsm): 4,421개
• ‘CONNECTED’ 관계: 15,037개
• 평균 무방향 차수(undirected degree): 6.8
• 평균 입출력 차수(in-degree, out-degree): 3.4
• 그래프 밀도(density): 7 x 10^(-4) (프라이멀 그래프보다 10배 높은 밀도)
Generation of Traffic Data
본 연구에서는 Modena 지역에 탑재된
400여 개의 유도 루프 감지기를 통해
매분 차량 수와 평균 속도 값을 얻었다
수집된 교통 흐름 데이터는 2018년 11월부터
2021년 4월까지의 데이터를 포함하며
Detection and classification of sensor anomalies for simulating urban traffic scenarios. Cluster Computing 369(2), 853866 (2021) https://doi.org/10.1007/s10586-021-03445-7, https://link.springer. com/article/10.1007/s10586-021-03445-7#citeas
위 논문에서 설명된 방식으로 데이터를 정제하여
SUMO 모델로 시뮬레이션을 실행하였다
(시뮬레이션 관련해선 내가 잘 모르는 부분이라
구체적은 설명은 생략하도록 하겠다
내 연구와 직접적으로 관련된 부분도 아니라..)
각 도로 r에 대하여
AADT(Annual Average Daily Traffic)을 계산하였으며
위와 같은 공식을 사용하였다
N은 주어진 연도의 시뮬레이션 일수
flow r,j,i는 해당 연도의 i번째 날, j번째 시간에 r도로 차선에서 관측된 교통량
을 나타낸다
Integrating traffic data in the graph model
primal graph에 위에서 계산한
AADT 정보를 추가하였다
AADT 정보는 교통량 측정이 시작된 node의 osm id와
교통량이 측정된 끝 node의 osm id를 담고있기 때문에
해당 node사이에 새로운 관계인
AADT를 추가하여 속성으로 AADT 데이터를 저장하였다
또한, 모든 도로에서 교통 데이터를 수집할 수 있는 것이 아니기때문에
아래와 같은 추가적인 방법을 활용해 교통 데이터를 보완하였다
1. 인접한 도로 데이터를 활용한 보정
- 같은 방향의 1~5차 이웃 관계에서 관측된
평균 교통량을 사용하여 부족한 부분을 보완
2. 유사한 도로 유형 기반 보정
- 인접한 도로를 확보할 수 없다면
해당 도로와 비슷한 유형(highway, primary, residential 등)의
평균 AADT값을 사용하여 데이터를 보정
마지막으로 dual graph에서는 각 road 노드에
traffic이라는 속성을 추가하였는데,
긴 도로일수록 높은 교통량을 가질 가능성이 크기 때문에
해당 도로의 평균 AADT를 전체 도로 길이로
나눈 값을 속성으로 traffic 속성으로 저장하였다
Routing
최단 경로는 아래 3가지 방법으로 탐색하였다
1. 이동한 node 개수를 기반으로 평가
- 단순 양방향 BFS 알고리즘 적용
2. 거리를 기반으로 평가
- Haversine distance를 이용하여 A* algorithm 적용
3. 교통량 기반으로 평가
- 첫 번째 시도에서는 교통량을 가중치로 A algorithm을 적용하였지만
도시 외곽과 시골의 도로는 교통량이 낮아 이 방식이 현실적이지 않았다
이 문제를 해결하기 위해 거리와 교통량을 모두 고려한
새로운 가중치를 정의하였다
위 가중치는 거리와 교통량을 정규화하여 동일한 가중치로 합산한 것이다
이러한 방식은 교통량과 경로 길이를 모두 고려한
최적 경로를 탐색할 수 있도록 한다
세 가지 방식을 이용하여 경로를 탐색하였을 때
각 방식마다 차이가 조금씩 있는 것을 확인할 수 있다
Managing Road Closure
도로는 특정 이벤트에 의해서
개방되거나 폐쇄될 수가 있다
이러한 정보를 동적으로 업데이트 시켜줘서
폐쇄된 도로를 피하는 경로를 찾도록 해준다
본 논문에서의 도로 네트워크의 ROUTE 관계는
status라는 속성을 가지고있다
git의 'ChangeStreetStatus' 스크립트를 사용하여
상태를 쉽게 변경할 수 있다
따라서 위 방법을 이용하여
해당 도로와 연결된 모든 ROUTE 관계의
상태를 update 시킨다
또한, 도로가 폐쇄될 경우
경로 탐색이 원활하게 작동할 수 있도록
POI와의 연결 관계를 수정하였다
폐쇄된 도로를 포함하는 모든 노드와 POI간의 관계를 삭제하고
100m 이내의 다른 도로와 새로운 관계를 생성한다
도로가 다시 개방될 경우
기존의 POI 관계를 복원한다
위 Fig 5는 폐쇄된 도로를 우회하여
경로를 탐색하는 알고리즘을 시각화한 것이다
Road Network Anaylsis
지금까지 도로 네트워크를 그래프로 변환하고
이를 Neo4j에 구축하였으므로
Neo4j의 Graph Data Science 라이브러리를 통해
아래 두 가지 목표를 실행하고자한다
1. 도로 네트워크의 구조 혹은 교통량을 사용하여 주요 junction 식별
2. 그래프 위상과 교통량을 고려하여 중요 도로 식별
우선 중요 junction 식별을 위해서
아래 3가지 방법론을 사용한다
1. BC(Betweennes Centrality, 매개 중심성)
2. Harmonic Centrality(HC, 조화 중심성)
3. Degree Centrality(DC, 차수 중심성)
1. Betweenness Centrality(BC, 매개 중심성)
BC는 쉽게 말하면 어떤 교차로가
여러 도로에서 얼마나 자주 지나쳐가는지이다
모든 교차로 쌍을 잇는 최단 경로를 계산하고
각 경로에서 특정 교차로를 지나가는 횟수를 점수로 계산한다
점수 식은 아래와 같다
n은 점수를 매길 교차로
N은 모든 교차로
s와 t는 교차로 쌍이며
sp(s, t | n)은 s에서 t로 가는 최단 경로 중 n을 지나는 횟수
path(s, t)는 s에서 t로 가는 모든 최단 경로의 개수
이다
2. Harmonic Centrality(HC, 조화 중심성)
HC는 어떤 교차로에서 다른 교차로까지가
얼마나 가까운지를 보는 방식이다
모든 다른 교차로까지의 거리를 계산해서
그 역수를 더한다
즉 HC는 점수가 높을 수록
가까운 다른 교차로들이 많다는 뜻이 된다
3. Degree Centrality(DC, 차수 중심성)
DC는 한 교차로에 연결된 도로의 개수를 계산하는 방식이다
기본적으로는 해당 junction과 연결된 도로를 세는 방식이지만
본 논문에서는 도로의 길이와 AADT를 고려한 가중치를 이용한다
따라서 본 논문에서 DC 점수는
해당 junction으로 유입되는 모든 도로의
AADT / 거리 비율의 합으로 평가된다
위의 3가지 방법으로 뽑아낸 Junction들의 점수가
AADT와 얼마나 관련이 있는지를 측정하기위해
Spearman 상관계수를 사용한다
Spearman 상관계수는 두 개의 데이터가
얼마나 비슷하게 변하는지를 특정하는 방법으로
각 값의 크기를 비교해서 순위를 매긴다음
순위끼리의 상관관계를 계산하는 방식이다
값이 1이면 완전히 같은 패턴(연관성이 높음)
0이면 전혀 관련 없음(연관성이 없음)
-1이면 완전히 반대 패턴(연관성이 전혀 반대임)
임을 나타낸다
위 3가지 방식에서 추출된 Junction들의 점수와 AADT간의
Spearman 상관계수를 측정해보면
BC -> 0.12~0.15
HC -> 0.45~0.61
DC -> 0.95가 나와서
Degree Centrality 방식이 도로 정체를 예측하는데에
가장 효율적인 방식임을 알 수 있다
(그런데 DC 계산할 때만 AADT를 가중치로 두고 계산했으니
당연한거 아닌가?....)
아무튼 ..
따라서 DC 방법을 통해 각 Junction별로 점수를 계산하였고
이를 dual graph에서 교차로의 속성으로 추가하였다
이렇게 DC점수가 부과된 dual graph를 바탕으로
PageRank(PR) 알고리즘을 적용하여 주요 도로를 분석하였다
PageRank는 구글을 포함한 유명 검색엔진에서 사용하는
검색 추천 알고리즘인데
이를 도로 네트워크에도 적용할 수 있다고 한다
PageRank 알고리즘의 기본 원리는
각 노드는 링크가 걸린 만큼 점수를 부여받으며
중요한(점수가 높은) 노드로부터 링크되면
그만큼 더 높은 점수를 부여받는다
이렇게 점수를 계산해서 높은 순서대로 추천해주는 알고리즘이
PageRank 알고리즘이다
따라서 본 dual graph에서는
DC를 바탕으로 계산된 점수가 높은
교차로와 연결된 도로가
더욱 중요도가 높은 도로로 뽑히는 것이다
PR 결과로는
최소 0.15에서 최대 7.28 사이의 결과값이 나왔으며
평균 0.95로 좌측으로 치우친 분포를 가진다
평균 + 2 표준편차 이상의 PR 점수를 가진 도로를 뽑아서
총 201개의 도로를 주요 도로로 식별하였다
아래 Fig 6에서는 위와같은 방법으로 추출된
중요한 도로 네트워크를 시각화해서 나타내었다
Conclusion
본 연구에서는 primal graph와 dual graph를 모두 사용하여
1. 주요 교차로를 식별하고
2. 교통량을 반영하여 실제 혼잡도가 높은 도로와 교차로를 분석하였다
또한 이러한 직관적인 분석을 제공하는 framework는
현존하지 않으며
도로 네트워크의 취약성 분석이나
도시 간 네트워크 비교 연구에 활용될 가능성이 있다
여기까지가 논문의 내용이다
conference paper라서 그런가
약간의 허점(?)이 보이는 것 같은데
뭐 내가 남의 논문을 평가할 처지는 안되지만
내가 느끼는 몇 가지 의문점을 정리해보고
논문 리뷰를 마치고자한다
1. routing에 관한 부분은 주제와 관련이 없지 않나?
중간에 살짝 Routing에 관한 얘기가 나오는데
conclusion에 나오는 목표에는 routing에 관한 얘기는 없다
논문의 전체적인 내용을 훑어봐도
본 논문은 오픈소스 지리 데이터를 활용하여
POI + 도로 네트워크 데이터를 구축한 다음
중요 교차로와 중요 도로를 찾아주는
framework의 구현이 최종 목적인 듯 한데
그냥 단순 도로 네트워크를 이용해서
이러한 방식으로 path finding을 할 수 있다는 것을
보여주기 위해서 넣은 것인지가 궁금했다
(약간은 주제와 관련없지않나 하는 생각?)
2. 주요 교차로 점수를 계산하는 방법론 비교에서의 의문
논문 리뷰 중에도 언급했지만
교차로의 점수를 매기는 부분에서
BC, HC, DC 3가지 방법론을 사용해서
AADT와 가장 높은 상관관계를 보인
DC 방법을 교차로의 점수를 매기는 수단으로 활용한다
그런데 계산한 과정을 보면 알겠지만
DC방법에서만 가중치로 AADT를 활용한다
그러면 당연히 DC는 AADT와 상관성이 커지는것 아닌가?
실제로 결과만 봐도 1점이 만점인 상관계수에서
DC는 거의 만점 수준인 0.95가 나온다
(다른 방법들은 높아봤자 0.6에서 그친다)
뭔가 세 가지 계산 방법론을 비교하는 방식에서
약간 의문이 들었다
3. evaluation이 없다
최초로 오픈소스 framework를 구축한 것은 알겠으나
해당 framework에서 추출된
주요 junction이나 주요 road들이
실제로 꽤나 중요한 역할을 하고 있는지..
기존에 다른 framework들이 없더라도
분명 도로나 교차로의 중심성을 분석한
선행연구들은 있었을 것이라고 생각한다
그런 논문들에서 방법론을 가져와서 적용해본다음
본 framework와 결과가 비슷했는지?
아니면 달랐는데 본 framework가 도출한 결과가
사실상 더 우월했다던지?
어떤 점에서 더 우월한건지?
하는 평가가 없다는 점이 아쉬웠다
다른 선행연구에서 방법론을 가져오기 어려웠다면
중요한 도로라고 뽑힌 201개의 도로들이
실제로 어느 정도로 막히는지
실제 Modena시에서 주요 도로라고 식별이 되는지에 대한
정량적 지표라도 가져왔으면
본 framework가 얼마나 높은 정확도를 가지는지
더 납득이 갔을 것 같다
evaluation이 없다보니 신뢰도가 안가는 경향이 있다..
아무튼 위 3개가 내가 논문을 읽으면서 느낀 의문이었다
conference paper라서 그런지
아직 완성을 못한 논문이었을 가능성도 있었을 것 같다
아무튼 내가 연구하고 있는 것과
비슷한 주제여서 읽고 리뷰하기 좋았던 것 같다
그럼 여기서 해당 논문 리뷰 마무리-!