Cytoscape Wiki|
← Revision 1 as of 2007-02-15 09:22:35
Size: 3783
Comment:
|
← Revision 2 as of 2007-02-15 09:28:53 →
Size: 3703
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 4: | Line 4: |
| Line 6: | Line 5: |
| Line 10: | Line 8: |
| Line 16: | Line 13: |
| Line 18: | Line 14: |
|
15/2/07 Not yet completely written but open for public comment. |
15/2/07 Not yet completely written but open for public comment. |
| Line 22: | Line 17: |
| Line 28: | Line 22: |
| Line 30: | Line 23: |
| Line 34: | Line 26: |
|
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), |
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) |
| Line 39: | Line 34: |
|
The multilevel approach (item 1 above) enables fast network layouts for large graphs. The given node classes (item 2) helps to emphasize functionally important aspects in the network topology, similarly as was done in [http://www.pasteur.fr/recherche/unites/Biolsys/GOlorize.htm GOlorize plug-in]. In the absence of such information, the data-driven graph clustering (item 3) aims at revealing possible [http://bioinformatics.oxfordjournals.org/cgi/content/abstract/23/2/207 modular organization] of the network , which can facilitate the layout process. The resulting node classes/clusters provide multi-resolution visualization in terms group nodes (or metanodes), similarly as was done the the [http://genepro.ccb.sickkids.ca/index.html GenePro plug-in]. |
The multilevel approach (item 1 above) enables fast network layouts for large graphs. The given node classes (item 2) helps to emphasize functionally important aspects in the network topology, similarly as was done in [http://www.pasteur.fr/recherche/unites/Biolsys/GOlorize.htm 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 in terms group nodes (or metanodes), similarly as was done the the [http://genepro.ccb.sickkids.ca/index.html GenePro plug-in]. |
| Line 45: | Line 37: |
| Line 47: | Line 38: |
| Line 49: | Line 39: |
| Line 51: | Line 40: |
| Line 53: | Line 41: |
| Line 55: | Line 42: |
| Line 57: | Line 43: |
| Line 59: | Line 44: |
|
* ["/Implementation Plan"] |
* [:MultilevelLayout/Implementation Plan:/Implementation Plan] |
| Line 63: | Line 46: |
RFC Name : Multilevel graph layout algorithm |
Editor(s): TeroAittokallio |
About this document
This is an official Request for Comment (RFC) for implementing a multilevel graph layout as a Cytoscape plug-in.
For details on RFCs in general, check out the [http://www.answers.com/main/ntquery?method=4&dsid=2222&dekey=Request+for+Comments&gwp=8&curtab=2222_1&linktext=Request%20for%20Comments 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 methods 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 (Journal of Graph Algorithms and Applications, 2003, 7(3): 253-285) seems interesting, because it combines force-directed placement with multilevel optimization framework. By hierarchically coarsening the network through iterative node matching and merging, the multilevel approach can not only accelerate the drawing process but it also appears to give globally more pleasant 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 fast network layouts for large graphs. The given node classes (item 2) helps to emphasize functionally important aspects in the network topology, similarly as was done in [http://www.pasteur.fr/recherche/unites/Biolsys/GOlorize.htm 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 in terms group nodes (or metanodes), similarly as was done the the [http://genepro.ccb.sickkids.ca/index.html GenePro plug-in].
General Notes
Requirements
Deferred Items
Open Issues
Backward Compatibility
Expected growth and plan for growth
References
Implementation Plan
[:MultilevelLayout/Implementation Plan:/Implementation Plan]