8 - Distances in geographically embedded networks

Summary

We now address the geometrical properties of the networks, arising from their embedding in Euclidean space (see Section 4.6). For this purpose, it is useful to consider the spatial arrangement of the networks as measured both in a Euclidean metric and in chemical space. The chemical distance l between any two nodes is the minimal number of links between them (shortest path). Thus, if the distance between the two nodes is r, then l ˜ r^dmin defines the shortest path exponent d_min. We will see that for scale-free networks embedded in d > 1 lattices, d_min < 1, contrary to all known fractals and disordered media where d_min ≥ 1. Nodes at chemical distance l from a given node constitute its lth chemical shell. Thus, the number of (connected) nodes within radius r scales as m(r) ˜ r^df, defining the fractal dimension d_f. Likewise, the number of (connected) nodes within chemical (hop) radius l scales as m(l) ˜ l^d_l, which defines the fractal dimension d_l in chemical (hop) space. The two fractal dimensions are related: d_min = d_f/d_l [BH96, bH00, SA94]. Note that d_min has a meaning only when the network is embedded in Euclidean space. In networks that are not embedded, the relation between M(l) and l exists, but it can only be a power law when the networks are fractals (Chapter 7) or at the percolation threshold (Chapter 10).