RFC Name : Multilevel graph layout algorithm |
Editor(s): TeroAittokallio |
<<TableOfContents: execution failed [Argument "maxdepth" must be an integer value, not "[2]"] (see also the log)>>
About this document
This is an official Request for Comment (RFC) for implementing a multilevel graph layout algorithm as a Cytoscape plug-in.
For details on RFCs in general, check out the Wikipedia Entry: Request for Comments (RFCs)
Status
15/2/07 Not yet completely written but open for public comment.
How to Comment
To view/add comments, click on any of 'Comment' links below. By adding your ideas to the Wiki directly, we can more easily organize everyone's ideas, and keep clear records. Be sure to include today's date and your name for each comment. Here is an example to get things started: /Comment.
Try to keep your comments as concrete and constructive as possible. For example, if you find a part of the RFC makes no sense, please say so, but don't stop there. Take the extra step and propose alternatives.
Proposal
The graph layout algorithms based on the basic spring-embedder or force-directed placement approaches may become unfeasible when drawing larger networks with more than 10.000 nodes. Therefore, new methods have recently been suggested in the graph drawing literature. In particular, the method by Chris Walshaw seems interesting, because it combines force-directed placement with multilevel optimization framework. By hierarchically coarsening the network through iterative node matching and merging steps, the multilevel approach can not only accelerate the drawing process but it also appears to give globally more appealing quality to the drawings.
Along these lines, we will develop a multilevel graph layout plug-in, that:
1. implements a variant of the original Walshaw (2003) algorithm within Cytoscape
2. can also reflect user-defined node classes (e.g. GO annotation or other attributes)
3. incorporates automatic graph partitioning (module finding) in the layout process.
Biological Questions / Use Cases
The multilevel approach (item 1 above) enables computationally fast and visually pleasant layouts for large networks. The given node classes (item 2) helps to emphasize functionally important aspects in the network topology, similarly as was done in the GOlorize plug-in. In the absence of such information, the data-driven graph clustering (item 3) aims at revealing possible modular organisation of the network, which can facilitate the layout process. The resulting node classes/clusters provide multi-resolution visualization of the network in terms group nodes (or metanodes), similarly as was done the the GenePro plug-in.
Open Issues
* What is the "optimal" clustering algorithm for the visualization purposes?
* Is it meaningful to use both the user-defined and data-driven node classes?
* How to perform systematic comparison against alternative layout results?