Efficiently finding furthest two nodes in a graph

Question

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.

Answer 1

For large graphs, "PseudoDiameter" method could help:

g = RandomGraph[BernoulliGraphDistribution[10000, 0.5]];

GraphDiameter[gtest, 
  Method -> "PseudoDiameter"] // AbsoluteTiming

{181.635, 2}

GraphDiameter[gtest, 
  Method -> {"PseudoDiameter", 
    "Aggressive" -> False}] // AbsoluteTiming

{1.42781, 2}

PseudoDiameter finds an approximate graph diameter. It works by starting from a vertex u, and finds a vertex v that is farthest away from u. This process is repeated by treating v as the new starting vertex, and ends when the graph distance no longer increases. A vertex from the last level set that has the smallest degree is chosen as the final starting vertex u, and a traversal is done to see if the graph distance can be increased. This graph distance is taken to be the pseudo-diameter.

“Aggressive” -> True or False — whether to make extra effort in finding the optimal graph diameter

To find path, GraphPeriphery could be used:

GraphPeriphery[g, 
  Method -> {"PseudoDiameter", 
    "Aggressive" -> False}] // AbsoluteTiming

{1.23822, {2615, 181}}

FindShortestPath[g, Sequence @@ %[[2]]]

{2615, 18, 181}

Answer 2

Basically a brute-force approach and thus probably not more efficient than GraphDiameter, but a way to obtain also a path that realizes the diameter:

n = 100;
p = 0.05;
g = RandomGraph[BernoulliGraphDistribution[n, p]];
A = GraphDistanceMatrix[g];
maxdistpairs = Position[UpperTriangularize[A, 1], Max[A]];
maxpath = FindShortestPath[g, ##] & @@ maxdistpairs[[1]];

HighlightGraph[g, UndirectedEdge @@@ Partition[maxpath, 2, 1]]

If the graph is disconnected, the empty list {} is returned as maxpath.

Edit

This is just a heuristic but it tends to deliver surprisingly good results. It is based on the intuition that the minimum and the maximum of the first eigenvector of the graph Lapacian tend to be be well separated. So this method computes the first eigenvector v and extracts its minimum and maximum

Generating a large connected graph:

g = RandomGraph[{10000, 14000}];
comp = ConnectedComponents[g];
g = IndexGraph@Subgraph[g, comp[[Ordering[Length /@ comp, -1][[1]]]]];

Solving the eigenvalue problem and extracting maximum i and maximum j:

A = With[{a = SparseArray[{N@VertexDegree[g]}]},
   ArrayFlatten[{
     {N@KirchhoffMatrix[g], a\[Transpose]},
     {a, 0.}
     }
    ]
   ];
{\[Lambda], u} = Eigensystem[A, -1, Method -> "Arnoldi"];
v = Most[u[[1]]];
i = Ordering[v, -1][[1]];
j = Ordering[v, 1][[1]];
path = FindShortestPath[g, i, j];
estimateddiameter = Length[path] - 1
truediameter = Max[GraphDistanceMatrix[g]]

I have not theorem however that could certify the quality of this approximate diameter.

Maybe you find something useful in this script by Fan Chung. At least upper bounds for the diameter in terms of eigenvalues can be found there; these could be used to assess the quality of the approximation a posteriorily.

Answer 3

IGraph/M has IGDiameter for computing the diameter and IGFindDiameter for finding a longest shortest path, including the endpoints.

Diameter computation is approximately cubic in the number of vertices. Based on a quick fit, I expect a 300 second (5 minute) running time for a RandomGraph[BernoulliGraphDistribution[10000, 0.5]]. Now you know how long you need to wait—so try it!

Example:

g = RandomGraph[BernoulliGraphDistribution[1000, 0.5]];

IGDiameter[g] // Timing
(* {0.355301, 2} *)

IGFindDiameter[g] // Timing
(* {0.332708, {1, 4, 2}} *)