Name
Title | ||
|---|---|---|
BFL: a node and edge betweenness based fast layout algorithm for large scale networks |
Abstract | ||
|---|---|---|
Background: Network visualization would serve as a useful first step for analysis. However, current graph layout algorithms for biological pathways are insensitive to biologically important information, e.g. subcellular localization, biological node and graph attributes, or/and not available for large scale networks, e.g. more than 10000 elements. Results: To overcome these problems, we propose the use of a biologically important graph metric, betweenness, a measure of network flow. This metric is highly correlated with many biological phenomenasuchaslethalityandclusters.Wedeviseanewfastparallelalgorithmcalculatingbetweenness tominimizethepreprocessingcost.Usingthis metric,we alsoinventa nodeandedgebetweennessbased fast layout algorithm (BFL). BFL places the high-betweenness nodes to optimal positions and allows the low-betweenness nodes to reach suboptimal positions. Furthermore, BFL reduces the runtime by combining a sequential insertion algorim with betweenness. For a graph with n nodes, this approach reduces the expected runtime of the algorithm to O(n 2 ) when considering edge crossings, and to O(n log n) when considering only density and edge lengths. Conclusion: Our BFL algorithm is compared against fast graph layout algorithms and approaches requiring intensive optimizations. For gene networks, we show that our algorithm is faster than all layout algorithms tested while providing readability on par with intensive optimization algorithms. We achieve a 1.4 second runtime for a graph with 4000 nodes and 12000 edges on a standard desktop computer. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1186/1471-2105-10-19 | BMC Bioinformatics |
Keywords | Field | DocType |
Short Path, Layout Algorithm, Node Betweenness, Betweenness Score, Generalize Zeta Function | Graph drawing,Flow network,Parallel algorithm,Computer science,Algorithm,Theoretical computer science,Preprocessor,Betweenness centrality,Bioinformatics,Time complexity,Gene regulatory network,Computer graphics | Journal |
Volume | Issue | ISSN |
10 | 1 | 1471-2105 |
Citations | PageRank | References |
18 | 0.47 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tatsunori B. Hashimoto | 1 | 90 | 11.02 |
| Masao Nagasaki | 2 | 368 | 26.22 |
| Kaname Kojima | 3 | 152 | 11.12 |
| Satoru Miyano | 4 | 2406 | 250.71 |