Consolidated_graph_analysis_plugin

<<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.

1. Collect analysis plugins already available for Cytoscape.
2. Implement a common UI for them.
3. Design a expandable backend system which accepts additional analysis algorithms without changing the core.
4. 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

• Pajek

• JUNG

• igraph

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.