printlogo
http://www.ethz.ch/index_EN
Welcome to Algorithms, Data Structures and Applications
 
print
  

Complex Networks

Our research in complex networks concentrates on analysis of stochastic processes on simple graphs and higher order distributions. Moreover we are interested in visualisation and parallel simulation of complex networks. Recently we finished a new algorithm which uses multi-level gamma-clustering to visualize complex biological networks. The software and experimental data could be found in the following file MultiLevelGammaClustering_suppl.zip

To illustrate the different ways of rendering a graph we prepared 5 demonstrations. For all we have used the same settings for the generation of the graph (ConfigModel with gamma = 1.75 and 600 nodes).

Classic Force Directed

Here we used a classical force directed algorithm that is based on a physical model. The edges are interpreted as springs which gives the attraction force. In addition, a so called anti-gravity is applied that provokes a repulsion of all nodes.

FDClassic
FDClassic.PNG

Force Directed using heuristics

In addition to the classical force directed method, here we implemented heuristics as explain in the Lukas Oertle's master thesis. These heuristics are intended to take care of the osciallation observed in the classical algorithm. On the one hand, an internal temperature is lowered slowly so that the nodes will for sure come to a final position. On the other hand, each step a node makes is interpolated with the last 4 steps. In this way opposing movement neutralize each other.

FDHeuristic
FDHeuristic.PNG

Circular Force Directed using heuristics

Here the positioning algorithm is equivalent to the previous one. In addition, a 'correction displacement' is calculated to force each node on a circle according to its degree.

CFDHeuristic
CFDHeuristic.PNG

Force Directed with Hierarchical Gamma Clustering using heuristics

Again, the positioning algorithm is left mainly untouched except for some constants. Before the actual rendering is started the graph was 'prepared' as explained in our paper 'Hierarchical Gamma Clustering'.

FDClustering
FDClustering.PNG

Circular Force Directed with Hierarchical Gamma Clustering using heuristics

This rendering is equivalent to the previous one, with the same addition as seen in the third example: With a 'correction displacement' the nodes are forced on circles according to their distance (=number of edges) from the root node (root node not shown here, would be placed in the center).

CFDClustering
CFDClustering.PNG
 

Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.

Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.
More information

© 2014 ETH Zurich | Imprint | Disclaimer | 12 April 2013
top