Gephi Cycles Detection

Gephi Cycles Detection

This Gephi plugin traverses the active graph searching for closed walks, cycles and cliques. The search is made using the popular depth-first order search algorithm, using a standard single stack implementation made popular by Robert Sedgewick. Although this is very common in graph searching, there wasn’t a plugin for Gephi performing just this simple task and no more in a efficient way. Some features:

  • The plugin can be used on both directed and undirected graphs. In the first case, close walks (cycles) are hunted, while cliques in the latter;
  • Reports include a distribution of the founded cycles by size;
  • No use of external libraries: just 18k for the whole package;
  • Asynchronous and interruptible task;
  • Written in a pure OOP flavour, using Gephi APIs.

tFileOutputGML_icon32You can download the most recent release of the plugin here or browse the source code on GitHub.

How to install the plugin

To install this plugin in Gephi, click on Tools on the menu bar, then Plugins. The plugin manager window will open.

Now, just click on Downloaded tab, then Add Plugin. Locate the NPM file on your file system and finally click Install.

You’ll need to restart Gephi to finalize the installation.

As the component is still under heavy testing, it has not been deployed to Gephi Marketplace, yet. Thus the automatic install/update feature is not available. The manual procedure described above is the only way to install it at the moment

How to use the plugin

Usage of this plugin is absolutely trivial.  Just open the graph you want to traverse in the active window and search Cycles Detection on the bottom of Network Overview elements of the Statistics panel. Just click Run to perform the search.

The algorithm is fully asynchronous and yon break it at any time, if needed. Clicking Cancel before the end of the traversal phase will result in partial, but still valid, results (ie. only part of the cycles will eventually be found). Please not that the progress bar is not guarantee to be linear and it tends to slow down with huge and/or highly connected graphs.

Results and Reports

This plugin doesn’t add new attributes or metrics to nodes/edges. It just files a report on the screen. The report will contain:

  • Parameters area that shows which kind of search was made on the graph (closed walk for directed graphs, cliques for undirected/mixed) graphs
  • Number of cycles founded – no need to explain that further
  • Cycles Size Distribution that plots (Y axis) the number of cycles found of a given size (X axis).

To-Do List

This is not the kind of artifact I usually maintain and support for my whole life, because it solves its small, finite task and that’s it. But if I realize that someone  needs/likes/loves it and politely requests it, I would be happy to add these features some day in the future:

  • Refine the traversing process using something better than boring java Collections to handle internal stacks of data, for memory saving and speed improving;
  • Going multi-thread to dramatically improve speed;
  • Define a partitioning attribute for node if they are laying in one or more closed walks;
  • Trying to make the progress bar a bit more linear.

Support

Please feel free to use the comment form below or the contact form to share considerations, report bugs and complainants, ask for support, give your opinion to improve this component and submit patches and fixes. I’ll try to help you as best I can do but please don’t forget that this component is not guaranteed to work under every circumstances and on every system. It really needs some massive test before going to a production stage!

Changelog

  • Version 1.0 – 02/09/2014
    • First public release