Time to extract vertex coordinates from a graph

Questions
1

I am making large graphs (>400000 vertices) of modest density (6% possible edges). I am embedding them in 2d with the spring-electric embedding and need the coordinates. It runs, what appears to me to be quite slowly. Any thoughts. Note I would have embedded the example notebook, but it was too large. Note this is my first post, so apologies for errors in protocol. Thank you.

ClearSystemCache[]

Timing[g=RandomGraph[{400000,24000000}]]

Timing[g=Graph[g, GraphLayout->"SpringElectricalEmbedding"];]

Timing[vertexLocations=ResourceFunction["VertexCoordinateList"][g];]

Out[6]= {1.95313,Graph[Vertex count: 400000, Edge count: 24000000]}

Out[7]= {0.,Null}

Out[8]= {67.6563,Null}
2

You can see them in the vertexLocations list. For example, the first 10 coordinates may look like thees:

In[5]:= vertexLocations[[1 ;; 10]]

Out[5]= {{1.10698, 1.50615}, {2.19579, 0.841207}, {1.25174, 
  0.799162}, {2.10738, 1.51831}, {1.96417, 1.04546}, {0.680264, 
  0.819208}, {1.21224, 0.478298}, {1.40553, 1.90238}, {2.05948, 
  0.993345}, {0.651144, 0.728469}}
3

I suppose it takes time because the SpringElectricalEmbedding layout requires an optimization with a very large number of parameters.

4

Gianluca
Thank you.The calculation of the vertex coordinates by the Spring Electic Embedding is very fast. The extraction of the coordinates is comparatively slow.

Valeriu
Thank you. I understand. My issue is the run time of the function that generates that array.

5

I agree with Gianluca. I don’t think Graph[g, GraphLayout->"SpringElectricalEmbedding"] actually computes the vertex coordinates. I think it sets an option that determines how they are to be computed, whenever they are needed.

One may infer this, I believe, from the following small example:

g = RandomGraph[{8, 12}];
g = Graph[g, GraphLayout -> "SpringElectricalEmbedding"];
g // InputForm
(*
Graph[{1, 2, 3, 4, 5, 6, 7, 8}, 
 {Null, SparseArray[Automatic, {8, 8}, 0, 
   {1, {{0, 1, 5, 8, 10, 13, 17, 21, 24}, {{6}, {3}, {4}, 
     {5}, {6}, {2}, {6}, {7}, {2}, {7}, {2}, {7}, {8}, {1}, 
     {2}, {3}, {8}, {3}, {4}, {5}, {8}, {5}, {6}, {7}}}, 
    Pattern}]}, {GraphLayout -> {"Dimension" -> 2, 
    "VertexLayout" -> "SpringElectricalEmbedding"}}]
*)

We can calculate the coordinates like this:

GraphEmbedding[g]
(*
{{3.35409, 0.883529}, {1.02062, 1.02716}, {1.47535, 1.45068},
 {0., 1.40268}, {0.611681, 0.}, {2.16284, 0.836485},
 {0.570805, 0.719401}, {1.40896, 0.0658664}}
*)

It’s clear that they are not stored in g, I think.

6

Thank you all,
This makes a lot of sense. I needed a perspective reset.
Rob

7

I’ll add one other thing that occurred to me. If we time the coordinate generation with GraphEmbedding[g] // AbsoluteTiming, the first time takes ~0.05 sec. on my machine. Subsequent times take ~4 x 10^-6 sec. It’s clear to me that the results are cached internally, so that the coordinates are computed only once.

A lightly larger example:

g = RandomGraph[{800, 2000}];
g = Graph[g, GraphLayout -> "SpringElectricalEmbedding"];

GraphEmbedding[g] // Dimensions // AbsoluteTiming
(*  {0.145172, {800, 2}}  *)

GraphEmbedding[g] // Dimensions // AbsoluteTiming
(*  {8.*10^-6, {800, 2}}  *)
8

Is any “spring-like” embedding of interest to you?
I wonder how fast would it be to get the vertex coordinates for the graphs you consider using Graphviz.