Navigating networks with limited information

We study navigation with limited information in networks and demonstrate that many real-world networks have a structure which can be described as favoring communication at short distance at the cost of constraining communication at long distance. This feature, which is robust and more evident with limited than with complete information, reflects both topological and possibly functional design characteristics. For example, the characteristics of the networks studied derived from a city and from the Internet are manifested through modular network designs. We also observe that directed navigation in typical networks requires remarkably little information on the level of individual nodes. By studying navigation or specific signaling, we take a complementary approach to the common studies of information transfer devoted to broadcasting of information in studies of virus spreading and the like.

Figure 1

(Color) Search information $I(s\to t)$ measures the average number of bits one needs in order to walk along one of the shortest paths from $s$ to $t$. It can be sampled by walking along the shortest paths between $s$ and $t$: (a) For nodes with a unique direction to the target, this direction is selected with an information cost ${\log }_2\left(k_j\right)$. (b) For nodes $j$ at branch points between degenerate paths, the exit links are selected with probability $q_{jit}$ (colored after value) proportional to $p_{jit}$, the probability that a random walker at that exit would reach the target along a shortest path. Let, for example, the probability to leave node $s$ to the left be $q$ and accordingly $1-q$ to take the right way (the probability is zero to go downwards in the figure since these links are not on a shortest path to $t$). Then, $I(s\to t)\left(q\right)=[{\log }_{2}4+q{\log }_{2}q+(1-q){\log }_2(1-q)]+[q{\log }_{2}2+(1-q){\log }_{2}6]$, where the first set of parentheses is the information cost on node $s$ and second set of parentheses the cost on the following step, left and right, respectively. We look for a $q$ that minimizes $\left\{I(s\to t)\left(q\right)\right\}$, giving $q=(1∕2)∕(1∕6+1∕2)=0.75$. $I(s\to t)=3.0$ in (a) and $I(s\to t)\approx 2.6$ in (b).

Figure 2

(Color) Search with limited information: At each node $j$ along a path from $s$ towards the target $t$, the information cost is limited by $ı\text{bits}$, or equivalently, only $ı\text{bits}$ are accessible. The color of the links represents $q_{jit}$, the probability to leave node $j$ along a link to node $i$ on a path towards $t$. With limited information the weighted exit probabilities $q_{jit}$ are changed according to $(q_{jit}+{ϵ}_{jt})∕(1+k_j{ϵ}_{jt})\to q_{jit}$ to satisfy ${ı}_{jt}⩽ı$. In (a) there is no upper limit, or $ı=\infty$, and the case reduces to the one in Fig. 1b with $I_{\infty }(s\to t)\approx 2.6\text{bits}$ and the excess walk $\Delta l=0$. In (b) $ı=0.2$ and $I_{0.2}(s\to t)\approx 0.7\text{bits}$ and the excess walk $\Delta l\approx 2.5$.

Figure 3

(Color online) Search with limited information in Erdös-Rényi (ER) networks and scale-free (SF) networks with degree distribution $P\left(k\right)\propto 1∕{(k_0+k)}^{\gamma }$ parametrized by $\gamma$ and $⟨k⟩$. (a) As the available information at each node decreases with decreasing $ı$, the typical path length for going between two nodes increases by $\Delta l$ beyond the length of the shortest path between the nodes. The inset demonstrates that $\Delta l$ is nearly independent of the length of the shortest path between nodes for $l>2$. (b) The variation of $I_{ı}$ as a function of the available node information $ı$. (c) The typical search information $I_{ı}$ first decreases and then subsequently increases as the walk length increases due to the limits on $ı$.

Figure 4

(Color online) Overall navigability of real-world networks, compared to their random counterparts presented as $Z$ scores, for four levels of $ı=\infty$,4,2, $1\text{bits}∕\text{node}$ together with the corresponding average excess path length $\Delta l$. $\Delta l$ shown in the figure is for the real networks, but it also very well represents the randomized counterparts. The Internet (hardwired Internet of autonomous systems [15]) is more sensitive to limited information than the similarly sized CEO (chief executive officers connected by links if they sit at the same board [16]). The city network is the Swedish city Malmö with streets mapped to nodes and intersections mapped to links [5]. The two biological betworks are the protein-protein interaction networks of Saccharomyces Cerevisiae (yeast) [17] and Drosophilia melanogaster (fly) [18].

Figure 5

(Color) Information horizon of (a) three real-world networks from Fig. 4 and (b) three model networks of size $N=1000$; one modular and two scale-free networks with degree distribution $P\left(k\right)\propto k^{-2.4}$, organized to be, respectively, degree hierarchy and degree antihierarchy [19]. We compare information associated to navigation between nodes at distance $l$, with the navigation in randomized counterparts (keeping the degree sequence) for $ı=\infty$, 2, and 1.

Figure 6

(Color online) The average degree $⟨k⟩$ of nodes as function of distance from a random node, in units of what it is in a randomized version. The networks are the same as studied in Fig. 5a. A relative high value of $⟨k⟩$ is associated with the information barrier, as indeed seen by comparing $⟨k\left(\mathcal{l}\right)⟩∕{⟨k\left(\mathcal{l}\right)⟩}_{\text{random}}$ with the $I\left(\mathcal{l}\right)-I_{\text{random}}\left(\mathcal{l}\right)$ in Fig. 5a.