Difference between revisions of "FORCE DIRECTED NETWORK (SPRING ALGORITHM) GRAPH VIEWER"

From Protein Prediction 2 Winter Semester 2014
(→‎First Week(21.11.2014 - 27.11.2014))
(→‎15.01.2015 Submission Deadline)
 
(62 intermediate revisions by the same user not shown)
Line 31: Line 31:
   
 
==Data==
  
==Data==
−
The input data should be in json/csv format
 +
The input data should be in tsv format
  +
[[File:data_snapshot.png | 500px | center | data]]
−  
−
E.g:
  
−
var json = [{
 
−
"adjacencies": [
 
−
"graphnode21",
 
−
{
 
−
"nodeTo": "graphnode1",
 
−
"nodeFrom": "graphnode0",
 
−
"data": {
 
−
"$color": "#557EAA"
 
−
}
 
−
}, {
 
−
"nodeTo": "graphnode13",
 
−
"nodeFrom": "graphnode0",
 
−
"data": {
 
−
"$color": "#909291"
 
−
}
 
−
}, {
 
−
"nodeTo": "graphnode14",
 
−
"nodeFrom": "graphnode0",
 
−
"data": {
 
−
"$color": "#557EAA"
 
−
}
 
−
}]
  
−  
−  
−  
−
[[File:data.png | 500px | center | data]]
  
   
 
=RoadMap=
  
=RoadMap=
Line 70: Line 43:
   
 
==First Week(21.11.2014 - 27.11.2014)==
  
==First Week(21.11.2014 - 27.11.2014)==
  +
*Learned about the concept of force directed graph and the algorithms.
−
Got to know about web workers.
  
  +
*Deciding on the libraries to be used for the implementation
−
Understood Max implementation of web workers.
  
−
Understood how spring layout works.
 +
*Understood how spring layout works.
  +
*Tried working with tools like Gephi in which we can visualize the network data.
  +
*Got acquainted with our mentors.
   
 
==Second Week(28.11.2014 - 4.12.2014)==
  
==Second Week(28.11.2014 - 4.12.2014)==
  +
*Explored about cytoscape and went through the list of issues sent by Max.
  +
*Understood the goals that Max wanted us to implement.
  +
*Defined the Milestone Plan.
  +
*Decide on the Approach to parallelize code.
  +
*Started working on web workers.
  +
*Got Clarified the doubts related to web workers from Max's implementation.
  +
*Started exploring about benchmark.js and parallel.js
   
−
==Third Week(28.11.2014 - 4.12.2014)==
 +
==Third Week(5.12.2014 - 12.12.2014)==
  +
*Did parallelisation using circle layout with the web workers implementation
   
  +
Github repository:
−
Goal
  
  +
https://github.com/Ahsanzia/FDG
−
Understand Max Goals
  
−
To define this Milestone Plan
  
−
Decide on the Approach to parallelize code
  
−
Reading List (BenchmarkJS, ParallelJS, Google Dev Tools)
  
−
Discuss with Max Debug Tools of Cytoscape
  
   
  +
*Started working on the web worker implementation for spread layout
−
Max Comments & Hints:
  
−
Separate the Graph into separate components (Subgraph components, Subsets of the Graph (Force-directed Layout))
  
−
Normalization, Fitting Step in the End to resolve conflicts if subset has connection / edges between
  
−
Approach Arbor uses (good example to look at). Own Worker API
  
−
Lot’s of different ways to parallelize things (depends on the layout)
  
−
Spread Layout using ParallelJS (convert using Cytoscape Worker API)
  
−
One thread is offload the computation
  
−
Always measure performance on the same machine! (console, timer, profiling)
  
−
It would be great to have a automated benchmarking
  
   
  +
==Fourth Week(13.12.2014 - 18.12.2014)==
−
Rmaco: https://github.com/cytoscape/cytoscape.js/pull/700
 
  +
Report, work on Spread Layout Algorithm. Some functions parallelized if possible.
  +
*Worked on visualization of 3000 nodes and corresponding edges using different features:
  +
**Different layouts
  +
**Zooming enabled and disabled
  +
**Calculating the time for rendering of the layout.
  +
**Getting all the nodes that are connected to a particular node on selection of a particular node
  +
Github repository:https://github.com/Vasantha4940/DataVisualization
   
  +
The following visualizations use spread layout.
−
Unexpected difficulties:
  
  +
[[File:Initial_page.png | 500px | left|thumb|'''Fig1.1:Intial Layout of the Page''']]
−
synchronization between workers (avoid communication between them in the beginning)
  
  +
[[File:data_200.png | 500px | center | thumb|'''Fig1.2:TIme taken to visualize 200 nodes: 349ms''']]
  +
[[File:data_400.png | 500px | left | thumb|'''Fig1.3:TIme taken to visualize 400 nodes: 572ms''']]
  +
[[File:data_600.png | 500px | center | thumb|'''Fig1.4:TIme taken to visualize 600 nodes: 998ms''']]
  +
[[File:data_800.png | 500px | left | thumb|'''Fig1.5:TIme taken to visualize 800 nodes: 1263ms''']]
  +
[[File:data_1000.png | 500px | center | thumb|'''Fig1.6:TIme taken to visualize 1000 nodes: 1975ms''']]
  +
[[File:data_1200.png | 500px | left | thumb|'''Fig1.7:TIme taken to visualize 1200 nodes: 2425ms''']]
  +
[[File:data_1400.png | 500px | center | thumb|'''Fig1.8:TIme taken to visualize 1400 nodes: 3127ms''']]
  +
[[File:data_1600.png | 500px | left | thumb|'''Fig1.9:TIme taken to visualize 1600 nodes: 3846ms''']]
  +
[[File:data_1800.png | 500px | center | thumb|'''Fig1.10:TIme taken to visualize 1800 nodes: 4840ms''']]
  +
[[File:data_2000.png | 500px | left | thumb|'''Fig1.11:TIme taken to visualize 2000 nodes: 5988ms''']]
  +
[[File:data_2200.png | 500px | center | thumb|'''Fig1.12:TIme taken to visualize 2200 nodes: 7069 ms''']]
  +
[[File:data_2400.png | 500px | left | thumb|'''Fig1.13:TIme taken to visualize 2400 nodes: 8547ms''']]
  +
[[File:data_2600.png | 500px | center | thumb|'''Fig1.14:TIme taken to visualize 2600 nodes: 9350ms''']]
  +
[[File:data_2800.png | 500px | left | thumb|'''Fig1.15:TIme taken to visualize 2800 nodes: 10992ms''']]
  +
[[File:data_3000.png | 500px | center | thumb|'''Fig1.16:TIme taken to visualize 3000 nodes: 11705ms''']]
  +
<br>
  +
<br>
  +
<br>
  +
<br>
  +
<br>
  +
<br>
  +
<br>
  +
The following graph shows the relationship between the nodes and time taken to visualize it.
  +
[[File:Plot_without.png | 500px | center | thumb|'''Fig1.17:Graph showing relationship between nodes and the corresponding time taken to visualize it without using the web workers''']]
   
−
==Fourth Week(5.12.2014 - 12.12.2014)==
 +
==Fifth Week(19.12.2014 - 29.12 .2014)==
  +
*Went through the documentation of web workers
−
Basic Program which is parallelised (Nested in Cytoscape)
  
  +
*Implement simple web worker for testing purpose
−
Please mind the Coding Style of Cytoscape
 
  +
*Implement one worker for a circle lay out in cytoscape.js
−
Send Graph Data to the Worker Program and back
  
−
Benchmark the simple program
  
−
i.e. BenchmarkJS
  
−  
−
==Fifth Week(13.12.2014 - 18.12.2014)==
  
−
Report, work on Spread Layout Algorithm. Some functions parallelized if possible.
  
   
−
==Sixth Week(19.12.2014 - 29.12 .2014)==
 +
==Sixth Week(30.12.2014 - 05.01 .2015)==
  +
*Implemented the web workers for the Spread layout.
−
Run the first Layout Algorithm (pick one algorithm) with multiple cores (parallelized)
  
  +
*Working on the benchmarking of the Spread layout
−
Test and BenchmarkJS
 
−
 
   
  +
In order to optimize the performance in terms of the time taken to visualize a large network of more than 2000 nodes,we can use web workers.Web workers are mainly based on the concept like parallel processing in web.They work by splitting the tasks across different workers without affecting the actual UI.
−
==Seventh Week(30.12.2014 - 05.01 .2015)==
  
  +
[[File:graph_comparison.png| 500px | center | thumb|'''Fig1.17:Graph showing relationship between nodes and the corresponding time taken to visualize it without using the web workers''']]
   
 
==08.01.2015 Final Presentation==
  
==08.01.2015 Final Presentation==
   
−
==15.01.2015 Submission Deadline==
 +
==25.01.2015 Submission Deadline==
   
 
= Source Code =
  
= Source Code =
   
  +
*[http://vasantha4940.github.io/DataVisualization/public_html/index.html '''Network Data Visualisation with different Layouts''']
−
*[http://www.github.com GITHUB]
  
  +
*[https://github.com/anu3090/Dataset_creation '''Dataset creation''']
   
 
= People =
  
= People =

Latest revision as of 17:50, 25 January 2015

The objective of this project is to visualize a network (large networks of >2000 nodes) in a way that the distance of a node from the rest of the network is determined by the number of nodes it is connected to => the more neighbors a node has the larger is its distance from the network. The component must allow zooming in/out, selection by the number of neighbors, coloring by various thresholds and other graph-related features.

Introduction

Force Directed Network is obtained by using the Force-directed graph drawing algorithms(SPRING ALGORITHM). This algorithm is mainly based on the forces assigned among the set of nodes and edges of a graph.The forces can be either atractive which is used to attract pairs of endpoints of the graph's edges towards each other or repulsive which is used to seperate all pairs of nodes.In equilibrium states for this system of forces,the edges tend to have uniform length(using spring forces) and the nodes which are not connected by any edge tend to be drawn further apart(due to electrical repulsion).

Mockups

mockup 1
mockup 2
mockup 1
mockup 4


Functionality

  • Zoom in and Zoom out of the graph.
  • Distance of a node from the rest of the network is determined by the number of nodes it is connected to.
  • Selection by the number of neighbors
  • Coloring by various thresholds
  • Dividing the whole network into module based on the modularity.
  • Applying filters.
  • Defining the layout of your choice.
  • Exporting the visualisation as an image.

Features

  • Import from Text format
  • Export to image
  • Visualization Using FORCE DIRECTED NETWORK

Application Design

  • Fancy Libraries
    • d3.js
    • jQuery
    • JavaScript InfoVis Toolkit

https://www.youtube.com/watch?v=3qo6EqwWmS0

Data

The input data should be in tsv format

data

RoadMap

mockup 1

Roadmap for Implementation

Cytoscape Worker API :

https://github.com/cytoscape/cytoscape.js/blob/unstable/src/worker.js

First Week(21.11.2014 - 27.11.2014)

  • Learned about the concept of force directed graph and the algorithms.
  • Deciding on the libraries to be used for the implementation
  • Understood how spring layout works.
  • Tried working with tools like Gephi in which we can visualize the network data.
  • Got acquainted with our mentors.

Second Week(28.11.2014 - 4.12.2014)

  • Explored about cytoscape and went through the list of issues sent by Max.
  • Understood the goals that Max wanted us to implement.
  • Defined the Milestone Plan.
  • Decide on the Approach to parallelize code.
  • Started working on web workers.
  • Got Clarified the doubts related to web workers from Max's implementation.
  • Started exploring about benchmark.js and parallel.js

Third Week(5.12.2014 - 12.12.2014)

  • Did parallelisation using circle layout with the web workers implementation

Github repository: https://github.com/Ahsanzia/FDG

  • Started working on the web worker implementation for spread layout

Fourth Week(13.12.2014 - 18.12.2014)

Report, work on Spread Layout Algorithm. Some functions parallelized if possible.

  • Worked on visualization of 3000 nodes and corresponding edges using different features:
    • Different layouts
    • Zooming enabled and disabled
    • Calculating the time for rendering of the layout.
    • Getting all the nodes that are connected to a particular node on selection of a particular node

Github repository:https://github.com/Vasantha4940/DataVisualization

The following visualizations use spread layout.

Fig1.1:Intial Layout of the Page
Fig1.2:TIme taken to visualize 200 nodes: 349ms
Fig1.3:TIme taken to visualize 400 nodes: 572ms
Fig1.4:TIme taken to visualize 600 nodes: 998ms
Fig1.5:TIme taken to visualize 800 nodes: 1263ms
Fig1.6:TIme taken to visualize 1000 nodes: 1975ms
Fig1.7:TIme taken to visualize 1200 nodes: 2425ms
Fig1.8:TIme taken to visualize 1400 nodes: 3127ms
Fig1.9:TIme taken to visualize 1600 nodes: 3846ms
Fig1.10:TIme taken to visualize 1800 nodes: 4840ms
Fig1.11:TIme taken to visualize 2000 nodes: 5988ms
Fig1.12:TIme taken to visualize 2200 nodes: 7069 ms
Fig1.13:TIme taken to visualize 2400 nodes: 8547ms
Fig1.14:TIme taken to visualize 2600 nodes: 9350ms
Fig1.15:TIme taken to visualize 2800 nodes: 10992ms
Fig1.16:TIme taken to visualize 3000 nodes: 11705ms








The following graph shows the relationship between the nodes and time taken to visualize it.

Fig1.17:Graph showing relationship between nodes and the corresponding time taken to visualize it without using the web workers

Fifth Week(19.12.2014 - 29.12 .2014)

  • Went through the documentation of web workers
  • Implement simple web worker for testing purpose
  • Implement one worker for a circle lay out in cytoscape.js

Sixth Week(30.12.2014 - 05.01 .2015)

  • Implemented the web workers for the Spread layout.
  • Working on the benchmarking of the Spread layout

In order to optimize the performance in terms of the time taken to visualize a large network of more than 2000 nodes,we can use web workers.Web workers are mainly based on the concept like parallel processing in web.They work by splitting the tasks across different workers without affecting the actual UI.

Fig1.17:Graph showing relationship between nodes and the corresponding time taken to visualize it without using the web workers

08.01.2015 Final Presentation

25.01.2015 Submission Deadline

Source Code

People

  • PP2_CS_2014 mentors, Björn Grüning (Galaxy) gruening. (at) .informatik.uni-freiburg.de
  • Students: Kommanapalli Vasantha Kumari,Anuradha Ganapati,Ahsan ZiaUllah

Additional Links

Retrieved from "https://i12r-studfilesrv.informatik.tu-muenchen.de/pp22014/index.php?title=FORCE_DIRECTED_NETWORK_(SPRING_ALGORITHM)_GRAPH_VIEWER&oldid=1712"