5th November, 2019
Detecting Highways on Large Networks
Highways are high-speed multi-lane roads which facilitate long-distance travelling in road networks. The properties of those highways yield some practical and theoretical implications which have been the motivation and foundation of many efficient route planning algorithms. In our work, we discuss the underlying structural concepts of highways and propose a formal definition for highways in networks. We provide a fast way of computing such highways based on a modification of Brandes' algorithm. Furthermore, we introduce an approximation approach which makes the computation even faster by two orders of magnitude. In our experiments, we show that our method Highway-Paths Ratio can identify up to 99% of all highway segments in real road networks. Additionally, we define a new contraction order for Contraction Hierarchies, a fast route planning algorithm based on vertex contraction. Our contraction order is solely based on our definition of a highway network and performs similarly good as the original approach Edge Difference, hence demonstrating that our highway definition finds an inherent hierarchical structure in the road network. The argument of finding an inherent structure is further supported when we compare the original road networks with random networks of the same degree distribution and the same weights. We discover a unique distribution of our highway edge scoring compared to the random networks, which in contrast to the original network follow a nearly log-normal distribution. This versatile toolkit of contraction order and value distributions in the original and random networks allows us to not only detect and verify highway-like structures in road networks but also in other types of networks. With our analysis on six networks from various domains, we lay the foundation for the highway detection and analysis in general networks and we hope to motivate research on the detection and analysis of highway-like structures on various types of networks.
Go to thesis