Exploring Maps with Greedy Navigators

During the last decade of network research focusing on structural and dynamical properties of networks, the role of network users has been more or less underestimated from the bird’s-eye view of global perspective. In this era of global positioning system equipped smartphones, however, a user’s ability to access local geometric information and find efficient pathways on networks plays a crucial role, rather than the globally optimal pathways. We present a simple greedy spatial navigation strategy as a probe to explore spatial networks. These greedy navigators use directional information in every move they take, without being trapped in a dead end based on their memory about previous routes. We suggest that the centralities measures have to be modified to incorporate the navigators’ behavior, and present the intriguing effect of navigators’ greediness where removing some edges may actually enhance the routing efficiency, which is reminiscent of Braess’s paradox. In addition, using samples of road structures in large cities around the world, it is shown that the navigability measure we define reflects unique structural properties, which are not easy to predict from other topological characteristics. In this respect, we believe that our routing scheme significantly moves the routing problem on networks one step closer to reality, incorporating the inevitable incompleteness of navigators’ information.

Figure 1

Illustration of three different routing schemes to probe navigability-related structures of cities and buildings. (a) shows SPN from $s$ to $t$; (b) shows the route of GSN (the angles are those used in the algorithm); (c) illustrates a possible route of a random DFS navigation, where the backtracking steps occur at vertices 6 and 9.

Figure 2

An example of the GSN pathway from the entrance $ϵ$ in the left to the central target $\tau$ for LCM (184 vertices and 194 edges) is shown, where the red arrows indicate the pathway with the backtracking processes represented as blue dotted arrows and the SPN path is shown in filled circles. The distances for this specific pair of the source and target with different routing strategies (GSN, random DFS, and SPN, respectively) are $d_g(ϵ\to \tau )=87$, compared to $d_r(ϵ\to \tau )=134.13$ (averaged over ${10}^3$ trials with the standard error 1.067), and $d(ϵ\to \tau )=52$.

Figure 3

Characteristics of vertices and edges of two empirical road maps from Boston (a)–(e) and NYC (f)–(j). We show scatter plots with color-coded density resolving the spatial structure with respect to vertices [(b) and (g)] and edges [(c), (d), (h), and (i)]. We show the relation between betweenness $b$ and navigator centrality $n$ [(b), (c), (g), and (h)] and the relation between navigator essentiality $e$ and betweenness $b$ [(d) and (i)]. The maps [(a) and (f)] show the natural logarithm of the navigator centrality for the vertices (the lower color bars) and edges (the upper color bars). [(e) and (j)] chart the natural logarithm of the absolute values of navigator essentiality [the upper (lower) color bars for normal (Braess) edges, respectively]. In (e) and (j) we also highlight some of the representative $e$ values from panels (d) and (i), respectively.

Figure 4

Scatter plots for the $\nu$ (a) and $\zeta$ (b) vs the number of vertices $N$, for the 100 large cities in the world.