Geometric properties of graph layouts optimized for greedy navigation

The graph layouts used for complex network studies have been mainly 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 encoding useful navigational information to geometric coordinates of vertices of spatial graphs, which is a reverse problem of harnessing geometric information for better navigation. In other words, the coordinates of the vertices are a map of the topology, not the other way around. We use a recently developed 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 compare these layouts to others targeted at better visualization and discuss the spatial statistical properties of the optimized layouts for better navigability and its implication.

Figure 1

Examples of the optimal (a) and KK layout (b) of the BA model. The GSN pathway is $3.85$ ($4.79$) for the optimal (KK) layout, respectively.

Figure 2

A typical time series of $d_g$ in the unit of MC steps $t_{\mathrm{MC}}$ in the BA model used in Fig. 1, along with the real shortest path length $d$, $d_g$ for the optimal layout $L_{\min }$ [Fig. 1a] and the KK layout [Fig. 1b]. The bursting part and almost flat plateau correspond to the heating ($p_{\mathrm{high}}$) and quenching ($p_{\mathrm{low}}$) processes, respectively. The moment of $L_{\min }$ denoted as the vertical line.

Figure 3

Distribution of angles in the optimized (a) and KK (b) layout. At least 18 graph ensembles are used to average for all of the cases.

Figure 4

Average step decreased along the GSN paths in terms of the relative position $f$ along the pathways in the optimized (a) and KK (b) layouts. At least 18 graph ensembles are used to average for all of the cases, and the horizontal axis is equipartitioned into appropriate bins. The error bars represent the standard deviation of the average values of $\Delta d\left(f\right)$ for each graph over different graph ensembles.

Figure 5

An illustration of the definition of deviation from the straight line for a $s$-$t$ pair. Each intermediate vertex's location in the GSN pathway of length 4 (arrows) is compared to the corresponding intermediate points ($f=1/4,1/2$, and $3/4$) equally spaced in the straight line (red line). The deviation for each intermediate point is defined as the Euclidean distance between the two points (blue dashed lines), in the unit of the straight line.

Figure 6

Average deviation from the straight line connecting $s$-$t$ pairs for the relative position $x$ in the GSN pathways and straight lines. Upper (lower) panels correspond to the optimized (KK) layouts, respectively. $\langle \mathrm{dev}\left(f\right)\rangle$ [(a) and (d)] is decomposed into $\langle {\mathrm{dev}}_{\parallel }\left(f\right)\rangle$ [(b) and (e)] and $\langle {\mathrm{dev}}_{\perp }\left(f\right)\rangle$ [(c) and (f)] with respect to the straight line. At least 18 graph ensembles are used to average for all of the cases. The horizontal axis is binned into appropriate equidistant intervals, and the error bars represent the standard deviation of the average values of measures for each graph, over different graph ensembles.