Return to 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 (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" 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.

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.

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

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

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

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