Gephi project propose the following proposals. Don’t hesitate asking for further information. We are also open for any other proposal from you.

Friends often talk about using Gephi with multitouch or just using it for the beauty of results. Smart ideas sometimes just came like this, applications don’t need to be centered only on Gephi software. They can be a challenging network case study, a Gephi plugin or a project using Gephi visualization module. Let us know.

Proposals can be downloaded as PDF and shared.

1 – Shader Engine

Difficulty: Hard
Required skills: Java, OpenGL, GLSL

This proposal is an experimental work about drawing large networks using GPU Shaders technology to improve performances and scalability. The aim is to create a basic 3D engine using suggested technologies and use it for drawing as many nodes and edges as possible.

Existing Gephi 3D engine is intended to be used with old hardware and so don’t profit from GPU revolution. Basically the engine draw only very basic shapes (sphere or cube for nodes and lines for edges), but a LOT of them. Drawing millions of objects, even if it is the same object is currently far from possible.

Shaders technologies have interesting features for our topic. For instance Geometry Shaders and (Pseudo-)Instancing techniques enhance performance when duplicating objects. Other techniques could be explored to reduce the amount of needed vertices or computing.

We suggest this draft roadmap:

• Getting started with loading and executing vertex and fragment shaders within a JOGL routine in a sample application.
• Try pseudo-instancing techniques for duplicating an existing shape, for instance a sphere.
• If available, use Geometry Shaders to implement an instancing test case.
• Try to create a Shader which will help to reduce sphere mesh size. For instance see if it is possible to create a sphere from only few triangles.
• Experimentation for increasing edge drawing performance using Shaders.
• Propose nice post-processing effects if you like!

Resources

* JOGL Website
* GLSL Definition
* GLSL Specifications
* GLSL Tutorial
* JOGL Developer forum
* OpenGL Geometry Instancing
* Instancing resources
* OpenGL resources from Nvidia
* Molecular visualization PyMOL and QuteMol

2 – Network algorithms and statistics

Difficulty: Easy
Required skills: Basic graph theory, Java

This proposal focuses on network analysis, through statistics and various algorithms. Though Gephi focus on powerful and easy-to-use exploration features, it is not enough to understand and classify all networks. Classical results like graph density, clustering coefficient or the number of weakly connected components help to recognize pattern and in general find features in network structure and data. Hence we propose to implement some of these algorithms in Gephi statistical module:

• Watts Strogatz Clustering Coefficient
• Pagerank
• HITS
• Network Diameter
• Node Betweenness Centrality
• Average Shortest Path

Implementing these algorithms will convey good overview on classical graph algorithms and some knowledge about fascinating results (like Watts-Strogatz Small Worlds model). Execution and results visualization tests will use native Gephi features.

A flexible architecture is able to host statistics algorithms and coding into needs only little programming experience. Moreover we will offer mentorship to get into existing interfaces. Existing documentation, resources and source code already exist on Internet for all of these algorithms. That’s why this proposal is an easy yet motivating idea.

Resources

* Detailed algorithms specification
* JUNG

Algorithms’ publications

* HITS : Kleinberg JM (1999). “Authoritative sources in a hyperlinked environment.” Journal of the ACM, 46(5), 604–632. PDF.
* Betweenness Centrality: Brandes U (2001). “A Faster Algorithm for Betweenness Centrality.” Journal of Mathematical Sociology, 25(2), 163–177. PDF.
* Pagerank: Page L, Brin S, Motwani R, Winograd T (1998). “The PageRank Citation Ranking: Bringing Order to the Web.” Technical report, Stanford Digital Library Technologies Project. PDF.
* Clustering Coefficient: Watts, D.J., Strogatz, S.H.(1998) Collective dynamics of ’small-world’ networks. Nature 393:440-442. PDF.

3 – Vectorial Preview

Difficulty: Medium
Required skills: Java, SVG basics

Gephi is able to export its network as SVG or PDF format. Using vectorial drawings for graph have many benefits like infinite zooming or clear shapes. The aim of this proposal is to develop a preview module in Gephi for seeing how the output will exactly looks like with the given parameters.

Whereas the embedded 3D engine is designed for efficient network exploration the vectorial export concentrate on clarity, readability and outstanding design. This module has many different settings like edge thickness, arrow size, white borders around labels, node border and so on. In the vein of WYSIWYG editors we would like to see direct setting change on a Vectorial Preview window. The module must be scalable to support large networks.

To resume there are two requirements, previewing the network exactly how it will looks-like in output and support huge graphs efficiently.

Technically the aim is to display the network exactly as it will be when opening the SVG, PDF or EPS in a postscript editor (Inkscape, Adobe Illustrator). This can be done with different approach, the student will have to compare and choose the most suitable. We propose following approach but we are open for your ideas as well.

Approach #1:

• Experiment existing SVG and Postscript Java interpreter. Use the output generated from Gephi Rich SVG Export module to reconstruct and display the network.

Approach #2:

• If the first approach fails, more things will have to be done from the root. A basic Java 2D previewer can be built for displaying the network. Given the fact the only objects we use are basic shapes, edges and labels, developing a mini interpreter isn’t unattainable. Actually this approach is similar to creating a 2D graph visualization module, which is well documented on Internet.

Resources

* Gephi Rich SVG Export
* Apache Batik
* Java2D