Showing Overlapping Communities in Complex Networks with GraphStream

My Ph.D. is focused on methods for overlapping community detection in complex networks. Complex networks are usually represented by graphs, mathematical abstractions of collections of objects (nodes) joined by lines (edges). These simple structures are very powerful and suitable to represent many complex systems, such as social networks, gene expression networks, transportation networks and many others.

There are several methods and algorithms for community detection with distinct approaches, however, the research in this field is much more related to physics and mathematics than to computer science or software engineering. My personal belief is that is the reason that many tools designed to solve the community detection problem lack of good quality visualization tools, or even do not offer any visualization at all.

Since I finished my first algorithm for overlapping community detection, MADOC (Memetic Algorithm to Detect Overlapping Communities). I started searching for a way to produce beautiful, or at least, good quality representation of overlapping communities. My first approach for small networks was reading the results of the algorithm and then use design software (eg. Adobe Illustrator) to produce high-quality representations of graphs with overlapping communities. This approach, however, is not practical due to the amount of time consumed drawing the communities over the graph. See an example here.

Figure 1 – Complex network of the co-appearance of Les Miserables Characters.

Luckily enough, this week I had the opportunity to try some Java Libraries and found the GraphStream Library. With allows using a syntax similar to CSS and nodes can assume a pie-chart shape. Therefore, I could use distinct colors for a single node, representing the communities of the node. The following Java Project shows the use of Graphstream to show overlapping communities on graphs.

To use the GraphStream library, download and add the .jar files as libraries to the Java Path of a Java Project. If you use Eclipse will be similar to this. On NetBeans is very similar as well.

Figure 2 – Adding the GraphStream library to a Java Project on Eclipse.

After that, you can create a class and start using the library to show graph files in the format .net or .gml.

In the following small example, a file named karate.net in a folder named karate is imported and displayed with some properties.

import java.io.IOException;
import org.graphstream.graph.ElementNotFoundException;
import org.graphstream.graph.Graph;
import org.graphstream.graph.implementations.SingleGraph;
import org.graphstream.stream.GraphParseException;

public class Visualization {
  publicstaticvoidmain(String[] args){
    System.setProperty("org.graphstream.ui.renderer","org.graphstream.ui.j2dviewer.J2DGraphRenderer");
  Graph Karate = new SingleGraph("Karate");
  Karate.read("karate/Karate.net");
  Karate.getNode("33").setAttribute("ui.style","shape:pie-chart;fill-color:rgb(127,0,55),rgb(255,0,110),rgb(1,127,1);");
  Karate.getNode("33").setAttribute("ui.pie-values","0.333,0.333,0.333");
  Karate.getNode("34").setAttribute("ui.style","shape:pie-chart; fill-color: rgb(255,0,110), rgb(0,255,1);");
  Karate.getNode("34").setAttribute("ui.pie-values","0.5,0.5");
  Karate.getNode(0).setAttribute("ui.style","shape:pie-chart; fill-color: rgb(255,0,110), rgb(0,255,1);");
  Karate.getNode(0).setAttribute("ui.pie-values","0.5,0.5");
  Karate.addAttribute("ui.quality");
  Karate.addAttribute("ui.antialias");
  Karate.addAttribute("ui.stylesheet","url('style.css')");
  Karate.display();
 }
}

Notice that, in the first line of the main method there is an instruction to the library to use the J2DGraphRenderer, this is not the default graph renderer, and, if you do not set to this specific renderer, the library will not show the pie-chart like nodes.

All the process is very straight forward, for each node that you want to use the pie-chart representation you must set the ui-style, like this:

Karate.getNode("34").setAttribute("ui.style","shape:pie-chart; fill-color: rgb(255,0,110), rgb(0,255,1);");

The fill-color attribute must have at least the number of colors that you want to show in the pie-chart node, and the shape attribute must be pie-chart. In addition, it is necessary pass the ui.pie-values, the sum of all values must be 1.

Karate.getNode("34").setAttribute("ui.pie-values","0.5,0.5");

This must be done for each node that you want to represent as a pie-chart. Obviously through an algorithm and not one-by-one as shown in the example.

The next steps are adding the desired attributes to the visualization ui.quality and ui.antialias to make the Graph smooth. (This is optional).

You can also attach a stylesheet with CSS like properties to your visualization using addAttribute(“ui.stylesheet”,”url(‘style.css’)”);.

The CSS file used in this example has the following rules.

graph {
 fill-color: rgb(255,255,255);
}
edge {
 size:2px;
 /*shape:cubic-curve;*/
 /*shape:blob;*/
}
node{
 size:40px;
 text-size:18px;
 fill-color:rgb(155,155,155);
 text-color:rgb(255,255,255);
 stroke-mode:plain;
 stroke-width:2px;
 stroke-color:#FFF8;
}

You can play around with the shape attribute to edges to change the visualization of the edges. This example will produce a graph similar to the graph shown on Figure 3.

Figure 3 – Zachary Karate Club Network with some overlapping nodes.

In Figure 4 an example is shown with all the nodes colored and some overlapping nodes and the edges colored according to the color of the source node.

Figure 4 – The “Natural Overlapping Communities” on Zachary’s Network.

The algorithm used to build the communities will be probably subject of a new post. If you like to try a more stylish and radical approach to design the edges, uncomment the line in the CSS file and make the shape of the edges like a blob, shape:blob. The result is similar to shown on Figure 5.

Figure 5 – The Karate Club Network with colored nodes and edges. Edges are show as blob shapes.

Thanks for reading. I hope this small tutorial can help someone else.

Advertisement