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