If I have a Delaunay Graph, what is the mean geodesic distance between two randomly chosen nodes. I know that in a small world network, it is in O(log(N)), with N being the number of nodes.

Thank you!

  • $\begingroup$ The Small World network is just an example, it doesn't have anything to do with the Delaunay graph. I know the result for a Small World, but I do not knowthe answer for a Delaunay Graph $\endgroup$ – Adrien Nivaggioli Dec 10 '18 at 17:02
  • $\begingroup$ Do you mean the least number of edges in a path or the (planar) Euclidean distance by "geodesic distance between two nodes"? $\endgroup$ – John L. Dec 10 '18 at 17:17
  • $\begingroup$ Yes, I understood that the geodesic distance in a graph is the number of nodes (or edges) traversed in the shortest path between two nodes! Sorry that is not true ! $\endgroup$ – Adrien Nivaggioli Dec 10 '18 at 17:18

As you have probably come to the right conclusion by now, for a Delaunay graph, the magnitude of the mean distance between two randomly chosen nodes depends on the particular configuration of the points.

Here is one extreme example. Let each one of the six sided of the triangulated honeycomb have $n$ edges. We will have $3n(n+1)+1$ points. The average distance between two nodes is $\Theta(n)$, which is $\Theta(\sqrt {3n(n+1)+1})$.

We can also consider the row of triangles just above the middle line in that honeycomb as a separate graph. It has $4n+1$ nodes. The average distance between two nodes is $\Theta(n)=\Theta(4n+1)$.

It is intuitive clear that for any given Delaunay graph of $N$ points, the mean distance between two nodes is between $\Theta(\sqrt{N})$ and $\Theta(N)$, which grows much faster than $O(\log(N))$, the mean distance between two nodes in a small-world network. That is one evidence why we call that kind of network small world!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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