Does anyone know what the complexity of Mathematica's GraphDiameter algorithm is? I have a family of very large (and very regular and very sparse) graphs, and if Mathematica uses something like the Johnson algorithm, it is feasible, but $O(V^3)$ algorithms are right out - $V$ is in the several million range.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ Are your graphs weighted? $\endgroup$– SzabolcsJul 21, 2016 at 6:57
-
$\begingroup$ No, they are not (some of them may be directed, though...) $\endgroup$– Igor RivinJul 21, 2016 at 16:08
-
$\begingroup$ Then you won't run into the performance problem with igraph. In fact it is usually slightly faster than Mathematica for undirected (occasionally slightly slower). Most importantly it'll spare you the memory problem. There are also functions for counting how many shortest paths are there of each length, again without the need to keep the full distance matrix in memory. This is what I specifically needed for my own work. $\endgroup$– SzabolcsJul 21, 2016 at 16:23
-
$\begingroup$ @Szabolcs any progress on this? With bated breath... $\endgroup$– Igor RivinAug 17, 2016 at 0:20
-
$\begingroup$ I just sent you an email. If you didn't get it, please email me. $\endgroup$– SzabolcsAug 17, 2016 at 8:42
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
If you need to compute diameters for large graphs, you should be aware that GraphDiameter tends to use an unreasonable amount of memory (up to gigabytes). Based on its memory use, I believe that it computes the complete GraphDistanceMatrix first, and then just takes the largest element.
I have reported this to WRI on Feb 13 this year, and support confirmed the problem.
Because of this problem, I exposed igraph's diameter calculation function in IGraph/M. How it compares in performance to Mathematica's builtin depends on the problem (the performance tends to be similar). But I simply wasn't able to do the calculation for large graphs with GraphDiameter because it ran out of memory.
The methods available for the builtin are documented:
{"Dijkstra", "FloydWarshall", "Johnson", "PseudoDiameter"}
I am not familiar with all of these so I cannot tell you about their complexity. "PseudoDiameter" does an approximation only.
Here is a test for a sparse graph, both weighted and unweighted versions. igraph is supposed to use Dijkstra for weighted graphs.
SeedRandom[42];
g =
First@ConnectedGraphComponents@
RandomGraph[BernoulliGraphDistribution[4000, 0.001]];
wg =
SetProperty[g, EdgeWeight -> RandomReal[1, EdgeCount[g]]];
Unweighted:
Table[
{m, AbsoluteTiming@GraphDiameter[g, Method -> m]},
{m, {"Dijkstra", "FloydWarshall", "Johnson", "PseudoDiameter"}}
]
(* {{"Dijkstra", {1.64515, 13.}}, {"FloydWarshall", {48.7639, 13.}},
{"Johnson", {1.77069, 13.}}, {"PseudoDiameter", {0.000592, 13}}} *)
Weighted:
Table[
{m, AbsoluteTiming@GraphDiameter[wg, Method -> m]},
{m, {"Dijkstra", "FloydWarshall", "Johnson", "PseudoDiameter"}}
]
(*
{{"Dijkstra", {2.54546, 6.07364}}, {"FloydWarshall", {51.3041, 6.07364}},
{"Johnson", {2.68918, 6.07364}}, {"PseudoDiameter", {2.70202, 6.07364}}}
*)
IGraph/M unweighted:
<< IGraphM`
IGDiameter[g] // AbsoluteTiming
(* {0.613409, 13} *)
Weighted:
IGDiameter[wg] // AbsoluteTiming
(* {34.0476, 6.07364} *)
Here's some more benchmarking for the weighted one with IGraph/M:
IGDistanceMatrix[wg, Method -> "Johnson"] // Max // AbsoluteTiming
(* {4.46778, 6.07364} *)
IGDistanceMatrix[wg, Method -> "BellmanFord"] // Max // AbsoluteTiming
(* {3.95098, 6.07364} *)
IGDistanceMatrix[wg, Method -> "Dijkstra"] // Max // AbsoluteTiming
(* {4.43047, 6.07364} *)
I will have to look into what is going on and why this is so much faster than IGDiameter. The underlying C layer of igraph has the habit of overriding the user's method choice. I am simply exposing this C layer to Mathematica.
Update: I reported the performance problem with igraph's diameter calculation function. It has been fixed. IGraph/M version 0.3.0 will include the fix. New timing is 3.2 s instead of 34 s.
answered Jul 20, 2016 at 20:17
-
$\begingroup$ Does IGraph/M export something like Mathematica's VertexEccentricity[]? I could not find it in the documentation.... (I have some vertex transitive graphs, so this would be way faster than diameter...) Thanks! $\endgroup$ Aug 9, 2016 at 1:34
-
$\begingroup$ @IgorRivin No, not without calculating the full distance matrix. But I made a note to add this in the next version. It will be in 0.3.0, if I ever get the time to finish it ... $\endgroup$– SzabolcsAug 9, 2016 at 8:54
-
$\begingroup$ Thanks, Szabolcs! Maybe I will just go to igraph in the meantime (for large graph, Mathematica bombs out of space [no surprise there...]) $\endgroup$ Aug 9, 2016 at 12:50
-
$\begingroup$ @IgorRivin What operating system do you usually use? $\endgroup$– SzabolcsAug 9, 2016 at 12:58
-
$\begingroup$
$\endgroup$
Hiding behind Details and Options on the documentation page is
Method Automatic Method to use
and
Possible Method Settings include "Dijkstra", "FloydWarshall", "Johnson", and "PseudoDiameter".
