I am trying to learn how in an efficient way can one find the diameter of a random graph, that is, the longest shortest path, and its corresponding end-nodes.
The direct built-in function GraphDiameter
seems to work normally and quite rapidly for small systems. What I do is as follows: generate a random ER graph with n
nodes and edge probability p,
check that it is connected, if yes find the diameter of the graph.
n = 10;
p = 0.5;
gtest = RandomGraph[BernoulliGraphDistribution[n, p]]
If[ConnectedGraphQ[gtest] == True, d = GraphDiameter[gtest];
Print[d];]
For such parameter it works quite rapidly and usually returns diameters of around $3,$ though it doesn't return the end-nodes this distance corresponds to.
But for much larger graphs, namely $n=10^4,$ and still $p=0.5,$ even in cases the graph is indeed connected, GraphDiameter
simply returns $Aborted[].
Which I assume means the search was taking too long and the kernel aborted it.
In the light of this, my questions are:
- What is happening when the abort message is being returned?
- Is there a way to efficiently obtain the graph diameter even for such large graphs within Mathematica? Or is the built-in
GraphDiameter
function known to be the most efficient option within Mathematica? - Is asking for the end-nodes corresponding to the found diameter an additional overhead in terms of computation or it can easily be retrieved if a finite diameter has been found?
Any feedback on these types of computations on graphs would be much appreciated.
GraphPeriphery
help? $\endgroup$ – Chip Hurst Jul 31 '19 at 14:05GraphPeriphery
lists all such vertices, it doesn't indicate which two vertices are maximally distant, unless there are only 2 such vertices, i.e. the diameter corresponds to a unique $(i,j)$ tuple. $\endgroup$ – user52181 Jul 31 '19 at 15:40$Aborted[]
withGraphDiameter
either. Maybe you run out of memory? $\endgroup$ – Szabolcs Aug 1 '19 at 6:50n=10000
andp=0.2,
IGDiameter
did finish and correctly found a diameter of $2$ taking $543$ sec (absolute timing). For the same graph the suggested solution of user halmir takes $144$ sec and only $0.7$ sec whenAggressive
is set toFalse,
both yielding same result of $2.$ $\endgroup$ – user52181 Aug 1 '19 at 9:32