Skip to main content
added 75 characters in body
Source Link
Matthieu Latapy
  • 1.4k
  • 1
  • 10
  • 28

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 modelWatts 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 consider thanargue 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.

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 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 consider than 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.

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.

Source Link
Matthieu Latapy
  • 1.4k
  • 1
  • 10
  • 28

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 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 consider than 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.