5
$\begingroup$

I have a graph with ~ 360 000 nodes and ~90000000 edges. Unfortunately, I can't create a graph from the list of edges, the process not converge. An example of the code is:

  Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3,3 \[UndirectedEdge] 1}]

But when I create a random graph with these parameters the function succeeds into 1.5 minutes.

Any suggestion how I can improve my code?

$\endgroup$
  • 1
    $\begingroup$ Try repeatedly reducing the size of your problem by 2x or 10x, while keeping the essential character of your problem, until you get something small enough that it will run. Then measure the memory used for this and for a few smaller iterations. Be careful that the Mathematica cache doesn't give you the wrong impression. From those results estimate the amount of memory needed for your full problem. If the answer is something less than 64GB then buy more memory. If it is something more than 100s of GB then you know this isn't going to work without a very different implementation. $\endgroup$ – Bill Jun 9 '18 at 6:29
  • $\begingroup$ Thank you For the ~tenth part of the original problem, I succeed to create a graph, and it takes around 8 GB of the memory, but I'm not sure that the problem grows linearly. Then maybe I need another software or a different implementation (unfortunately all my algorithms using the WL's Graph object :( ) $\endgroup$ – Kiril Danilchenko Jun 9 '18 at 6:46
  • 1
    $\begingroup$ See if you can eliminate all other memory used and try to do 1/8, 1/16, 1/32 of the original problem while trying to maintain the scaling of everything else. That may help determine whether linear, quadratic, exponential or perhaps even sub-linear. If you get 1/10 of the problem in 8GB then you might have a chance with 64GB. It will be stunningly slower than ram, but you could try bumping the swap space on your drive up to say 32 or 64GB and see if you can get 1/4 or even 1/2 of your problem to run. That will give you some idea what you are facing. $\endgroup$ – Bill Jun 9 '18 at 9:01
  • $\begingroup$ I deleted my answer because I cannot remember the details of what situations it is useful in. I will repost it if I can remember and demonstrate its utility. $\endgroup$ – C. E. Jun 9 '18 at 19:49
  • $\begingroup$ What is it what you want to do with the graph? Maybe it can be done with the adjacency alone. Do you have the edges given or do you want to generate randomly? That's not very much information that you share there... $\endgroup$ – Henrik Schumacher Jun 9 '18 at 21:19
2
$\begingroup$

The following creates a random graph by first building its adjacency matrix and using the post by C.E. in to turn it into a graph. Note that we never want to plot the graph. It's just too complex. So we don't need such luxury as an embedding onto the plane. Thus, we turn off its computation with GraphLayout -> None.

The following function turns a number between 1 and n(n-1) into an offdiagonal pair {i,j} and can be interpreted as directed edge.

idx2edge = Compile[{{idx, _Integer}, {n, _Integer}},
   Block[{i, j},
    j = Mod[idx, n - 1, 1];
    i = Quotient[idx - j, n - 1] + 1;
    If[j >= i, {i, j + 1}, {i, j}]
    ],
   CompilationTarget -> "C",
   RuntimeAttributes -> {Listable},
   Parallelization -> True,
   RuntimeOptions -> "Speed"
   ];

This creates a random graph with 360000 vertices and 90000000 directed edges.

n = 360000;
m = 90000000;

G = With[{edges = idx2edge[RandomSample[Span[1, n (n - 1)], m], n]},
    Graph[
     Automatic,
     {Null, SparseArray[edges -> 1, {n, n}]},
     GraphLayout -> None
     ]
    ]; // MaxMemoryUsed // AbsoluteTiming

{95.038, 6467484368}

722950008

So, the computations require not much more than 6 GB and the final graph can be stored in less than 700 MB.

Remark

Actually, the graph produced is not directed. I am not familiar with the syntax Graph[Automatic, {Null, sa}], so maybe C.E. can tell us how a directed graph can be generated this way.

$\endgroup$
  • $\begingroup$ @C.E. That's a very interesting syntax you use there to produce a graph from its adjacency matrix. Is it possible to also create a directed graph this way? Would you explain the syntax a bit? Where can we find some details (I am aware that this might be undocument). $\endgroup$ – Henrik Schumacher Jun 9 '18 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.