Over the past few weeks I've asked (and my supervisors have asked) myself two questions - how will the cooling schedule work for dynamic graphs (which I covered as a post previously), and how does the number of iterations required to find a good layout using MGF, compare to the OT. The latter is especially important as, in theory, the MGF will take fewer iterations, and proving that would be good for both Technical Report and Thesis.
So, I set up and run both algorithms, using the "default" parameters for a selection of graphs. For both algorithms, given the same parameters, the number of iterations for a graph are the same.
| MGF | OT | ||||
| levels | iter g0 | iter all | iter g0 | iter all | |
| 55grid | 12 | 61 | 526 | 61 | 526 |
| data | 15 | 61 | 619 | 61 | 619 |
| 4elt | 17 | 69 | 769 | 69 | 769 |
| add32 | 175 | 64 | 7962 | ||
| finan512 | 36 | 77 | 1775 | 77 | 1775 |
| sierpinski10 | 20 | 77 | 1030 | 77 | 1030 |
The table above gives 6 graphs (dime20 would be included but testing that is far from nice), the number of levels generated by the multilevel algorithm, and the number of iterations for generating layout for the original graph (g0), and the number of iterations overall.
The number of iterations comes down to the cooling schedule and/or calculation of forces. In my implementation, and as described by others such as Veldhuizen, and Fruchterman and Reingold, vertices find a good position but remain moving backwards and forwards (in a zigzagging pattern) as the forces continue to push and pull the vertices into better positions (even though it may be in the best position). The cooling schedule fixes this by limiting the movement at later stages, and forces the algorithm to eventually stop. My understanding of this was that the layout should converge naturally, before the cooling schedule forces a stop.
In practice, the cooling schedule only stops when movement is limited to such extent that the layout is deemed converged - thus, forcing both MGF and OT algorithms to be iterated the same number of times. So if the cooling schedule is just a means of calculating an ideal number of iterations, why is it reported that the number of iterations can change for the same graph? The real answer is I am unsure. At a guess, I would say the calculation of K is the difference, and the number of controlled parameters in my application.
My first thought about this is: what have I implemented incorrectly. Hu's work would support this; implementing the adaptive cooling schedule, the behavior did not match that described by Hu, instead, followed the behavior I described above. So, my plan? I intend to replace my calculation of K with that used by Walshaw and check the iterations again. If the same, it looks like there's a problem in need of fixing.
Ah well, practice makes perfect. Let's hope my next rant isn't regarding another piece of work from 2 years ago. Until next time, bye.
