Design Functionality ~ dynamics gsoc timeline

My name is Daniel Bernardes and during this Google Summer of Code I am working on the new Timeline interface.

Dynamic graphs have been the subject of increasing interest, given their potential as a theoretical model and their promising applications. Following this trend, Gephi has incorporated tools to study dynamic networks. From a visualization perspective, a critical tool is the Timeline component, which allows users to select pertinent time intervals and display and explore the corresponding graph. The challenge concerning the timeline was twofold: redesign the component to improve user experience and add extra features and introduce an animation scheme with the possibility to export the resulting video.

Together with my mentors Cezary Bartosiak and Sébastien Heymann, we have proposed a new design for the timeline component featuring a sparkline chart in the background of the interval selection drawer (which is semi transparent): this feature will help the user to focus on particular moments of the evolution of the dynamic graph, like bursts of connections or changes in graph density or other simple graph metrics. Current metrics are the evolution of the number of nodes, the number of edges and the graph density. The sparkline chart was preferred to other chart solutions because it does not add too much visual pollution to the component and adds to the qualitative analysis. The interaction with the drawer remains globally the same of the old timeline, to guarantee a smooth transition for the user.

To implement this feature we have used the chart library JFreeChart (a library already incorporated to Gephi), customizing their XYPlot into a Sparkline chart by modifying their visual attributes. To display the Sparkine, one needs to measure the properties of the graph in several time instants of the global time frame where the dynamic graph exists. This represented a major challenge, since the original architecture did not allow the timeline component to access (and measure) the graph in particular instants of time; the solution was to introduce a slight modification to the DynamicGraph API to provide an object which gave us snapshots of the graph at given instants. Other challenges we dealt with included the automatic selection/switching of real number/time units in the timeline (depending on the nature of the graph in question) and sampling granularity of the timeline.

Another breakthrough of this project was the introduction of the timeline animation. Once the user has selected a time frame with the drawer it can make it slide as the corresponding graph is being displayed on the screen. Besides the technical aspects of interaction between the timeline and the animation controller, there were also an effort to calibrate the animation (ie, in terms of speed and frames) so it would be comfortable and meaningful for the user.

As far as the UI is concerned, the component has gained a new “Reset” button next to the play button which activates the timeline drawer and displays the chart. It also serves to reset the drawer selection to the full interval when the timeline is active. The play button gained its original function, that is, to control the animation of the timeline — instead of activating the selection.

Finally, the animation export to a video format revealed to be more tricky than expected and couldn’t be finished as planned. There were several setbacks to this feature, beginning with the selection of a convenient library to write de movie container: it turns out that the de facto options available are not fully Java-based and need an encoder working in the background. The best alternative I found was Xuggler, which is based on ffmpeg. Also, obtaining screen captures of the graph to were a little bit tricky so I have exported SVG images from the graph corresponding to each frame, converted them to jpeg and than encoded them though Xuggler to a video format. As one might expect, this solution is not very efficient in terms of time, so Mathieu Bastien and my mentors suggested me to wait for the new features from the new Visualization API that would make this process simpler.

In addition to current bugfixes and minor improvements concerning the timeline and the animation, the movie export remains the the next big step to close this project. If you have questions or suggestion, please do not hesitate! The new timeline will be available in the next release of Gephi.

DB

4 comments »

Design Functionality ~ gsoc infovis preview

My name is Yudi Xue and during this Google Summer of Code am glad to work on the Core evolution of Gephi.

Current API in the Preview module provides too many granular methods and classes. Developers are clueless about how they may extend the component. In this project, we do not seek to expand what the Preview module already have to offer. Rather, we focus on making the Preview module easy to learn, easy to use and easy to extend to the Gephi developers. The new API will allow developers to focus on particular parts of the module. They may specify a new visual algorithms just by implementing a new type of Renderer, such as edge bundling and convex hull. They may also extend the RenderTarget to allow display or export visualization to different platform.

The user story

We took the infovis reference model into consideration when we started designing the new infrastructure. The infrastructure aims to provide support to a visualization-preview workflow:

raw data -> the data builder -> renderers -> render targets.

In particular, the raw data is the graph associated with the current gephi workspace. The data builder (DataBuilder) will interpret information associated with the nodes and edges and generate Item objects for Preview use. The Item objects are immutable objects that are either node item (NodeItem), edge item (EdgeItem) or item group (GroupItem) specified from the graph workspace or data lab. We append “Item” to refer that they are data rather than display objects. After the data has been imported, the preview controller (PreviewController) will associate each type of entity items with Renderer objects. Renderer objects are functional procedures that describe how an item should be drew. While we give information to an Renderer object what it is going to draw, we also tell it what RenderTarget it will use. By default, we provide ProcessingRenderTarget, PDFRenderTarget and SVGRenderTarget. All RenderTarget objects contribute to the RenderTarget API, which provide granular drawing functions that can be used by developers to form advanced visual algorithm. In addition to the workflow, we will provide a flexible properties structure to the Preview module so it may be used to provide listener to user interface commands. The property will allow dynamic dependency where grouped properties can listen for a single parent property.

The code below demonstrates how a Renderer to a particular Item type could be updated at runtime.

Code sample:

PreviewController prc = (PreviewController)Lookup.getDefault().lookupItem(
                                                       PreviewController.DEFAULT_IMPL).getInstance();
prc.loadGraph();
// Load graph from workspace
prc.updateRenderer(NodeItem.class, new Renderer() {
    // How I want to draw a node, edge, or item types.
    // Specify your procedural visualization algorithm here
    @Override
    public void render(Item item, RenderTarget rt) {
        NodeItem ni = (NodeItem) item;
        rt.drawImage(..);
        rt.drawline(..);
    }
    // The RenderTarget will pick up the properties and draw the rest..
});

The big picture

Speaking of API flexibility, the Preview API goes from constrained to flexible in the direction from DataBuilder to RenderTarget. Here is the big picture:

Current progress

• done:
  • a working copy based on the new architecture
  • added ProcessingRengerTarget
  • added GroupRenderer (Convex hull)
  • added ImageRenderer
  • basic unit testing
  • basic functional testing against updating Renderer in Preview API at runtime
• in progress:
  • Property support
  • Selfloop, curved edge drawing
  • PDF and SVG RenderTarget implementation

Here is a screenshot of the new system with convex-hull enabled:

Code practice

The code base is under active development at https://code.launchpad.net/~yudi-xue/gephi/gephi-preview. The code base includes the PreviewAPI module and the PreviewImpl module.

Lookup API

We make use of Netbeans Lookup API to instantiate singleton and use Lookup. Template to ensure the correct implementation been called.

For example, to call the default PreviewController constructor, we call:

/*
* DEFAULT_IMPL is defined in the interface.
* It refers to default implementation class
* "org.gephi.preview.PreviewControllerImpl"
*/
(PreviewController)Lookup.getDefault().lookupItem(PreviewController.DEFAULT_IMPL).getInstance();

Accordingly, you may choose to use the API with your implementation by creating a Template that points your implementation class.

Functional Tests

During the development, we are creating functional tests against our own API for the purpose of both flexibility and stability. the “PreviewAPIFunctionalTest”

Conclusions

Our goal is to bring modularity and extensibility to the Preview module. We aim to deliver the freedom in defining your own visual algorithms (Renderer) and user interaction (Property) and make use of API without thinking about the detailed mechanism. I would like to give my thanks to Dr. Christian Tominski, Mathieu Bastian and Sébastien Heymann for their support and feedback, which is critical during the development for the new architecture.

2 comments »

Design Functionality ~ gsoc opengl visualization

My name is Vojtech Bardiovsky and I am working on the new Visualization API. This is done together with the new visualization engine based on shaders.

API design

The aim of the project was to design a clean and usable API for the new engine. It exposes only as much as necessary, but enough to make customization of visualization possible. The following four API classes are all services and can be retrieved through ‘Lookup’.

Visualization controller

This is the most important class in the API and can be used to retrieve the ‘Camera’, ‘Canvas’ used for visualization display, and very importantly the instance of active ‘VizModel’ and ‘VizConfig’ classes that both contain many settings that help controlling the visualization. It will also allow making direct changes to visualization like setting the frame rate or centering camera according to different parameters. The ‘Camera’ class can be used to get data about its position or to make actions such as translation or zooming.

Event and Selection managers

The Event manager can be used to register listeners to user events exactly as in the old engine. This is very important for the tools. The selection manager provides methods to retrieve all currently selected nodes or edges, to select nodes or edges and to control the selection state of the UI (dragging, rectangle selection, etc).

Motion manager

Apart from listening to all user induced events and their most basic handling (selection, translation, zoom), this class provides information about current mouse position in both screen and world coordinates.

New features

There are many changes the new engine will bring and although it is not finished yet, there already are some new user-side features.

Complex selection

In the old visualization engine, only rectangular and direct (one node) selection were possible. New API will allow to implement any reasonable shape. At the moment it supports rectangles, ellipses and polygons.

Thanks to the selection shape variability and changes in the mouse event system, it is possible to make incremental/decremental selections using Shift and Ctrl keys. Opposed to only one node at the time, the whole selection can be dragged and moved now.

Background image

It is now possible to change and configure the background image. Settings are similar to the CSS properties such as ‘background position’ or ‘background repeat’.

Node shapes

It is possible to have different shapes for every node in graph. Basic shapes include ‘circle’, ‘triangle’, ’square’, etc., but also up to 8 custom images that can be imported by user. Nodes can have their shapes defined in the import file or set them directly through the context menu.

Better 3D

Work has been done on a better way to control the scene in the 3D. Graphs are not naturally suited for 3D, for example adding new nodes or moving them will never be perfectly intuitive. But for displaying the graph, some enhancements can be done.

Current status

The engine is still under development, but the API is slowly closing to its final state. Next step for the API will be to include as many configuration possibilities as the engine will allow. The underlying data structures will be optimized for performance.
As the project consists of two parts, API and engine, Antonio Patriarca, the mentor for this GSoC project and implementor of the engine will write an article about rendering details in the near future.

(The rendering pipeline for edges is not fully finished, so the images shown are not the actual new look of gephi.)

8 comments »

Design Events Exhibition ~ knowledge map

The Saint Étienne International Design Biennial, holding from 20 November to 5 December, is a unique event in the domain of design, due to the exhibitions shown as well as the diversity of its attendees. The Biennial democratizes design and makes it accessible to all kinds of audiences, proving that this creative discipline can take many forms, and is often driven by human aspects, including its uses by humans.

The theme of the 2010 biennial is around teleportation. It intends to explore paths of discoveries that will tend in their extreme expression to lead to a possible teleportation as the dematerialization of movement which appears to be an incredibly revealing notion of our era.

Sebastien Heymann will exhibit maps of designers’ conceptual world, placed at the center of the “Prédiction” exhibition. Made in collaboration with Benjamin Loyauté, curator of the event, these inscriptions are a proposal to reveal the state of knowledge sharing in Design today.

Useful information on how to come here.

You may contact Sebastien by email to appoint a meeting during the first weekend.

Ten free tickets will be given to the first comments of this post!

EDIT: photos are available on the Facebook page of Gephi.

4 comments »

Community Design ~ 0.7 architecture developer infovis review

Guest blog post from Dr. Tominski who accepted to review Gephi 0.7alpha4 for us.

Christian Tominski received his diploma (MCS) from the University of Rostock in 2002. In 2006 he received doctoral degree (Dr.-Ing.) from the same university. Currently, Christian is working as a lecturer and researcher at the Institute for Computer Science at the University of Rostock. Christian has authored and co-authored several articles in the field of information visualization. His main interests concern visualization of multivariate data in time and space, visualization of graph structures, and visualization on mobile devices. In his research, a special focus is set on interactivity, including novel interaction methods and implications for software engineering.

Recently, I stumbled upon the Gephi Project – an open source graph visualization system. As I’ve done some research in the area of interactive graph visualization, I was eager to see how Gephi works and if it brings some new concepts or if it’s yet another graph visualization system. I’ll share my thoughts on Gephi from three perspectives. The first one is the user perspective. I’ll take the role of a user who is interested in getting a visual depiction of some graphs. Secondly, I’ll take the role of a developer and shed some light on the aspect of software engineering. And finally, I’ll be a scientist and try to foresee if and in which regard Gephi might have some impact on visualization research.

The User’s Perspective

Gephi has been designed with the users and their needs in mind. The system welcomes its users with a familiar look and feel. It is quite easy to load graph data into the system. Many of the known file formats for graphs are supported, as for instance, DOT, GML, GraphML, or Tulip’s file format TLP. A nice thing about the data import is that an import report provides essential information about the import process (e.g., number of nodes and edges, edge-directedness, potential problems, etc.). Once imported, the graph is shown as nodes and links in a main view, and several complementary views provide additional information.

The main view is the core for visual graph exploration. It allows users to zoom in, to select nodes, to adjust node size and color, to find shortest paths, and to access attributes of nodes and edges. In addition to letting users set sizes and colors manually, the system can also set these automatically based on attributes associated with nodes and edges. What is called “Partition” in Gephi is used to assign unique colors to nodes and edges based on qualitative data attributes (e.g., class affiliation). Quantitative data values can be mapped to size and color of nodes, edges, and labels using the “Ranking” tool. All these tools are customizable. It is worth mentioning, that Gephi provides some nice user controls to parameterize the color coding.

Gephi also supports graph editing, i.e., insertion and deletion of nodes and edges as well as manipulation of attribute values. What is missing in terms of editing the data is the possibility to add (and delete) attributes, for instance to generate some derived data values using simple formula.

A key aspect in graph exploration is the layout of node and edges. As it is usually unclear what will be the best layout for a given graph, Gephi offers various layout algorithms to choose from. While a layout is being computed, the main view constantly updates itself to provide feedback of the progress made. A big plus is that users can interrupt the layout algorithm once they deem the result to be ok or if they find that it might be more suitable to use the current result as the initial setup for another algorithm. This way users can easily tune the layout to fit the graph and the particular needs. Users may put the finishing touches to the layout by moving nodes manually in the main view.

Once a suitable visual representation has been created, the final step is to export nice pictures of the graph. To this end, Gephi follows the philosophy of providing a dedicated export interface with many options to create high quality printouts.
People that have been working with larger graphs might know that some computations on graphs (including layout computation) are quite complex and take some time. While other systems are blocked during computation and in the best case provide a progress bar, Gephi is different. Long running calculations are concurrent to the main application. From my point of view, this is one of the strongest points of Gephi, the system does not block during costly computations. The benefit for the users is that they can always interact, for instance to initiate some other computations or to cancel running ones when they recognize that a re-parameterization would yield better results.

Concurrency is Gephi’s solution to offering computations of statistics about the graph. Currently, Gephi supports a variety of classic graph statistics including degree distribution, number of connected components, and others. Based on data attributes and computed statistics, the graph can be filtered to reduce nodes and edges to those that fulfill the filter criteria. In a dynamic filtering UI, several filters can be combined using drag’n’drop and thresholds can be manipulated easily, for instance via sliders. Besides using filtering for data reduction, Gephi also provides basic support for graph clustering. However, the currently implemented MCL algorithm is still experimental. But there is the possibility to manually group nodes to build a hierarchical structure on top of the visualized graph. Yet, this is quite cumbersome for larger graphs. Additional tools are needed to support the user in creating a navigable hierarchy on top of a graph. Configurable clustering pipelines that combine several strategies for clustering (e.g., based on attributes or based on bi-connected components) in addition to a clustering wizard user interface would be helpful.

In summary, I see a much potential in Gephi, the overall shape of the system impressed me – me as a user. I personally felt it easy to work with Gephi and explore some of my own data sets and some provided at Gephi’s website. Given the fact that the version I’ve worked with is 0.7 alpha, there is also much space for improvements. In the first place I would like to mention the navigation of the graph. The main view provides just basic zoom and pan navigation, which is even imprecise in some situations. Navigation tools like those provided in Google Earth and navigation based on paths through a graph would be really helpful. Moreover, I was missing the concept of linking between views. Selecting an element (node or edge) in one view should highlight that element in all other views. Right now this is not really an issue as the number of views seen in parallel is quite low. But once additional views are needed, for instance to focus on data attributes in a Parallel Coordinates Plot or to visualize the cluster hierarchy in a dedicated view, or when one and the same graph is shown in parallel in two or more main views for comparing different analytic results, linking will be crucial for user experience. But these things are not too complex and should be easy to integrate in future versions of Gephi. Another aspect regards highlighting in the main view: instead of marking the selected node, all non-selected nodes faded out to focus on the selected node. This implies rather big visual changes because all but one nodes change their appearance when a single node gets selected and deselected.

Pros:	Cons:
Easy graph import and export Many options for visual encoding Various layout algorithms to choose from Support for dynamic filtering Computation of graph statistics Basic support for graph clustering System does not block during long running computations	Graph navigation can be improved No linking among views Few visual glitches Still an alpha version with bugs here and there

The Developer’s Perspective

Now let me switch to the developer’s view. Gephi is open source software so that everybody can participate in improving the system or can adapt the system to personal or business needs. Gephi seems to be very well designed on the back-end. The project is based on the Netbeans platform and the Java language. It is subdivided into a number of modules that define several APIs and SPIs and that provide implementations of these interfaces. Thanks to the modular structure, Gephi can be extended quite easily. The best way to do so is to implement plugins. Plugins can be used, for instance, to add further layout or clustering algorithms, statistical computations, filter components, or export methods. The modular structure also allows for using only specific parts of the Gephi project in one’s own projects. The Gephi Toolkit is a good example. It is not an end-user desktop application, but a class library that provides all the functionality of Gephi to those who want to reuse Gephi’s functionality and data structures in different ways.

As I’ve mentioned in the user perspective, the way how Gephi deals with long running computations is a big plus. Given the fact that aspects of multi-threading are inherent in the system from the very beginning and are manifested at the systems core, I sincerely hope – no, I’m quite sure that Gephi will not run into all the problems that are likely to occur when multithreading is integrated into an existing single-threaded system, as I have experienced it myself. Also I conjecture that others will find it much easier to implement concurrent non-blocking extensions of the system simply by following the way how existing code handles things in Gephi.

As Gephi is split up into many different modules, it took me a while to get accustomed to the system and to learn which functionality can be found in which module. But I have to add that I had no prior experience in Netbeans platform development and the module concept that is used there. I also found that the code documentation could be improved in several parts of Gephi’s sources. On the other hand, the Gephi website provides informative wiki pages with various examples and tutorials.

My view from the developer’s perspective can be summarized as the following pros and cons:

Pros:	Cons:
Open source Modular structure Well defined interfaces Extensible via plugins Inherently multithreaded	In-code documentation can be improved

The Scientist’s Perspective

As a scientist I’m not so much interested in developing fully-fledge end-user software, but in developing solutions to scientific questions and in publishing the results. A difficulty in interactive visualization is that usually one needs a broad basis of fundamental functionality to be able to develop such solutions. Previous attempts of establishing a common infrastructure for interactive data exploration made notable progress, but eventually did not fully succeed or are no longer actively maintained. This is due to the fact that a single researcher usually simply does not have the time to do decent research and at the same time to maintain a larger software project.

I personally feel that Gephi can become such a fundamental infrastructure. Maintained by an active community, the system allows researchers to focus on solutions in form of plugins, while they can utilize the functionality that the system provides. Visualization researchers will be happy if they can simply plug in new visualization techniques as additional views, test new layout algorithms, and experiment with new clustering methods. Moreover, new solutions can be easily disseminated to real users in the community. This might prove beneficial when it comes to acquiring early user feedback or when more formal user evaluation is needed prior to publishing new techniques and concepts.

A big issue in visualization research is visual analytics, that is, the combination of analytical, interactive, and visual means to facilitate making sense of large volumes of data. In terms of analytic means, a goal is to break analytic black boxes and make analysis algorithms interactively steerable. With the architecture of Gephi, where parameterizable algorithms run concurrently and provide feedback in form of intermediate results, I believe this goal can be reach in the future. A thing that I’m curious about is if it is also possible to come up with concepts that allow for plugging in new interaction techniques. As interaction is usually quite tightly bound to a view, I wonder if interaction could be implemented as independent plugins as well, and if novel interaction concepts will be supported in the future (e.g., touch interaction)? Furthermore, aspects of interactive collaboration of multiple users working to solve a common analysis problem could be of interest. A question related to the visual side is whether it is possible to use Gephi with different displays and display environments such as tabletop displays, display walls, smart phones, or multi-display environments?

A facet of graph visualization that I did not mention in the user’s perspective as I felt it more suited to be mentioned here is dealing with dynamically changing graphs. Visualization of time-varying graphs is a hot research topic and Gephi is about to face this challenge. There is preliminary support for exploring time-dependent graphs via a time slider. But there is more to this that just browsing in time. Concepts have to be integrated to support easy comparison of multiple snapshots of a graph and to highlight significant changes in the development of a graphs history.

Let me try to put my thoughts into a pros and cons list:

Pros:	Cons:
Potential infrastructure for visualization research Researchers can focus on solutions in form of plugins Potential to use community for user feedback and evaluation Partial results for current research questions (graph clustering, steerable algorithms, dynamic graphs) Nice playground for experimentation and testing new ideas	Unclear if new and alternative technologies will be supported

Summary

Since I’ve put hands on Gephi I’m infected. Maybe I’m dazzled by the beautiful demo video or the nice pictures that have been generated using Gephi, but in my opinion Gephi has the potential to become a big player in interactive visual graph exploration and analysis. From all perspectives that I’ve taken I see many positive things – and plenty of room for improvements or additional features. I do hope that the people behind Gephi will continue their work to the benefit of all users, developers, and researchers.

Related Stuff

There are many other systems and frameworks out there that do a great job in interactive graph visualization or in supporting it as a toolkit. I would like to give credit to these systems, because they can be the source of many ideas and much inspiration:

• Tulip – A great visualization system
• Cytoscape – Sophisticated network visualization for bio-medicine
• GUESS – Interactive graph exploration at its best
• Pajek – Graph analysis at its best
• prefuse – The well known information visualization framework
• JUNG – A library for graph structures and algorithms
• JGraphT – Another library for graphs

2 comments »