5
$\begingroup$

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:

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.

![enter image description here

enter image description here

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.

enter image description here

$\endgroup$
9
  • $\begingroup$ can you generate those diagrams from the random graph distributions which have been studied specifically for their degree distribution: random k-trees and Barabasi-Albert models, maybe also the small-world model of Watts-Strogatz? $\endgroup$
    – JimN
    Sep 13, 2020 at 7:17
  • $\begingroup$ @JimN: I added diagrams for a random $4$-regular graph. A Watts-Strogatz graph and a power-law graph (Barabasi-Albert) is to come. $\endgroup$ Sep 13, 2020 at 7:56
  • $\begingroup$ random k-trees share the expected/desirable power law distribution in node degrees, like Barabasi-Albert, but B-A lacks higher-order statistics like clique/clustering distributions that k-trees also exhibit. And there are other higher-order distributions that k-trees have which match real-world distributions (like edge embeddedness and overlapping clusters) which other models have. $\endgroup$
    – JimN
    Sep 13, 2020 at 8:07
  • $\begingroup$ To make a random partial k-tree:start with a large clique,store all cliques of size k, choose one uniformly at random and make a new node adj to that chosen k-clique.This creates a clique of size (k+1), so you store more new k-cliques. Now delete some small number of edges(this destroys a number of k-cliques). Again, add a new vertex adj to a uniformly-chosen existing k-clique and repeat. I have a paper on higher-order structures in random models where we tried to argue the importance of going beyond degree distribution: tinyurl.com/yxna36n7 , and (partial) k-trees had the desirables $\endgroup$
    – JimN
    Sep 13, 2020 at 8:13
  • 1
    $\begingroup$ Are you referring to your first picture? Yes, that shows there is a difference in distance distribution and degree distribution. But can you show two 6-regular graphs with different distance distributions where one distribution (correctly) predicts something like contagion-spreading better than the other? If not, the branching factor of 6 is still going to be the main measure an epidemiologist will use to estimate a disease's r-naught value. $\endgroup$
    – JimN
    Sep 13, 2020 at 9:08

4 Answers 4

3
+150
$\begingroup$

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)

$\endgroup$
1
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I only see now that you already answered a question of mine in December last year! That's nice - and I'm still after this issue. Anything new from your side? $\endgroup$ Jul 22, 2021 at 13:29
1
$\begingroup$

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).

  1. 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

  2. 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).

  3. 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).

$\endgroup$
1
  • $\begingroup$ What is frustrating about all the three answers that you have published so far is that you only promote your own articles. It is a very subtle form of spam. In fact, I'm tempted to flag your posts as spam, really. $\endgroup$
    – Alex M.
    Oct 29, 2021 at 15:54
1
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.