CIShell Manual : DrL (VxOrd)

Description

DrL is a force-directed graph layout toolbox focused on real-world large-scale graphs (see References). This toolbox includes:

• Standard force-directed layout of graphs using algorithm based on the popular VxOrd routine (used in the VxInsight program).
• Parallel version of force-directed layout algorithm.
• Recursive multilevel version for obtaining better layouts of very large graphs.
• Ability to add new vertices to a previously drawn graph.

DrL has been used on graphs up to 2 million vertices. It is written in C++ and can be used with Linux, Windows, and Mac.

Links

• Source Code: http://www.cs.sandia.gov/~smartin/DrL.tar.gz
• Binaries: link
• Home Page: http://www.cs.sandia.gov/~smartin/software.html

Pros & Cons

DrL is one of the few force-directed layout algorithms that can scale to over 1 million nodes, making it ideal for large graphs. However, small graphs (hundreds or less) do not always end up looking so good. This algorithm expects similarity networks, so some networks may need to derive another network with weighted edges declaring the similarity between nodes.

The version of DrL included in NWB only does the standard force-directed layout (no recursive or parallel version).

Applications

Force-directed layout of large networks.

Implementation Details

DrL expects the edges to be weighted, directed edges where the weight (greater than zero) denotes how similar the two nodes are (higher is more similar). The NWB version has several parameters. The edge cutting parameter expresses how much automatic edge cutting should be done. 0 means as little as possible, 1 as much as possible. Around .8 is a good value to use. The weight attribute parameter lets you choose which edge attribute in the network corresponds to the similarity weight. The X and Y parameters let you choose the attribute names to be used in the returned network which corresponds to the X and Y coordinates computed by the layout algorithm for the nodes.

Usage Hints

• For article/citation networks, feed the network into either cocitation or bibliographic coupling for computing similarity. Use this network for laying out DrL.
• GUESS or Pre-Defined Layout can be used to see the layout created by DrL.

To see the VxOrd/DrL layout in GUESS, you must run the following command in the GUESS interpreter (click the 'Interpreter' tab near the bottom of the GUESS interface):

for n in g.nodes:
    n.x = n.xpos * 100
    n.y = n.ypos * 100

(Whitespace is significant.)

This assumes you used the default 'xpos' and 'ypos' labels suggested by the DrL algorithm.

This code is translated into English as the following: For every node in the network,

    make the GUESS x coordinate equal to the DrL-generated X coordinate times 100
    make the GUESS y coordinate equal to the DrL-generated Y coordinate times 100

We multiply by 100 because DrL coordinates are on a smaller scale than GUESS coordinates, so we need to enlarge the DrL coordinates to see the network structure (otherwise it will appear that the nodes are nearly on top of each other).

• Now you can switch between the GUESS layout options to retrieve different visualization effects. Recommended: Switch between Bin Pack and GEM a few times.

Acknowledgements

DrL was created at Sandia National Labs

References

• S. Martin, W. M. Brown, K. Boyack, "DrL: Distributed Recursive (Graph) Layout," in prepartion for Journal of Graph Algorithms and Applications.
• Davidson, G.S., Wylie, B.N. & Boyack, K.W. (2001). Cluster stability and the use of noise in interpretation of clustering. Accepted by IEEE Information Visualization `01.

See Also