GraphStream

Modeling Interaction Networks
Using Dynamic Graphs

Antoine Dutot & Yoann Pigné

LITIS — University of le Havre

Outlook



  • GraphStream's principles and capabilities

    • The dynamic graph model
    • Algorithms from Graph Theory
    • Viewing capabilities
  • Example applications

    • A simple graph example
    • A dynamic graph example
    • A wireless mobile network example
    • A Schelling's segregation model example

GraphStream

Modeling interaction networks using dynamic graphs.

  • Java library of components dedicated to dynamic graphs;
  • The main goal is to study interaction networks of any size and their dynamics;
  • Based on an event model in order to accommodate the dynamics from the start;
  • Provides several import / export components to interact with other tools of the domain.

GraphStream

Graph components

  • GraphStream provides several classes allowing to represent Graph structures.
    • "Single" graphs (1-graph), "multigraphs" (p-graphs, that are graphs where several edges can connect two nodes).
    • Directed, undirected graphs.
    • Several internal representations some ensuring fast data retrieval, other ensuring data compactness.
  • Such classes give a representation of a graph at a given time.
  • But this representation can evolve.

GraphStream

Graph components

  • Any number of data attributes can be associated with any element of the graph.
  • An attribute is made of an identifier and a value that can be any Java object.
  • You can place attributes on nodes, edges and on the graph itself.

GraphStream

The event model

  • The dynamics of the graph is expressed by an event model.
  • Events can be :
    • Addition or removal of nodes.
    • Addition or removal of edge.
    • Addition, update or removal of data attributes.
    • Time steps.
  • A stream of such events is used to modify graph structures.

GraphStream

The event model

  • Some components of GraphStream can produce such a stream of events. We call them Sources.
  • Some components can receive this stream of event to process it, we call them Sinks.
  • Some components are both source and sink, we call them Pipes.
  • A graph is a pipe.
Source
Sink
Pipe

GraphStream

Pipelining

  • Sources send their events to sinks using the listener metaphor.
  • This is quite comparable to the listeners often seen in Java GUI.
  • Sources, pipes and sinks can be connected in a pipeline of elements.
  • Exemple of an often used pipeline:

File Graph Viewer

GraphStream

Pipelining

The stream of events can flow between sources and sinks:

  • across the network,
  • processes,
  • threads.

For example a viewer can run in a distinct thread or machine, while a simulation on a graph runs on another.

Algorithms, metrology and generators

Various ways to operate on graphs

Algorithms:
  • observe and modify the graph and its dynamics.
  • Random Walks, Shortest paths, Spanning Trees, etc.
Metrology algorithms:
  • extract data from the graph and its dynamics.
  • Modularity, Centrality, Degree distribution, Connected components, etc.
Generators:
  • create graphs according to a model or from specific data.
  • Random, Preferential attachment, Small World, From GIS data, etc.

Graph Views

Several views on a graph or stream of graph event

View on data, metrology

  • Metrics allow to observe the graph and collect data during its evolution.

Graphical views

  • A rendering engine using CSS allows to represent graphs on screen.
  • The CSS allows to specify colors, sizes, shapes, images, labels, and interactive behaviour for nodes, edges and the graph itself.
  • A data rendering system based on symbols that can be attached to nodes or edges, or float anywhere on the drawing surface allows to render data attributes and to animate them.


Connection with other tools

  • There are various data import sources:
    • from graph file formats;
    • from internet data (networks of pages, blogs, social, citation);
    • from geographic information systems (GIS);
    • etc.
  • It is possible to connect easily a program or simulation that dynamically generate data with GraphStream components.

GraphStream and simulations

GraphStream can be used...

  • ... to study « the records » of a simulation under the form of a dynamic graph with data attributes.
  • ... as a toolbox to directly create simulations on interaction networks.
  • ... as a way to experiment on various data.

Installation

We will be using eclipse to test GraphStream:

  1. You can find the files needed to work on the tutorial here: XXXX
  2. Download the eclipse package for your OS.
  3. Uncompress it in a place of your choice.
  4. Download the TutorialECSS2010.zip.
  5. Uncompress it in a place of your choice, this should create a TutorialECSS2010 directory.

Installation

The base code for the tutorials is available in a "workpace" for eclipse:

  1. Open the eclipse folder you uncompressed previously and launch eclipse.
  2. When it asks for a work space, browse the file system to select the TutorialECSS2010 folder then click OK.

Installation

  1. You should see eclipse appear with at the left the four parts of the tutorial.

Tutorial 1: basis tasks with GS

Creating a basic graph and displaying it

Open Tutorial1 > src > eccs2010 > Tutorial1.java:

import org.graphstream.graph.*;
import org.graphstream.graph.implementations.*;

public class Tutorial1 {
	public static void main(String args[]) {
		Graph graph = new SingleGraph("Tutorial 1");
		
		graph.display();
		
		graph.addNode("A");
		graph.addNode("B");
		graph.addEdge("AB", "A", "B");
		graph.addNode("C");
		graph.addEdge("BC", "B", "C", true); // Directed edge.
		graph.addEdge("CA", "C", "A");
	}
}

Tutorial 1

Basic tasks with GS

We can improve the display with some CSS:

...
graph.display();

graph.addAttribute("ui.quality");
graph.addAttribute("ui.antialias");
graph.addAttribute("ui.stylesheet",
	"edge { fill-color: grey; }");

graph.addNode("A");
...

Tutorial 1

Basic tasks with GS

  • Each node, edge and attribute is identified by an unique string.
  • The node and edge elements are created for you.
  • You can access them however, when created:
    Node n = graph.addNode("A");
  • Or after creation:
    Node n = graph.getNode("A");

Tutorial 1

Basic tasks with GS

  • You can remove nodes and edges the same way:
    graph.removeNode("A");
  • You can change the graph this way at any time. Each change is considered as an “event”.
  • The sequence of changes is seen as the dynamics of the graph.
  • There are many other ways to modify the graph.

Tutorial 1

Basic tasks with GS

  • Data stored in the graph, on nodes and edges, are called “attributes”.
  • An attribute is a pair (name,value).

Edge ab = graph.getEdge("AB");
Edge bc = graph.getEdge("BC");
Edge ca = graph.getEdge("CA");

ab.setAttribute("ui.label", "AB");
bc.setAttribute("ui.label", "BC");
ca.setAttribute("ui.label", "CA");

Tutorial 1

Basic tasks with GS

  • But you can add any kind of data on each graph element.
  • However not all attributes appear in the viewer.
  • Notice the way you can add arrays with setAttribute() and a variable number of arguments:

ab.setAttribute("aNumber", 10);
bc.setAttribute("anObject", new Double(10));
ca.setAttribute("anArrayOfThings", 1, 2, 3);

Tutorial 1

Basic tasks with GS

  • You can access attributes in several ways:

int value1 = ((Number) ab.getAttribute("aNumber")).intValue();
double value2 = (Double) bc.getAttribute("anObject");
Object[] value3 = (Object[]) ca.getAttribute("anArrayOfThings");

  • Special methods are here to simplify things:

double value4 = ab.getNumber("aNumber");
double value5 = bc.getNumber("anObject");

Tutorial 1

Basic tasks with GS

  • Travelling through all nodes of the graph is easy:

for(Node n: graph) {
	System.out.println(n.getId());
}

  • The same for edges:

for(Edge e: graph.getEachEdge()) {
	System.out.println(e.getId());
}

Tutorial 1

Basic tasks with GS

  • You can also do it with iterators:

Iterator<? extends Node> nodes = graph.getNodeIterator();

while(nodes.hasNext()) {
	System.out.println(nodes.next().getId());
}

  • The same for edges:

Iterator<? extends Edge> edges = graph.getEdgeIterator();

while(edges.hasNext()) {
	System.out.println(edges.next().getId());
}		

Tutorial 1

Basic tasks with GS

  • You can also travel the graph using nodes:

import static org.graphstream.algorithm.Toolkit.*;
...
Node node = getRandomNode(graph);

for(Edge e: node.getEachEdge()) {
	System.out.printf("neighbor %s via %s%n",
		e.getOpposite(node).getId(),
		e.getId() );
}

  • Toolkit is a collection of often used methods and small algorithms.
  • Each node and edge allows to iterate on its neighbourhood.

Tutorial 1

Basic tasks with GS

  • You can iterate on directed edges:

Node node = getRandomNode(graph);
Iterator<? extends Edge> edges = node.getLeavingEdgeIterator();

  • Or:

Iterator<? extends Edge> edges = node.getEnteringEdgeIterator();

  • And get the node degree, entering or leaving:

System.out.println(“Node degree %d (entering %d, leaving %d)%n”,
	node.getDegree(),
	node.getInDegree(),
	node.getOutDegree());

Tutorial 2

A first dynamic graph

  • Each graph is a source of events.
  • You can connect to any source using the Source.addSink(Sink) method.
  • You can choose to receive only events concerning the graph structure with addElementSink(ElementSink). Elements are nodes and edges.
  • You can choose to receive only events concerning data attributes stored on elements with addAttributeSink(AttributeSink).
  • A Sink is only an empty interface inheriting ElementSink and AttributeSink.

Tutorial 2

A first dynamic graph

An element sink must follow the interface:

public interface ElementSink {
	void nodeAdded( ... );
	void nodeRemoved( ... );
	void edgeAdded( ... );
	void edgeRemoved( ... );
	void graphCleared( ... );
	void stepBegins( ... );
}

Tutorial 2

A first dynamic graph

An attribute sink must follow the interface:

public interface AttributeSink {
	void graphAttributeAdded( ... );
	void graphAttributeChanged( ... );
	void graphAttributeRemoved( ... );

	void nodeAttributeAdded( ... );
	void nodeAttributeChanged( ... );
	void nodeAttributeRemoved( ... );

	void edgeAttributeAdded( ... );
	void edgeAttributeChanged( ... );
	void edgeAttributeRemoved( ... );
}

Tutorial 2

A first dynamic graph

A source is an interface that only defines methods to handle a set of sinks.

public interface Source {
	void addSink(Sink sink);
	void removeSink(Sink sink);
	void addAttributeSink(AttributeSink sink);
	void removeAttributeSink(AttributeSink sink);
	void addElementSink(ElementSink sink);
	void removeElementSink(ElementSink sink);
	void clearElementSinks();
	void clearAttributeSinks();
	void clearSinks();
}

Tutorial 2

A first dynamic graph



These three interfaces are the most important of GraphStream.

Tutorial 2

A first dynamic graph

  • As the graph is also a sink, you could use these methods to create the graph.
  • But a better way is to send graph events using an existing source, like a file.
  • Few graph file formats are dynamic.
  • GraphStream provides a format named DGS that allows to store and load dynamic graphs.

Tutorial 2

A first dynamic graph

A DGS file looks like this. You can find it in the Tutorial2 > tutorial2.dgs

DGS003
"Tutorial 2" 0 0
an "A"
an "B"
an "C"
ae "AB" "A" "B"
ae "BC" "B" "C"
ae "CA" "C" "A"
ce "AB" label="AB"
ce "BC" label="BC"
ce "CA" label="CA"
  • an add a node and ae an edge.
  • ae "AB" "A" > "B" adds a directed edge.
  • cn, ce and cg change or add one or more attributes on a node, edge or graph.
  • dn and de allow to remove nodes, edges.

Tutorial 2

A first dynamic graph

  • Each change in the graph is an event.
  • However you may want to define a notion of time, and group some events as occurring "at the same time".
  • You can do this using a step.
  • The DGS notion for steps is st <number>.

Tutorial 2

A first dynamic graph

  • The ability to remove nodes and edges make the format dynamic.
  • Add this to the our previous DGS file:
st 2
an "D"
an "E"
ae "BD" "B" "D"
ae "CE" "C" "E"
ae "DE" "D" "E"
de "AB"
dn "A"
st 3
  • And save it.

Tutorial 2

A first dynamic graph

  • We will now read this file.
  • This can be done in one simple operation :

graph.read("tutorial2.dgs");

  • However this will "play" all events as fast as possible.
  • We have no control over the speed at which events occur.
  • This form of reading is an utility method of the Graph interface allowing to read static graphs from all the supported file formats.

Tutorial 2

A first dynamic graph

  • We can read the DGS file event by event using an input source:

public class Tutorial2 {
	public static void main(String args[]) {
		Graph graph = new SingleGraph("Tutorial2");
		graph.display();
		graph.addAttribute("ui.antialias");
		try {
			FileSource source = FileSourceFactory.sourceFor(
				"tutorial2.dgs");
			source.addSink(graph);
			source.begin("tutorial2.dgs");
			while(source.nextEvents());
			source.end();
		} catch(Exception e) { e.printStackTrace(); }
	}
}

Tutorial 2

A first dynamic graph

  • We read the file event by event, however it still does it as fast as it can.
  • Note the line while(source.nextEvents()); that does the job.
  • Also note that we have to call the begin() and end() methods before and after reading to cleanly open and close the file.
  • Now change the line:

			while(source.nextEvents()) { Thread.sleep(1000); }

  • An run the program anew.

Tutorial 2

A first dynamic graph

  • The graph is automatically reshaped for you.
  • However you may want to position nodes by yourself.
  • You can do this using the x and y attributes:

an "A" x=0 y=1
an "B" x=1 y=-1
an "C" x=-1 y=-1

  • And:

an "D" x=1 y=1 
an "E" x=-1 y=1

Tutorial 2

A first dynamic graph

  • You have to tell the viewer it should not place nodes for you:

		graph.display(false);

  • You can now run the program anew.

Tutorial 3

A simple mobility model with GraphStream

  • People with mobile communicating devices are moving in a given place.
  • Their devices have a limited range of communication with others.
  • Each time they are close enough, a link is created to exchange data.

    

Tutorial 3

A simple mobility model with GraphStream

  • The ad-hoc network created through this process is dynamic : links appear and disappear.
  • It can be modelled by a dynamic graph where devices are nodes and communication links are edges.
  • We will now model such mobile devices behaviour and the resulting dynamic graph with GraphStream.

Tutorial 3

A simple mobility model with GraphStream

  • We will use the “random waypoint” mobility model:
    • Each person chooses a random destination,
    • Walks with a random speed toward it,
    • And stands still at this position for a random time.
    

Tutorial 3

A simple mobility model with GraphStream

  • We will create two Java classes:
    • MobileDevice, and
    • MobilityModel.
  • The first one will represent a moving person with a communicating device.
  • The second will represent a set of such mobile devices, and will run each device iteratively in a loop.

Tutorial 3

A simple mobility model with GraphStream

Here is the structure of a MobileDevice:

public class MobileDevice {
	protected double x, y;				// Current position.
	protected double targetx, targety;	// Destination.
	protected double speed;				// Speed factor.
	protected int pause;				// How many time to wait.
	protected Graph graph;				// The graph.
	protected Node node;				// The node for this device.
	public MobileDevice( Graph graph, String name );
	public void next();	// Move a little, wait or find a new target.
	protected boolean closeTo( Node other );// Close to another?
	protected void nextTarget();		// Choose a random target.
	protected void move();				// Move a little.
	protected boolean atTarget();		// Arrived at target?
	protected void checkEdges();		// Check the connectivity.
}

Tutorial 3

A simple mobility model with GraphStream

public MobileDevice(Graph graph, String name) {
	this.graph = graph;	
	this.x = Math.random();
	this.y = Math.random();
	nextTarget();
	node = graph.addNode( name );// Associate the device with a node.
}

public void next() {		// Our three behaviours.
	if (pause > 0) {
		pause--;			// Stand still.
	} else if(atTarget()) {
		nextTarget();		// Choose a next target, speed, and wait.
	} else {
		move();				// Move a little toward the target.
	}
}

Tutorial 3

A simple mobility model with GraphStream

protected void nextTarget() {
	targetx = Math.random();			// New random destination.
	targety = Math.random();
	speed   = Math.random()*0.1f;		// New random speed.
	pause   = (int)(Math.random()*10);	// New random pause time at
}										// target.

protected void move() {
	x += (targetx-x)*speed;		// Move a little.
	y += (targety-y)*speed;
	node.setAttribute("x", x);	// Modify the node attributes to move
	node.setAttribute("y", y);	// it in the graph viewer.
}

Tutorial 3

A simple mobility model with GraphStream

  • It remains a method that is actually empty:
protected void checkEdges() {
	// To be done ...
}
  • It remains a method that is actually empty:

Tutorial 3

A simple mobility model with GraphStream

Here is the mobility model structure:

public class MobilityModel {
	protected ArrayList<MobileDevice> devices;// Set of mobile devices.
	protected int deviceCount = 200;					// N devices.
	protected int steps = 10000;							// Simulate N steps.
	protected Graph graph;										// The dyn. ad-hoc net.

	public MobilityModel();										// Runs the simulation.

	protected void addMobileDevices(int number);// Create N devices.
	protected void runMobileDevices();				// Run each device in turn.
	protected void checkEdges();							// Check the coms.
	protected void sleep();						
}

Tutorial 3

A simple mobility model with GraphStream

Here is how the mobility model works:

public MobilityModel() {
	graph = new DefaultGraph();			// The network.
	graph.display( false );
	addMobileDevices(deviceCount);	// Add N mobile devices.
	for( int i=0; i<steps; i++ ) {		// For N steps do:
		runMobileDevices();						// Make each device move or stand.
		checkEdges();									// Check the connectivity, that is
		sleep();											// which device can “see” others.
	}
}

Tutorial 3

A simple mobility model with GraphStream

protected void runMobileDevices() {
	for( MobileDevice device: devices )
		device.next();
}

protected void checkEdges() {
	for( MobileDevice device: devices )
		device.checkEdges();
}

Tutorial 3

A simple mobility model with GraphStream

  • If you run this example, you see nodes moving in the GS viewer window.
  • It still lacks the edges...
  • As a demonstration, we propose a method that is fast to code, but not to run since to check the connectivity of one devices requires to look at each other devices.
  • In other words, the algorithm is in O(n²).

Tutorial 3

A simple mobility model with GraphStream

protected void checkEdges() {
	// Look at edges to remove :
	Iterator<?extends Edge> edges = node.getEdgeIterator();
	ArrayList<String> toRemove = new ArrayList<String>();
	while( edges.hasNext()) {
		Edge edge = edges.next();
		if(!closeTo(edge.getOpposite(node))) {
			toRemove.add(edge.getId());
		}
	}

	for(String edge: toRemove)
		graph.removeEdge(edge);

	// TODO look at edges to add.
	...

Tutorial 3

A simple mobility model with GraphStream

	...
	for(Node other: graph) {
		// If close enough but not too much :
		if(other != node && closeTo(other)) {
			// If not already connected :
			if(!node.hasEdgeToward(other.getId())) {
				// Edge creation in the graph :
				graph.addEdge(
					String.format("%s-%s", node.getId(), other.getId()),
					node.getId(), other.getId());
			}
		}
	}
}

Tutorial 4

About Schelling's Segregation Model

  • Two populations modeled with cells of a cellular automata
  • Depending on its neighbors a cell may move away
       

Tutorial 4

About Schelling's Segregation Model

  • We propose to observe the evolution of the two populations
  • Dynamic representation of the evolution on a graphs

Tutorial 4

First step: display the graph

	private void initGraph()
	{
		graph = new DefaultGraph("Segregation Model Graph");
		
		// Modify the graph here
		graph.display();
		
	}

Tutorial 4

Second step: get real coordinates

  • disable the layout in initGraph();
    		// Add code here
    		graph.display(false);
  • update position in move() and initPlaces()
    		// Add code here
    		n.addAttribute("x", i);
    		n.addAttribute("y", dimension - j);
    			// Add code here
    			n1.addAttribute("x", i);
    			n1.addAttribute("y", dimension - j);
    			// Add code here for nodes position
    			n2.addAttribute("x", i);
    			n2.addAttribute("y", dimension - j);

Tutorial 4

Third step: get gradient colors with Style Sheets

  • Get the style Sheet
	protected static final String styleSheet = ""
		+ "graph {"
		+ "	padding: 10px;" 
		+ "}" 
		+ "node {"
		+ "	fill-mode: dyn-plain;" 
		+ "	fill-color: gray, red;" 
		+ "}";
		// Add code here
		graph.addAttribute("ui.antialias");
		graph.addAttribute("ui.stylesheet", styleSheet);
		graph.display(false);

Tutorial 4

Third step: get gradient colors with Style Sheets

  • Get the gradients change (in checkNeighbors())
		// Add code here
		double color =  n.getNumber("ui.color");
		if (n.getDegree() < threshold)
		{
			move(n, place);
			// Add code here
			n.addAttribute("ui.color", 
            Math.min(1.0, color + ( epsilon)));
		} else
		{
			// Add code here
			n.addAttribute("ui.color", 
            Math.max(0.0, color - (0.1f * epsilon)));
		}
	}

Tutorial 4

Third step: get gradient colors with Style Sheets

  • Get the gradients initialized (in initPlaces())
			// Add code here
			n1.addAttribute("x", i);
			n1.addAttribute("y", dimension - j);
			n1.addAttribute("ui.color", 0.0);
			// Add code here
			n2.addAttribute("x", i);
			n2.addAttribute("y", dimension - j);
			n2.addAttribute("ui.color", 0.0);