Geometric properties of graph layouts optimized for greedy navigation by Sang Hoon Lee and Petter Holme.
The graph layouts used for complex network studies have been mainly been developed to improve visualization. If we interpret the layouts in metric spaces such as Euclidean ones, however, the embedded spatial information can be a valuable cue for various purposes. In this work, we focus on the navigational properties of spatial graphs. We use an recently user-centric navigation protocol to explore spatial layouts of complex networks that are optimal for navigation. These layouts are generated with a simple simulated annealing optimization technique. We compared these layouts to others targeted at better visualization. We discuss the spatial statistical properties of the optimized layouts for better navigability and its implication.
Despite my misgivings about metric spaces, to say nothing of Euclidean ones, for some data, this looks particularly useful.
If you had the optimal layout for navigation of a graph, how would you recognize it? Aside from voicing your preference or choice?
Difficult question but one that the authors are pursuing.
It may be that measurement of “navigability” is possible.
Even if we have to accept that hidden factors are behind the “navigability” measurement.