Google Summer of Code 2013

It’s a great news, Gephi has been accepted again for the Google Summer of Code for the 5th year! The program is the best way for students around the world to start contributing to an open-source project. Since 2009, each edition is a great success and dramatically boosted Gephi’s project development.

What is Gephi?

Networks are everywhere: email systems, financial transaction systems and gene-protein interaction networks are just a few examples. Gephi began as a university student project four years ago and has quickly become an open source software leader in the visualization and analysis of large networks. It is an important contribution to the ecosystem of tools used by researchers and big data analysts to explore and extract value from the deluge of relational data and disseminate a better understanding for people to think about a “connected” world.

Gephi is a “Photoshop” for graphs: designed to make data navigation and manipulation easy, it covers the entire process from data importing to aesthetics refinements and communication. Users interact with the visualization and manipulate structures, shapes and colors to reveal the properties of complex and messy data. The goal is to help data analysts make hypotheses and intuitively discover patterns or errors in large data collections.

Gephi’s project aims at providing the perfect tool to visualize and analyze networks. We focus on usability, performance and modularity:

  • Usability: Easy to install, an UI without scripts and real-time manipulation.
  • Performance: Visualization engine and data structures are built scalable. Supporting always-larger graphs is an endless challenge!
  • Modularity: Extensible software architecture, built on top of Netbeans Platform. Add plug-ins with ease.

Learn more about Gephi, watch Introducing Gephi 0.7, download and try it by following Quick Start Tutorial.

Gephi’s project is young, the growing community is composed of engineers and scientists involved in network science, datavis and complex networks.

List of ideas

List of ideas are availabe on our wiki. They cover various skills and level of difficulties:

* Completing Legend moduleComplete the Legend module, which was started in last year GSoC.
* GraphStore benchmark and tuningOptimize and tune GraphStore based on a serie of new well-defined benchmarks.

Please also propose your ideas on the forum. They will be considered and discussed by the community. Have a look at our long-term Roadmap.

Students, join the network

Students, apply now for Gephi proposals. Join us on the forum and fill in the questionnaire. Be careful, deadline for submitting proposals is May 3 (timeline)!

Hélder Suzuki, student for Gephi in 2009 and now software engineer at Google, wrote:
At Gephi students will have the opportunity to produce high impact work on a rapidly growing area and be noted for it.

View our previous Google Summer of Code projects here and read former students interviews.

Follow Gephi on Twitter

GSoC: interconnect Gephi Graph Streaming API and GraphStream

My name is Min WU and during this Google Summer of Code I have worked on the project to interconnect Gephi Graph Streaming API and the GraphStream library. My mentors are Yoann Pigné and André Panisson.

This project aims at interconnecting the GraphStream’s dynamic graph event model with Gephi in order to have Gephi to visualize an ongoing graph evolution and measurement. Based on this project, users can model and simulate complex systems with GraphStream while observing the output with the visual tools offered by Gephi.

GraphStream is written in Java. In order to use streams of graph events in other languages, GraphStream provides the NetStream framework, i.e. a network interface, such that other projects written in other language can use GraphStream. The NetStream framework consists of three parts, receiver, sender and the NetStream Protocol. The receiver is responsible for receiving graph events from the network and dispatching them to pipes. It works within only one thread, listening at a given address and port while receiving graph events from several streams, actually several threads or clients. The sender encodes graph events into messages according to the NetStream protocol and send them to a defined receiver with given port, host and stream ID. Every message contains sourceId, timeId and event context, among which the combination of sourceId and timeId is dedicated to distinguish between several streams and solve the synchronization issue. Finally the NetStream protocol specifies the message format at byte level.

Gephi also supports the idea of “streams of graph events”. It has a framework for graph streaming in Gephi plugin built by André Panisson during the 2010 GSoC, through a multi-threaded socket server. Other applications can push graph data to the Gephi server through the network, and have it visualized. In this graph streaming project, operations (a concept similar to event) are invoked through HTTP requests made by the client to the server, based on a JSON format.

Work done

In my project, I interconnected Gephi and GraphStream based on André’s Graph Streaming plugin. Since NetStream on GraphStream side works on NetStream protocol while Graph Streaming API on Gephi side works on JSON protocol, we have to make them compatible with each other. Considering the flexible interoperability and language agnostic properties, I have chosen the JSON protocol to do the interconnection and implement a sender part and a receiver part.

The sender part (JSONSender) is responsible for sending events from GraphStream to Gephi. GrpahStream works as a client and Gephi works as a server. Every time the graph in GraphStream changes, a corresponding event is sent to Gephi. Gephi handles the event and changes its own graph. In this way, the sender part works as a sink of the GraphStream graph, so it must implement the sink interface which contains methods to deal with graph element events and attribute events. In each method, we first encode the event message into a JSON string, and then send it to Gephi. We connect to Gephi and use “updateGraph” operation to send events. The corresponding URL is “http://host:port/workspace?operation=updateGraph”. The host and port must match with the Gephi sever and the workspace is a destination workspace of Gephi, for example an URL can be “http://127.0.0.1:8080/workspace0?operation=updateGraph”. The Gephi server and client are built with the “Graph Streaming API ” in the Gephi-plugin.

The receiver part (JSONReceiver) is responsible for receiving events from Gephi. It listens to Gephi and waits for events. Every time the graph in the Gephi changes, a corresponding event will be send to GraphStream. Then the GraphStream handles the event and changes its graph object. In this way, the receiver part works as a source of the GraphStream graph. In order to listen to Gephi events, we use a URL within “getGraph” operation to connect to Gephi. The corresponding URL is “http://host:port/workspace0?operation=getGraph”.

With these two classes, we can interconnect GraphStream and Gephi in real-time. Two tutorials are given to show how to do real-time connection between GraphStream and Gephi, see the video below. If you are interested in the detail implementation, please refer to the manual page.

The first class is GraphSender, which aims at loading a graph in GraphStream and dynamically displays it on a Gephi workspace. We need to create a graph instance and a JSONSender instance, and plug the JSONSender instance as a sink of the graph instance. Since then, when we generate the graph, or load the graph from a file, Gephi will display it in real-time.

The other class is LinLogLayoutReceiver. The Lin-Log layout in GraphStream is dedicated to find communities in graphs. This tutorial shows the execution of a Lin-Log layout in GraphStream and the sending of the layout information to Gephi in real time. We first load a graph in Gephi, display it and apply some algorithms. Then we send the graph to GraphStream and apply the Lin-Log layout on the graph on the GraphStream side. Meanwhile we visualize the layout process on the Gephi side in real time. To achieve it, we create a graph instance and a JSONReceiver instance, and then get the ThreadProxyPipe instance and plug the graph instance as an ElementSink of the pipe instance. Then we apply the Lin-Log layout, and create a new thread in which to create a JSONSender instance and plugin it as a sink of the graph layout.

Distribution

This project is distributed under MIT license. You can refer to the code on Github. By the way, I feel very appreciative for my mentors’ supervision. Thank you very much!

GSoC: Legend module

My Name is Eduardo Gonzalo Espinoza Carreon and during this summer I developed the new Legend Module for Gephi, with the mentoring of Eduardo Ramos and Sébastien Heymann. This article will give you an overview of the work done.

Problem statement

Currently Gephi offers the possibility of visualizing graphs, but what about legends? Legends provide basic and extra information related to the graph and they are useful when interpreting any kind of network map. If a person is not familiar with the content of a graph, missing or wrong legends could lead to misleading interpretations and sometimes wrong decisions. When a visualization is used by multiple people for discussing, analyzing or communicating data, legends are of great importance.

For instance, the following graph represents the coappearance of characters in the novel Les Miserables. After performing a visual analysis we could only conclude that the graph has 9 groups. This is probably a little of the information the creator wanted to transmit. The graph has no information related to the number of nodes explored, or what the groups represent and how many elements each group has, etc.

A current workaround to solve this problem is to export the graph as an image, and then manually add the legends using Inkscape, Adobe Illustrator or another graphics editor. However this task is time-consuming and can be automated. The new Legend Module proposes a solution to this problem.

Solution

We propose an extension to the Preview module for generating legend items. The following legend items are available: Table, Text, Image, Groups and Description. They can be added using the Legend Manager, which is shown in a new tab under the Preview Settings:

After selecting a type of legend, the user chooses a sub-type builder, e.g. “Table” > “Partition interaction table”, or “Top 10 nodes with greatest degree”, as shown in the following figure:

When a new Legend item is added, it is displayed in the list of active legend items, where the user can edit its properties. The user can also edit its label and assign a user-friendly name to remember the content of the legend easily.

Every item has a set of common properties: label, position, width, height, background color and border, title, description; and also each type of item has its own properties and data. The values of those properties are editable through a Property Editor like the one used in the preview settings.

Some properties like scale and translation can be modified using the mouse like most of the graphic design applications. All legend items are designed with a smart way of autoresize. It’s not the common scale feature, e.g. if the text included in the Text Item is bigger than the size assigned, then the Text Renderer overrides the text font defined by the user and decreases the font size until the text is able to fit in the specified dimensions. The results of this feature are shown in the next figure:

Workflow

The legend builder retrieves the graph data (partitions, node labels, edge labels, etc) and creates a new Legend item for each of them. Then a legend renderer makes use of these information, plus the properties set by the user, to render the Legend item to the specified target: PNG, PDF or SVG.

For developers

The renderers can be extended. For instance, the default Group Renderer is:

Using external libraries like JFreeChart, we can extend it to create a Pie Chart Renderer like as follows:

Other types of items can be created by combining other available Legend Items or by extending Legend Item, Legend Item Builder and Legend Item Renderer.

The Legend Module also provides a save/load feature. So you can save your legends for future editing.

Limitations

Currently there are some limitations like selecting a specific renderer for each type of item, and also exporting legends to SVG format is not done automatically like PNG and PDF, e.g. Exporting an Image (they will be embedded in the SVG file).

Conclusions

I would like to thank Eduardo Ramos and Sébastien Heymann for their support and feedback, which was critical during the development of this new module. The Legend module will be available as core feature in next Gephi release.

This GSoC was a great opportunity to learn and it also represents my first important contribution to the open-source community.

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.

original
mode-1

mode-2
mode-3

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.

gui

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.

The GSoC rocket launched

GSoC_2012_logo_250pxThe Google Summer of Code 2012 has officially started! The results have been announced by Google. Congratulations to the students who join the Gephi project:

  • Eduardo Espinoza – Legend Module in Preview
  • Romain Yon – Cloud Gephi
  • Taras Klaskovsky – Force Directed Edge Bundling algorithm
  • Vikash Anand – Statistics Reports and HTML5 Charts
  • Min WU – Interconnect Graph Streaming API and GraphStream

You put a lot of attention on doing the bests applications and demonstrate great motivation in addition to strong technical skills. We are very excited to work with you guys!

This year we are also honored to count on world-class researchers as mentors: Yoann Pigné is an Assistant Professor at the university of Le Havre, France, and is a leader of the GraphStream project. We will co-mentor the Graph Streaming project with André Panisson, our former Google Summer of Code student. André got his Ph.D. recently, and authored the video of the Egyptian Revolution on Twitter. Finally, Christian Tominski, who mentored the Preview refactoring last year, will mentor the Force Directed Edge Bundling project. He is a Lecturer and Researcher at the Institute for Computer Science at the University of Rostock. He has authored several articles in the field of information visualization.

Former Google Summer of Code students will also mentor and advise students, like Luiz Ribeiro.

The Summer Timeline:

* Until May 21: Students get to know mentors, read documentation, get up to speed to begin working on their projects.
* May 21: Students starts to code
* July 13: Mid-term evaluation
* August 24: Final evaluation

Google Summer of Code 2012

GSoC_2012_logo_250pxIt’s a great news, Gephi has been accepted again for the Google Summer of Code. The program is the best way for students around the world to start contributing to an open-source project. Since 2009, each edition is a great success and dramatically boosted Gephi’s project development.

What is Gephi?

Networks are everywhere: email systems, financial transaction systems and gene-protein interaction networks are just a few examples. Gephi began as a university student project four years ago and has quickly become an open source software leader in the visualization and analysis of large networks. It is an important contribution to the ecosystem of tools used by researchers and big data analysts to explore and extract value from the deluge of relational data and disseminate a better understanding for people to think about a “connected” world.

Gephi is a “Photoshop” for graphs: designed to make data navigation and manipulation easy, it covers the entire process from data importing to aesthetics refinements and communication. Users interact with the visualization and manipulate structures, shapes and colors to reveal the properties of complex and messy data. The goal is to help data analysts make hypotheses and intuitively discover patterns or errors in large data collections.

Gephi’s project aims at providing the perfect tool to visualize and analyze networks. We focus on usability, performance and modularity:

  • Usability: Easy to install, an UI without scripts and real-time manipulation.
  • Performance: Visualization engine and data structures are built scalable. Supporting always-larger graphs is an endless challenge!
  • Modularity: Extensible software architecture, built on top of Netbeans Platform. Add plug-ins with ease.

Learn more about Gephi, watch Introducing Gephi 0.7, download and try it by following Quick Start Tutorial.

Gephi’s project is young, the growing community is composed of engineers and scientists involved in network science, datavis and complex networks.

List of ideas

List of ideas are availabe on our wiki. They cover various skills and level of difficulties:

* Legend moduleIntegrate a legend in the Preview module
* Flexible Table ImporterCreate a generic network creation wizard from data tables
* Cloud GephiBuild an online gallery and bring some of Gephi’s features to the cloud
* Force Directed Edge BundlingImplement Force Directed Edge Bundling algorithm
* Statistics Reports and HTML5 ChartsImprove statistic report and port existing charts to HTML5+Javascript
* Statistics Unit TestsAdd unit tests to the statistical algorithms
* Graph StreamingImprove Graph Streaming API and interconnect GraphStream’s dynamic graph event model with Gephi

Please also propose your ideas on the forum. They will be considered and discussed by the community. Have a look at our long-term Roadmap.

Students, join the network

Students, apply now for Gephi proposals. Join us on the forum and fill in the questionnaire. Be careful, deadline for submitting proposals is April 6 (timeline)!

Hélder Suzuki, student for Gephi in 2009 and now software engineer at Google, wrote:
At Gephi students will have the opportunity to produce high impact work on a rapidly growing area and be noted for it.

View our previous Google Summer of Code projects here and read former students interviews.

Follow Gephi on Twitter

screenshot_gephi1903

How 3 years of Google Summer of Code made us great

seb

This post was originally posted on the Google Open Source blog by Sébastien Heymann, co-founder of the Gephi project and Google Summer of Code administrator.

Networks are everywhere: email systems, financial transaction systems and gene-protein interaction networks are just a few examples. Gephi began as a university student project four years ago and has quickly become an open source software leader in the visualization and analysis of large networks. It is an important contribution to the ecosystem of tools used by researchers and big data analysts to explore and extract value from the deluge of relational data and disseminate a better understanding for people to think about a “connected” world.

Gephi is a “Photoshop” for such data: designed to make data navigation and manipulation easy, it covers the entire process from data importing to aesthetics refinements and communication. Users interact with the visualization and manipulate structures, shapes and colors to reveal the properties of complex and messy data. The goal is to help data analysts make hypotheses and intuitively discover patterns or errors in large data collections.

separator

Our success was made much faster thanks to the Google Summer of Code. The timing of our acceptance into our first Google Summer of Code in 2009 was perfect: we were at the point where we could make the project really open in the way our infrastructure could scale code, and our human organization was ready to welcome contributors. Participating in the program gave us a boost of fame helping us promote the project and created an international community for Gephi.

We met many people and learned a lot, but this is the most important lesson to share: though students are paid stipends for their work during the program, money should not be the first incentive. To encourage students to stick with the project, we talk with each of them to find their deeper motivations in working on Gephi and try and develop a win-win situation. And it works! Many of the students continue to contribute to the project for at least a few months after the end of the Google Summer of Code program, and others have gone on to become members of our team.

We recognize this long-term investment by promoting their work, like André Panisson who released a plug-in in 2010, which connects Gephi to a graph stream and visualizes it in real-time. André made this amazing video of the Egyptian Revolution on Twitter, when he monitored the hashtag #jan25. More recently, Martin Škurla presented his work at FOSDEM 2012 and talked about his plug-in which connects Gephi to the graph database Neo4j. He started his project during the Google Summer of Code 2010 and continued his work until the release. We really appreciated the effort, so the Gephi Consortium and Neo Technologies Inc. paid his expenses to attend the conference. Finally, I must talk about Eduardo Ramos, who we rejected as a student two years ago for Google Summer of Code but who was so motivated that he decided to contribute to Gephi anyway, becoming one of the project leaders, a Google Summer of Code mentor… and a friend!

To learn more about Gephi, watch our madness screencast and view our previous Google Summer of Code projects here. Want to apply for Gephi? Join us on the forum.