A simple maths problem.
If I have a disk of unit radius and place within it $N$ nodes such that the node density $\rho$ is given by
$$\rho=\frac{N}{\pi R^{2}}=\frac{N}{\pi}$$
then connect each node up to anybody within a Euclidean distance 0.4, how long does Mathematica take to evaluate the betweenness centrality of all $N$ nodes? I think it uses Brandes' algorithm (http://en.wikipedia.org/wiki/Betweenness_centrality).
I've tried submitting a job to a supercomputer taking $\rho=1000$ and I'm not sure if this is going to take a day or a year....can anyone estimate the waiting time specifically for the $\rho=1000$ case, or as a function of $\rho$?
To answer my own question, assuming Mathematica uses Brandes' algorithm for unweighted graphs, the time complexity is $\mathcal{O}\left(nm\right)$ where $n$ is the total number of nodes and $m$ the number of edges.
As such, when $\rho\approx1000$, $N=3141$: every node connects to every other within a radius of $r_{0}$, such that the $m$ scales algebraically with $r_{0}$ for fixed $N$.
With $r_{0}=0.4$, Brandes takes over a day, but with $r_{0}=0.07$ (which should just about ensure the network connects), Brandes takes about 4 minutes (when run on a ~3Ghz processor).