NOESIS Network Visualization Techniques

There are many algorithms for creating pleasant visual networks representations. These network visualization techniques allow gaining insight into the network structure by placing nodes according to the topology of the network. NOESIS implements several network layout algorithms under the noesis.algorithms.visualization package. This page is describes these techniques and provides examples of how to use them.

Applying a network layout algorithm

NOESIS provides several network visualization techniques under a unique interface defined by NetworkLayout. These implementations provide two layout methods. On the one hand, a layout method that only takes the network and assumes that node coordinates are encoded in two node attributes, named x and y. For example, in order to apply a hierarchical layout using this method, we would write the following code:

AttributeNetwork network = new AttributeNetwork();
...
HierarchicalLayout layout = new HierarchicalLayout();
layout.layout(network);

On the other hand, a layout method that takes the network and two node attributes, where the computed coordinates will be stored. The previous example, using this alternative, would be written as follows:

AttributeNetwork network = new AttributeNetwork();
...
Attribute<Double> x = new Attribute<Double>("x");
Attribute<Double> y = new Attribute<Double>("y");
network.addNodeAttribute(x);
network.addNodeAttribute(y);
...
HierarchicalLayout layout = new HierarchicalLayout();
layout.layout(network, x, y);

If your network does not already have the node attributes for the x and y coordinates, they must be initialized before some layout algorithms are invoked. The easiest way to do this is by means of RandomLayout:

AttributeNetwork network = new AttributeNetwork();
...
Attribute<Double> x = new Attribute<Double>("x");
Attribute<Double> y = new Attribute<Double>("y");
network.addNodeAttribute(x);
network.addNodeAttribute(y);

RandomLayout random = new RandomLayout();
random.layout(network);
...
HierarchicalLayout layout = new HierarchicalLayout();
layout.layout(network);

Creating a custom network layout algorithm

New network layouts can be implemented by extending the NetworkLayout class. Extending this class only requires implementing the layout method, which takes the network for which to compute the layout and the pair of node attributes where the obtained coordinates must be stored. A template for a custom layout would look as follows:

public class MyLayout extends NetworkLayout 
{
    @Override
    public void layout(AttributeNetwork network, Attribute<Double> x, Attribute<Double> y) 
    {
        // Implement your layout here. NOTE: Node coordinates must be stored in x and y
    }
}


Creating a custom iterative network layout algorithm

Many layout algorithms are iterative and follow a similar structure. NOESIS simplifies their implementation by providing the IterativeNetworkLayout class. The interface provided by IterativeNetworkLayout requires implementing each of the stages separately. The init method is used for initializing the resources used by the implemented network layout algorithm. The actions performed in each iteration are implemented in the iterate method. These actions are repeated until a stop condition is met. This conditions is implemented using the stop method, which returns true is the layout has finished or false otherwise. Finally, the end method is used for releasing the resources used by the technique. The following code snippet shows a template for a custom iterative layout algorithm:

public class MyIterativeLayout extends IterativeNetworkLayout 
{
    /* NOTE: The network and the coordinate attributes are available 
       in the protected members "network", "x", and "y", respectively. */

    @Override
    public void init() 
    {
        // Initialize the resources used by the layout here
    }

    @Override
    public void iterate() 
    {
        // Perform an algorithm iteration here
    }

    @Override
    public boolean stop() 
    {
        // Check the algorithm stopping criterion (i.e. if the algorithm has converged or finished)
        return <true or false>;
    }

    @Override
    public void end() 
    {
        // Free resources
    }
}

Provided network layout algorithms

Fruchterman-Reingold layout

The Fruchterman-Reingold technique is a force-directed layout algorithm, which models a physical system with attractive and repulsive forces between nodes. This physical system is iteratively updated until converge, when the system reaches an equilibrium state and nodes do not change their position between iterations. The following example shows how to compute a Fruchterman-Reingold layout for a given network with attributes:

AttributeNetwork network = ...
FruchtermanReingoldLayout layout = new FruchtermanReingoldLayout();
layout.layout(network);

References:

  • Fruchterman, T. M., & Reingold, E. M. (1991). Graph drawing by force‐directed placement. Software: Practice and experience, 21(11), 1129-1164. DOI: 10.1002/spe.4380211102.

Kamada-Kawai layout

The Kamada-Kawai layout is another force-directed graph layout technique. This approach minimizes the total energy of the simulated physical model by solving a system of partial differential equations using the Network-Raphson method and updating a node each time. An example of applying this layout technique is shown in the following code fragment:

AttributeNetwork network = ...
KamadaKawaiLayout layout = new KamadaKawaiLayout();
layout.layout(network);

References:

  • Kamada, T., & Kawai, S. (1989). An algorithm for drawing general undirected graphs. Information processing letters, 31(1), 7-15. DOI: 10.1016/0020-0190(89)90102-6.

Radial layout

A radial layout arranges nodes in different concentric rings starting from a root node. When the network has different components, a virtual root node is created and connected to each component real root. This layout supports different strategies for choosing the root node through the interface provided by SelectionStrategy. Currently, NOESIS provides two different strategies: the node with minimal average path length to other nodes, using MinAveragePathLengthSelectionStrategy, and the node with minimal eccentricity, using MinEccentricitySelectionStrategy. The following example shows how to compute a radial layout using the strategy based on minimal average path length:

AttributeNetwork network = ...
SelectionStrategy selectionStrategy = new MinAveragePathLengthSelectionStrategy();
RadialLayout layout = new RadialLayout(selectionStrategy);
layout.layout(network);

References:

  • Wills, G. J. (1999). NicheWorks—interactive visualization of very large graphs. Journal of computational and Graphical Statistics, 8(2), 190-212. DOI: 10.1080/10618600.1999.10474810.

Hierarchical layout

In the hierarchical layout, nodes are arranged in different stacked layers composing a hierarchy. The ordering of the nodes within each layer is chosen to minimize the number of crossing links between layers. This layout can be applied to a network as shown in the following example:

AttributeNetwork network = ...
HierarchicalLayout layout = new HierarchicalLayout();
layout.layout(network);

References:

  • Roberto Tamassia: Handbook on Graph Drawing and Visualization. Chapman and Hall/CRC 2013, ISBN 978-1-5848-8412-5.


NOESIS includes several regular network layouts, which are specially useful when dealing with regular networks:


Circular layout

In a circular layout, nodes are arraged in a circle or ring. This layout can be used as follows:

AttributeNetwork network = ...
CircularLayout layout = new CircularLayout();
layout.layout(network);

Star layout

The star layout is similar to the circular layout, but a node is placed in the center of the circle, creating a star. This layout can be applied as shown below:

AttributeNetwork network = ...
StarLayout layout = new StarLayout();
layout.layout(network);

Mesh layout

The mesh layout arranges nodes in a grid-like structure. An example using this layout is shown below:

AttributeNetwork network = new AttributeNetwork();
MeshLayout layout = new MeshLayout();
layout.layout(network);

Hypercube layout

The hypercube layout places the nodes as they were the corners of a hypercube embedded in a two-dimensional space. This layout can be used as follows:

AttributeNetwork network = new AttributeNetwork();
HypercubeLayout layout = new HypercubeLayout();
layout.layout(network);

Binary tree layout

The binary tree layout arranges nodes in different layers, similar to the hierarchical layout. However, in this case, the number of nodes in a layer is twice the number of nodes in the previous layer. The binary tree layout can be applied as shown below:

AttributeNetwork network = new AttributeNetwork();
BinaryTreeLayout layout = new BinaryTreeLayout();
layout.layout(network);

Toroidal layout

A toroidal layout places nodes in a grid-like structure, which would cover a torus. This layout is applied as follows:

AttributeNetwork network = new AttributeNetwork();
ToroidalLayout layout = new ToroidalLayout();
layout.layout(network);

Linear layout

The linear layout arranges nodes in a straight line. This layout can be applied as shown in the following code snippet.

AttributeNetwork network = new AttributeNetwork();
LinearLayout layout = new LinearLayout();
layout.layout(network);