--------------------
More Recent Research
--------------------
- The article presents the barycentric heuristic for reordering nodes
in an arc diagram, for example.
In investigating the matter a bit more, I have found preliminary
theoretical and empirical evidence that the barycentric heuristic
works slightly better if, when computing the average position
of neighbors, we give a weighting to each node's current position
that is slightly greater than 1.0. So, if we define a variable
weight = 1.1
we could then modify two lines of the pseudocode in the article
to implement the weighting (lines 5 and 11 below, both starred).
I don't know if the matter of this weighting has been investigated before,
but I recommend readers use this weighting in their implementations.
It seems to allow the algorithm to converge faster, in some cases.
1 // compute average position of neighbors
2 for i1 = 0 to N-1
3 node1 = nodes[i1]
4 p1 = positionOfNode(i1)
5* sum = p1 * weight
6 for j = 0 to node1.neighbors.length-1
7 i2 = node1.neighbors[j]
8 node2 = nodes[i2]
9 p2 = positionOfNode(i2)
10 sum = sum + p2
11* orderedNodes[p1].average = sum / ( node1.neighbors.length + weight )
12
13 // sort the array according to the values of average
14 sort( orderedNodes, comparator )
- I have learned about a much more efficient way to implement force-directed layout: stress majorization.
The article "Graph drawing by stress majorization" by Gansner, Koren, and North
( http://scholar.google.ca/scholar?q=Gansner+Koren+North+%22Graph+drawing+by+stress+majorization%22 )
describes this. Much of the article presents somewhat complicated mathematics,
however most of these details can be ignored. The reader can skip over equations (3) through (11)
and focus on implementing equation (12), which is simple to implement.
Each iteration of the algorithm brings the layout closer to the optimal layout,
with none of the stability problems or oscillations associated with traditional force-directed layout.
Before performing stress majorization, you must generate
a matrix of desired distances d_{i,j} between nodes i and j, for all pairs of nodes,
to serve as input to the stress majorization.
This matrix can be computed efficiently and easily with the Floyd-Warshall algorithm
( https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm ).
-----------------------
Additional Related Work
-----------------------
- The article cites Alper et al. (2011) as an example of
visualizing subsets of nodes. More recent work
on this topic includes
Kasper Dinkla, Marc J. van Kreveld, Bettina Speckmann, and Michel A. Westenberg
Kelp Diagrams: Point Set Membership Visualization
Eurographics Conference on Visualization (EuroVis) 2012
DOI: 10.1111/j.1467-8659.2012.03080.x
http://scholar.google.ca/scholar?q=kelpfusion+meulemans+riche
@inproceedings{efrat2014,
author={Efrat, Alon and Hu, Yifan and Kobourov, Stephen G and Pupyrev, Sergey},
title={{MapSets}: Visualizing Embedded and Clustered Graphs},
booktitle={Symposium on Graph Drawing (GD)},
year={2014}
}
% http://vcg.github.io/upset/about/
@article{lex2014,
author = {Lex, Alexander and Gehlenborg, Nils and Strobelt, Hendrik and Vuillemot, Romain and Pfister, Hanspeter},
title = {{UpSet}: Visualization of Intersecting Sets},
journal = {{IEEE} Transactions on Visualization and Computer Graphics ({InfoVis} '14)},
year = {2014},
}
Corinna Vehlow, Fabian Beck, and Daniel Weiskopf
The State of the Art in Visualizing Group Structures in Graphs
Eurographics Conference on Visualization (EuroVis) (2015)
http://groups-in-graphs.corinna-vehlow.com/
Visualizing Sets and Set-typed Data: State-of-the-Art and Future Challenges
Bilal Alsallakh, Luana Micallef, Wolfgang Aigner, Helwig Hauser, Silvia Miksch, Peter Rodgers
EuroVis 2014
http://www.cvast.tuwien.ac.at/node/657
http://www.setviz.net/ , http://www.cvast.tuwien.ac.at/SetViz
http://www.cvast.tuwien.ac.at/~alsallakh/SetViz/literature/www/
Rodgers et al.
Visualizing Sets with Linear Diagrams
ACM TOCHI 22(6), 2015
http://dx.doi.org/10.1145/2810012