{"action":"created","issue":{"url":"https://api.github.com/repos/igraph/igraph/issues/963","repository_url":"https://api.github.com/repos/igraph/igraph","labels_url":"https://api.github.com/repos/igraph/igraph/issues/963/labels{/name}","comments_url":"https://api.github.com/repos/igraph/igraph/issues/963/comments","events_url":"https://api.github.com/repos/igraph/igraph/issues/963/events","html_url":"https://github.com/igraph/igraph/issues/963","id":176339913,"number":963,"title":"Why does Kamada-Kawai fail on a Bethe lattice?","user":{"login":"szhorvat","id":1212871,"avatar_url":"https://avatars.githubusercontent.com/u/1212871?v=3","gravatar_id":"","url":"https://api.github.com/users/szhorvat","html_url":"https://github.com/szhorvat","followers_url":"https://api.github.com/users/szhorvat/followers","following_url":"https://api.github.com/users/szhorvat/following{/other_user}","gists_url":"https://api.github.com/users/szhorvat/gists{/gist_id}","starred_url":"https://api.github.com/users/szhorvat/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/szhorvat/subscriptions","organizations_url":"https://api.github.com/users/szhorvat/orgs","repos_url":"https://api.github.com/users/szhorvat/repos","events_url":"https://api.github.com/users/szhorvat/events{/privacy}","received_events_url":"https://api.github.com/users/szhorvat/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2016-09-12T10:12:40Z","updated_at":"2016-09-13T15:00:59Z","closed_at":null,"body":"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.\r\n\r\nLet's make a partial Bethe lattice.  In Mathematica,\r\n\r\n```\r\nlinks = {0 -> 1, 0 -> 2, 0 -> 3, 1 -> 4, 1 -> 5, 2 -> 6, 2 -> 7, \r\n   3 -> 8, 3 -> 9, 4 -> 10, 4 -> 11, 5 -> 12, 5 -> 13, 6 -> 14, \r\n   6 -> 15, 7 -> 16, 7 -> 17, 8 -> 18, 8 -> 19, 9 -> 20, 9 -> 21, \r\n   10 -> 22, 10 -> 23, 11 -> 24, 11 -> 25, 12 -> 26, 12 -> 27, \r\n   13 -> 28, 13 -> 29, 14 -> 30, 14 -> 31, 15 -> 32, 15 -> 33, \r\n   16 -> 34, 16 -> 35, 17 -> 36, 17 -> 37, 18 -> 38, 18 -> 39, \r\n   19 -> 40, 19 -> 41, 20 -> 42, 20 -> 43, 21 -> 44, 21 -> 45, \r\n   22 -> 46, 22 -> 47, 23 -> 48, 23 -> 49, 24 -> 50, 24 -> 51, \r\n   25 -> 52, 25 -> 53, 26 -> 54, 26 -> 55, 27 -> 56, 27 -> 57, \r\n   28 -> 58, 28 -> 59, 29 -> 60, 29 -> 61, 30 -> 62, 30 -> 63, \r\n   31 -> 64, 31 -> 65, 32 -> 66, 32 -> 67, 33 -> 68, 33 -> 69, \r\n   34 -> 70, 34 -> 71, 35 -> 72, 35 -> 73, 36 -> 74, 36 -> 75, \r\n   37 -> 76, 37 -> 77, 38 -> 78, 38 -> 79, 39 -> 80, 39 -> 81, \r\n   40 -> 82, 40 -> 83, 41 -> 84, 41 -> 85, 42 -> 86, 42 -> 87, \r\n   43 -> 88, 43 -> 89, 44 -> 90, 44 -> 91, 45 -> 92, 45 -> 93};\r\n\r\ng = Graph[links]\r\n```\r\n\r\n![image](https://cloud.githubusercontent.com/assets/1212871/18432224/2a944348-78e1-11e6-99d4-ec895d519bfc.png)\r\n\r\nLet's try to plot it with igraph's Kamada-Kawai layout:\r\n\r\n    <<IGraphM`\r\n    IGLayoutKamadaKawai[g]\r\n\r\n![image](https://cloud.githubusercontent.com/assets/1212871/18432256/47cc4884-78e1-11e6-96db-c37007617745.png)\r\n\r\nIt looks quite awful.  Let's increase the number of iterations:\r\n\r\n    IGLayoutKamadaKawai[g, MaxIterations -> 100000]\r\n\r\n![image](https://cloud.githubusercontent.com/assets/1212871/18432275/60f2939a-78e1-11e6-8d77-e8190227a395.png)\r\n\r\nNo change.  Note that the `epsilon` parameter is set to zero, so this many iterations are really carried out.\r\n\r\nLet's compare with Mathematica's Kamada-Kawai-like layout:\r\n\r\n    Graph[links, GraphLayout -> \"SpringEmbedding\"]\r\n\r\n![image](https://cloud.githubusercontent.com/assets/1212871/18432343/c0e301d6-78e1-11e6-9236-b44c9f64f954.png)\r\n\r\n\r\nMore iterations:\r\n\r\n    Graph[links, GraphLayout -> {\"SpringEmbedding\", \"MaxIteration\" -> 10000}]\r\n\r\n![image](https://cloud.githubusercontent.com/assets/1212871/18432336/b8b91a54-78e1-11e6-8cd9-c6a3a03fe6f6.png)\r\n\r\n\r\nStill not the best but better.\r\n\r\n**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*?\r\n\r\nI 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\n\r\n----\r\n\r\nR code for a basic KK layout:\r\n\r\n```\r\nlibrary(igraph)\r\n\r\ng<-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));\r\n\r\nplot(g, layout=layout_with_kk)\r\n```\r\n\r\n![image](https://cloud.githubusercontent.com/assets/1212871/18432398/064e05b8-78e2-11e6-822e-cf1d49474cd2.png)\r\n\r\n----\r\n\r\nFinal note: The best way for such a graph is circular Reingold-Tilford:\r\n\r\n    IGLayoutReingoldTilfordCircular[Graph[links], DirectedEdges -> True]\r\n\r\n![image](https://cloud.githubusercontent.com/assets/1212871/18432581/081335fc-78e3-11e6-9856-1d646fae2cc8.png)\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/igraph/igraph/issues/comments/246711089","html_url":"https://github.com/igraph/igraph/issues/963#issuecomment-246711089","issue_url":"https://api.github.com/repos/igraph/igraph/issues/963","id":246711089,"user":{"login":"ntamas","id":195637,"avatar_url":"https://avatars.githubusercontent.com/u/195637?v=3","gravatar_id":"","url":"https://api.github.com/users/ntamas","html_url":"https://github.com/ntamas","followers_url":"https://api.github.com/users/ntamas/followers","following_url":"https://api.github.com/users/ntamas/following{/other_user}","gists_url":"https://api.github.com/users/ntamas/gists{/gist_id}","starred_url":"https://api.github.com/users/ntamas/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ntamas/subscriptions","organizations_url":"https://api.github.com/users/ntamas/orgs","repos_url":"https://api.github.com/users/ntamas/repos","events_url":"https://api.github.com/users/ntamas/events{/privacy}","received_events_url":"https://api.github.com/users/ntamas/received_events","type":"User","site_admin":false},"created_at":"2016-09-13T15:00:59Z","updated_at":"2016-09-13T15:00:59Z","body":"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 ?)."}}
{"actor":{"display_login":"ntamas"}}