March 28, 2011 to April 20, 2011
Europe/Stockholm timezone

Exploring spatial networks with greedy navigators

Apr 1, 2011, 1:30 PM


Dr Sang Hoon Lee (IceLab, Umeå University)


During the last decade, network research has focused on the global structural properties. Fewer studies take the local perspective of agents traveling the network. In this talk I will present a method that uses such a local perspective to integrate topological and spatial properties. This approach, we argue, will be even more important in this era of GPS-equipped smartphones, which give users ability to access local geometric information and navigate efficiently. We use a simple greedy spatial navigation strategy as a probe to explore spatial networks. These greedy navigators use geometric information to guide their moves and have a memory of their route in the network. We apply our method to several real-world networks of roads and railways. The results suggest that centrality measures have to be modified to incorporate the navigators’ behavior. We also see that removing some edges may actually enhance the routing efficiency, which is reminiscent of Braess’s paradox (caused by the conflict between user- and global optima). Furthermore, we present the reverse problem of optimizing the spatial layout of networks themselves to enhance the performance of the greedy spatial navigation. We relate these results, to the positioning of facilities and even architectural design to facilitate the behavior of humans.

Presentation materials

There are no materials yet.