RFC Name : Consolicated Graph Analysis Plugin |
Editor(s): Keiichiro Ono |
Status: Open for Comments |
<<TableOfContents: execution failed [Argument "maxdepth" must be an integer value, not "[2]"] (see also the log)>>
Proposal
This document is for consolidated graph analysis plugin development plan. The purpose of this project is collecting general graph analysis algorithms in one place and provide users a common interface to access the functions.
Biological Questions / Use Cases
Some network visualization/analysis tools have built-in graph analysis features such as:
- Shortest path
- Cluster analysis
- Graph traverse
- Graph Statistics:
- Mean shortest path
- Degree distribution
- Average number of interaction partners
- Clustering coefficient
- Topological coefficient
These functions are useful for most of users (both biology/non-biology) to see the general characteristics of the graph. Some of these are implemented as Cytoscape plugins, but there is no one simple plugin to provide all of these. The purpose of this project is creating a core plugin to provide easy access to these functionality.
General Notes
We will use the incremental approach for this project.
- Collect analysis plugins already available for Cytoscape.
- Implement a common UI for them.
- Design a expandable backend system which accepts additional analysis algorithms without changing the core.
- Implement individual algorithms. These can be added later.
Requirements
The following functions will be implemented. Some of them will be ported from other libraries (such as JUNG).
Statistics
- Degree distribution
- Mean shortest path
- Diameter of a graph
- Average number of degree
- Clustering coefficient
- Topological coefficient
- Centrality
Ranking
- Page Rank algorithm
Paths/Flows
- Shortest path
- Critical path
- All paths between two nodes
- Max flow between two nodes
Graph Generators (Optional)
- Random graph (Erdos-Renyi model)
- Scale-Free graph (Barabasi-Albert model)
- Watts-Strogatz small-world model
Note: We do not have to implement all of them at once. We will implement small group of functions first.
Deferred Items
Open Issues
Functions needs to be implementd:
- (Please add functions we need to implement...)
Backward Compatibility
Expected growth and plan for growth
References
Software with Graph Analysis Functionalities
Implementation Plan
Comments
How to Comment
Edit the page and add your comments under the provided header. 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. 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.