GSoC: Force Directed Edge Bundling

My name is Taras Klaskovsky and during this Summer Of Code I have implemented the Force Directed Edge Bundling algorithm.

Force Directed Edge Bundling (FDEB) is an edge layout algorithm. Gephi already has node layouts, which are placing the nodes (usually using force-directed algorithms). FDEB helps to further improve graph visualization by changing shapes and colors of the edges to merge them in bundles, analogous to the way electrical wires and network cables are merged into bundles along their joint paths and fanned out again at the end. This reduces visual clutter, inevitable in large graphs, allowing to find high-level edge patterns and get an overview of the graph just by looking at it. As example, US flights graph below, with nodes as airports and edges as flights.

The algorithm

Edges are modeled as flexible springs that can attract each other while node positions remain fixed. A force-directed technique is used to calculate the bundling and it is relatively slow. On small graphs it works pretty fast due to optimizations, but consumes large amount of memory to store precomputed similar pairs of edges; for average and large graphs a special slow low-memory mode implemented. After every iteration preview is being refreshed, so it’s possible to observe formation of bundles in real-time.

Full algorithm description can be found on this research paper.

Renderer Modes

FDEB has 3 renderer modes:

• Simple renderer: Draws all edges with the same color and transparency (color, transparency and thickness are set in the preview settings in the bottom-left panel), bundles are emphasized by combined transparency.
• Gradient renderer: Draws all edges with color from gradient slider. Edges that are similar to higher number of other edges get higher color.
• Gradient slow renderer: Uses more precise method to determine intensity of edge (needs precalculate points checkbox and to be re-runned) to set personal color for every segment.

FDEB can be customized with lots of options and they all have descriptions, some of the most influential on result are:

• Use inverse-qudratic model: Makes more localized bundling
• Compatibility threshold: Ignore pairs of edges that are not similar enough, which makes FDEB faster (ignored in low-memory mode) and bundling become more localized.

To make FDEB faster it’s also possible to decrease number of cycles/subdivision points increase rate.

The Edge Layout API

An edge layout API has been created to simplify the integration of other edge layouts into Gephi. This API is very similar to the existing node layout API, with the following additions. Since edge layouts do not only change shapes of edges, but are also responsible for their visualization, a modifyAlgo() is called each time when the Preview is refreshed, to control the modification of parameters. The edge layout data, which is accessible for each edge, provides polyline points and it’s colors for all renderer modes.

How to get the FDEB algorithm

It will be available in the next release of Gephi. The current source code is available on Github.

New Tutorial: Layouts in Gephi

A new tutorial is available about Layouts in Gephi. It will guide you to the basic and advanced layout settings in Gephi. You will learn how to use various layouts in Gephi according to the feature you want to emphasis in the topology and the size of the network, how to avoid node overlapping and how to do some geometric transformations.

This tutorial explains when and how to use each layout, including:

• the new ForceAtlas 2
• OpenOrd
• Fruchterman-Reingold

Gephi Tutorial Layouts

View more presentations from Gephi NGO

Tutorial: Download it in PDF.

ForceAtlas2, the new version of our home-brew Layout

The new version of the build-in layout ForceAtlas is now released. It is scaled for small to medium-size graphs, and is adapted to qualitative interpretation of graphs. The equations are the same as ForceAtlas 1, but there are more options and innovative optimizations that make it a very fast layout algorithm.

It is good enough to deal with very small graphs (10 nodes)  and fast enough to spatialize 10,000 nodes graphs in few minutes, with the same quality. If you have time, it can deal with even bigger graphs.

Update Gephi (Help > Check for Updates) to get this new layout.

Force Atlas 2:

• Is a continuous algorithm, that allows you to manipulate the graph while it is rendering (a classic force-vector, like Fruchterman Rheingold, and unlike OpenOrd)
• Has a linear-linear model (attraction and repulsion proportional to distance between nodes). The shape of the graph is between Früchterman & Rheingold’s layout and Noack’s LinLog.
• Features a unique adaptive convergence speed that allows most graphs to converge more efficiently
• Proposes summarized settings, focused on what impact the shape of the graph (scaling, gravity…). Default speed should be the good one.
• Now features a Barnes Hut optimization (performance drops less with big graphs)

 

 

Force Atlas 2 features these settings:

• Scaling: How much repulsion you want. More makes a more sparse graph.
• Gravity: Attracts nodes to the center. Prevents islands from drifting away.
• Dissuade Hubs: Distributes attraction along outbound edges. Hubs attract less and thus are pushed to the borders.
• LinLog mode: Switch ForceAtlas’ model from lin-lin to lin-log (tribute to Andreas Noack). Makes clusters more tight.
• Prevent Overlap: Use only when spatialized. Should not be used with “Approximate Repulsion”
• Tolerance (speed): How much swinging you allow. Above 1 discouraged. Lower gives less speed and more precision.
• Approximate Repulsion: Barnes Hut optimization: n² complexity to n.ln(n) ; allows larger graphs.
• Approximation: Theta of the Barnes Hut optimization.
• Edge Weight Influence: How much influence you give to the edges weight. 0 is “no influence” and 1 is “normal”.

 

 

Force Atlas 2 was created by Mathieu Jacomy at the Sciences Po Médialab (Paris), founding member of the Gephi Consortium.

OpenOrd: New layout plugin, the fastest algorithm so far

A new force-directed layout algorithm plugin named OpenOrd has just been released. It is one of the few force-directed layout algorithms that can scale to over 1 million nodes, making it ideal for large graphs.

Features:

• Very fast, scales to millions nodes
• Can be run in parallel, run it on multicore processors
• Aims to highlight clusters

Install it directly from Gephi (Tools > Plugins > Available Plugins) or download it from the Plugin Center. Longer description and source code can be found directly on the plug-in page.

Below is a small demo of how fast this algorithm is layouting a 10K nodes network, and only using one processor.

OpenOrd Layout Demo in Gephi from gephi on Vimeo.

The algorithm original design and implementation can be found at this address. Kudos to the authors!