Why does Kamada-Kawai fail on a Bethe lattice? #963

Open
szhorvat opened this Issue Sep 12, 2016 · 2 comments

Projects

None yet

3 participants

@szhorvat
Contributor
szhorvat commented Sep 12, 2016 edited

This refers to what's in the master branch of the C core, not the released version. This is also what's included in the current R version, but not in Python. R code is at the end.

Let's make a partial Bethe lattice. In Mathematica,

links = {0 -> 1, 0 -> 2, 0 -> 3, 1 -> 4, 1 -> 5, 2 -> 6, 2 -> 7, 
   3 -> 8, 3 -> 9, 4 -> 10, 4 -> 11, 5 -> 12, 5 -> 13, 6 -> 14, 
   6 -> 15, 7 -> 16, 7 -> 17, 8 -> 18, 8 -> 19, 9 -> 20, 9 -> 21, 
   10 -> 22, 10 -> 23, 11 -> 24, 11 -> 25, 12 -> 26, 12 -> 27, 
   13 -> 28, 13 -> 29, 14 -> 30, 14 -> 31, 15 -> 32, 15 -> 33, 
   16 -> 34, 16 -> 35, 17 -> 36, 17 -> 37, 18 -> 38, 18 -> 39, 
   19 -> 40, 19 -> 41, 20 -> 42, 20 -> 43, 21 -> 44, 21 -> 45, 
   22 -> 46, 22 -> 47, 23 -> 48, 23 -> 49, 24 -> 50, 24 -> 51, 
   25 -> 52, 25 -> 53, 26 -> 54, 26 -> 55, 27 -> 56, 27 -> 57, 
   28 -> 58, 28 -> 59, 29 -> 60, 29 -> 61, 30 -> 62, 30 -> 63, 
   31 -> 64, 31 -> 65, 32 -> 66, 32 -> 67, 33 -> 68, 33 -> 69, 
   34 -> 70, 34 -> 71, 35 -> 72, 35 -> 73, 36 -> 74, 36 -> 75, 
   37 -> 76, 37 -> 77, 38 -> 78, 38 -> 79, 39 -> 80, 39 -> 81, 
   40 -> 82, 40 -> 83, 41 -> 84, 41 -> 85, 42 -> 86, 42 -> 87, 
   43 -> 88, 43 -> 89, 44 -> 90, 44 -> 91, 45 -> 92, 45 -> 93};

g = Graph[links]

image

Let's try to plot it with igraph's Kamada-Kawai layout:

<<IGraphM`
IGLayoutKamadaKawai[g]

image

It looks quite awful. Let's increase the number of iterations:

IGLayoutKamadaKawai[g, MaxIterations -> 100000]

image

No change. Note that the epsilon parameter is set to zero, so this many iterations are really carried out.

Let's compare with Mathematica's Kamada-Kawai-like layout:

Graph[links, GraphLayout -> "SpringEmbedding"]

image

More iterations:

Graph[links, GraphLayout -> {"SpringEmbedding", "MaxIteration" -> 10000}]

image

Still not the best but better.

Question: Is there something wrong with igraph's Kamada-Kawai? Why does it seems to be stuck? Is this a problem with the method or with the implementation?

I do realize that KK is just not the best for this graph, but some of the nodes appear to be stuck in their initial circular arrangement, which raises the suspicion of a bug.


R code for a basic KK layout:

library(igraph)

g<-make_graph(1+c(0, 1, 0, 2, 0, 3, 1, 4, 1, 5, 2, 6, 2, 7, 3, 8, 3, 9, 4, 10, 4, 11, 5, 12, 5, 13, 6, 14, 6, 15, 7, 16, 7, 17, 8, 18, 8, 19, 9, 20, 9, 21, 10, 22, 10, 23, 11, 24, 11, 25, 12, 26, 12, 27, 13, 28, 13, 29, 14, 30, 14, 31, 15, 32, 15, 33, 16, 34, 16, 35, 17, 36, 17, 37, 18, 38, 18, 39, 19, 40, 19, 41, 20, 42, 20, 43, 21, 44, 21, 45, 22, 46, 22, 47, 23, 48, 23, 49, 24, 50, 24, 51, 25, 52, 25, 53, 26, 54, 26, 55, 27, 56, 27, 57, 28, 58, 28, 59, 29, 60, 29, 61, 30, 62, 30, 63, 31, 64, 31, 65, 32, 66, 32, 67, 33, 68, 33, 69, 34, 70, 34, 71, 35, 72, 35, 73, 36, 74, 36, 75, 37, 76, 37, 77, 38, 78, 38, 79, 39, 80, 39, 81, 40, 82, 40, 83, 41, 84, 41, 85, 42, 86, 42, 87, 43, 88, 43, 89, 44, 90, 44, 91, 45, 92, 45, 93));

plot(g, layout=layout_with_kk)

image


Final note: The best way for such a graph is circular Reingold-Tilford:

IGLayoutReingoldTilfordCircular[Graph[links], DirectedEdges -> True]

image

@ntamas
Member
ntamas commented Sep 13, 2016

It could be something with the ordering of the nodes and the unfortunate fact that the igraph implementation of the Kamada-Kawai layout uses a circle as the initial configuration (unless parameters like minx, miny, maxx or maxy are given). You can even see the remainder of the circle in the middle of each layout that igraph produced. I guess that for this particular graph and this particular initial configuration, it takes way too may iterations for igraph to "disentangle" the edge crossings of the initial circular layout, and a random starting point works better. Maybe we start with a circle to stay close to the original publication (is that true, @gaborcsardi ?).

@gaborcsardi
Member

It indeed starts from a circle, but you can supply your own start positions as well.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment