The [**degree distribution**][1] of a graph is of main importance, especially for large graphs, and namely random graphs. Its expected value and its higher [moments][2] 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 of the graph its distance distribution $d(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(k)$$

The expected (value of) 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"][3] yields **180,000** results.

 - Googling for ["distance distribution" "graph theory"][4] yields only **10,000** results.

 - There is an extended article on [degree distributions][1] on Wikipedia.

 - There is no article on [distance distributions][5] on Wikipedia.

How can I understand this?


----------

<sub>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.</sub>

[![!\[enter image description here][6]][6]

[![enter image description here][7]][7]

The shades of green indicate node degrees.


----------

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

[![enter image description here][9]][9]


  [1]: https://en.wikipedia.org/wiki/Degree_distribution
  [2]: https://en.wikipedia.org/wiki/Moment_(mathematics)
  [3]: https://www.google.com/search?q=%22degree%20distribution%22%20%22graph%20theory%22
  [4]: https://www.google.com/search?q=%22distance%20distribution%22%20%22graph%20theory%22
  [5]: https://en.wikipedia.org/wiki/Distance_distribution
  [6]: https://i.sstatic.net/snPyr.png
  [7]: https://i.sstatic.net/VeTI2.png
  [8]: https://en.wikipedia.org/wiki/Configuration_model
  [9]: https://i.sstatic.net/wZSru.png