Simplest path betweenness centrality in embedded planar graphs

Abstract

In this thesis we present an alternative definition of distance, which aims to minimize the overall angle sum between adjacent edges in a path from s to t. In addition to this, we propose a corresponding centrality measure, based on betweenness centrality using the proposed definition of distance for paths. This research addresses the observed limitations of shortest path models on accurately capturing human movement, as flow in a network. To explore this concept, we construct an alternative representation of the input graph, which uses the geometrical properties of a graph embedding in the plane. Then we apply the traditional betweenness centrality to this new graph construction. Through a filtering process and visualization of the highest-ranking edges, we observe a difference in the spatial distribution of these edges. Our discussion focuses on the observed variations in the spatial distribution of the traditional betweenness centrality and betweenness centrality using the proposed definition of the simplest path. We highlight a correlation between differences in the size of the sets potential paths between arbitrary pairs of vertices when using the shortest path and the simplest path in grids and the difference in the distribution of the highest-ranking edges. This discussion provides a new look at betweenness centrality in road networks both real and synthetic.