The distance distribution of graphs

Question

The degree distribution of a graph is of main importance, especially for large graphs, and namely random graphs. Its expected value and its higher moments tell a lot about a graph – but of course not everything.

The distance distribution $D(k)$ of a graph is possibly of equal importance. First determine for each vertex $i$ of the graph its distance distribution $d_i(k)$ giving the numbers of $k$-order neighbours ($1$-order neighbours being the immediate neighbours). Then calculate the normalized sums

$$D(k) = \frac{1}{N}\sum_{i=1}^N d_i(k)$$

The expected distance between two nodes is the expected value of this distribution. But the distribution has higher moments which may tell something interesting about the graph.

My impression is that the so-defined distance distribution (and no other definition comes to my mind) is roughly as informative as the degree distribution (even though in other respects), but in the literature it is significantly underrepresented:

• Googling for "degree distribution" "graph theory" yields 180,000 results.

• Googling for "distance distribution" "graph theory" yields only 10,000 results.

• There is an extended article on degree distributions on Wikipedia.

• There is no article on distance distributions on Wikipedia.

How can I understand this?

---

_{In the following examples one can see that for regular graphs like Euclidean tilings (examples 1 to 4) the distance distributions look very much the same (even more than the degree distributions), but for the hyperbolic tiling $(3.4)^3$ and an Erdös-Renyi graph, the distance distribution looks qualitatively different.}

The shades of green indicate node degrees.

---

For some random graph distributions generated by the configuration model (625 nodes, mean degree 4). A power-law distribution of node degree is to come.

Answer 1

Q: Why is the degree distribution of vertices more widely studied than the distance distribution of links?

A: Vertices are more fundamental than links, in the following sense:
A vertex is associated with a scale, its degree (= number of nodes connected to it), which is determined only by the topology of the network. A link, on the other hand, has no intrinsic scale. One would need to attribute a weight to each link, such as its length, to define a scale, but there is no unique way to do that for a given network topology.

The lack of an intrinsic scale diminishes the fundamental interest of the link distance distribution. For that reason, Zhou, Meng, and Stanley [1] have recently studied an alternative distance distribution, the degree distance distribution, which does have an intrinsic scale. The degree distance $d$ of a link connecting two vertices of degree $k$ and $k'$ is defined as $d=\log|k-k'|$.

The authors argue that a power law degree distance distribution better represents the scale-free property of a network than a power law degree distribution.

[1] Bin Zhou, Xiangyi Meng, and H. Eugene Stanley, Power-law distribution of degree–degree distance: A better representation of the scale-free property of complex networks (2020)

Answer 2

I see several reasons why degree distributions may be preferred to distance distributions.

First, degrees are more robust than distances, in the following sense: adding or removing one or a few links have a small impact on the degree distribution, whereas it may have a dramatic impact on distance distributions. In particular, adding a few random links (which may reflect erroneous measurements in practice) makes the average distance drop very quickly. This is one of the key principles underlying the Watts and Strogatz model, by the way.

Second, in practice, computing degree distributions is trivial, whereas computing distance distributions is costly; it typically requires $O(n\cdot m)$ time on graphs with $n$ nodes and $m$ links. This is often prohibitive. Approximations may help, but the problem remains much harder than degree distributions, and some values missed by the approximation may be important for the distribution.

Third, as one may see in your examples, distance distributions are often quite centered around their mean, with few exceptions. Actually, as I said, adding just a few random links is often sufficient to obtain this effect. Instead, observed degree distributions often span several orders of magnitude, which may be seen as more informative: degrees somehow make more difference between nodes than distances.

Finally, notice that distances make sense only between pairs of nodes in the same connected components. If the considered graphs are not connected, then it may be unclear how to interpret distance distributions.

One may also argue that sampling random graphs with prescribed degree distributions makes more sense (or is easier?) than sampling random graphs with prescribed distance distribution. This makes degree distributions more appealing both in practice, when one indeed generates random graphs, and in theory, as proving property of these random objects may be tractable.

Answer 3

I think that distance distributions are actually much more interesting and informative than degree distributions of graphs. The reason is that graphs with the same degree distributions can have very different properties, including very different distance distributions. Examples are the Node Duplication model of random graphs and the Barabasi-Albert (preferential attachment) that exhibit a power-law degree distribution but have a very different structure. The reason there is much more interest in the degree distribution is because it is easier to analyze. However, much higher quality information about nodes is obtained via distances.

There are some results available for distances in random graphs, notably

1. Distances in Erdos-Renyi graphs: E. Katzav, M. Nitzan, D. ben-Avraham, P.L. Krapivsky, R. Kuhn, N. Ross and O. Biham, Analytical results for the distribution of shortest path lengths in random networks, EPL 111, 26006 (2015).

as well as in:

I. Tishby, O. Biham, E. Katzav and R. Kuhn, Revealing the Micro-Structure of the Giant Clusters in Random Graph Ensembles, Phys. Rev. E 97, 042318 (2018).

and

E. Katzav, O. Biham and A. Hartmann, The distribution of shortest path lengths in subcritical Erd{\H o}s-R'enyi networks, Phys. Rev. E 98, 012301 (2018).

2. Distances in configuration model networks: M. Nitzan, E. Katzav, R. Kuhn and O. Biham, Distance distribution in configuration model networks, Phys. Rev. E 93, 062309 (2016). In particular, there is an exact result for random regular graphs

3. Distances in undirected node-duplication networks: C. Steinbock, O. Biham and E. Katzav, The distribution of shortest path lengths in a class of node duplication network models, Phys. Rev. E 96, 032301 (2017).

4. Distances in directed node-duplication networks: C. Steinbock, O. Biham and E. Katzav, The distribution of shortest path lengths in directed random networks that grow by node duplication, Eur. Phys. J. B 92, 130 (2019).

Answer 4

The point is that the nature of these two distributions is completely different. The degree distribution is local: in order to find it one one just has to know how the 1-neighbourhoods of vertices look like. The distance distribution is global. Essentially, it measures the dependence of the size of the graph distance spheres on radius, i.e., the growth of the graph. Needless to say that, for instance, two regular graphs with the same (constant) vertex degrees may look very very different.

Several reasons for the "preference" given to degree distributions have already been exposed here. I think that the main one is, actually, a manifestation of the "streetlight effect". As Matthieu Latapy put it in his answer, "computing degree distributions is trivial, whereas computing distance distributions is costly".