Efficiently finding furthest two nodes in a graph

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}

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.

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}} *)