# Dynamic Graphs...     ...and a tool to handle them

## GraphStream

Modeling and Simulation Platforms
ICCSA 20014
Le Havre, June 24nd 2014

## Outlook

1. Dynamic Graphs
2. GraphStream
3. The Event Model
4. Algorithms
5. Visualisation
6. Interaction with other tools
7. Demos
• basic demos
• simulation of a mobile ad hoc network

## First, static graphs

Structure:

• Nodes, Vertices
• (directed) Arcs

Algorithms: Graphs Theory

• graph colouring problems
• routing problems
• flow problems
• covering problems
• subgraphs problems

What kind of dynamics?

• values/weight on edges or nodes?

Problem with algorithms

• As soon as computed the result has vanished.
• Can we stop the graph and recompute?
• Depends on the dynamic graph model.

## Dynamic Graph Models

Many graph models consider in some ways the dynamics

• but they are bounded to their application domain

## Complex Networks

Exploration: analysis of "real world" networks (web graphs, biological networks, social networks)

Modelling: build artificial networks (preferential attachment)

Measures on graphs: community, distribution, dimensions, etc.

Iterative Construction/Iteration: graphs' dynamics

## Aggregative Methods

All the evolution is known in advance, the dynamic graph is aggregated into a static graph.

Why? Because it allows the use of classical graph theory.

## Re-optimisation

Build and maintain structures on dynamic graphs (e.g. spanning trees).

Updating an existing structure after some modifications is more effective that recomputing it from scratch.

## GraphStream

### Study interaction networks and their dynamics

• Dynamic Algorithms
• Dynamic Visualisation

• Stefan Balev
• Antoine Dutot
• Yoann Pigné
• Guilhelm Savin

## In a nutshell

Java library with a handy public API

```  Graph g = new SingleGraph("MyGraph");
g.getDegree();
g.display();```

Based on an event model: Nodes and Edges are Added/Removed/Modified

Interaction with over tools

• Offline: several import / export file formats
• Online: through the API or through a network connection

## Architecture

### Public API

• org.graphstream
• .graph
• .stream
• .ui
• .algorithm
• .util

• gs-core
• gs-algo
• gs-ui
• gs-netstream
• gs-deps
• gs-boids
• gs-netlogo
• gs-geography

## Get GraphStream!

### On Maven

```<groupId>org.graphstream</groupId>
<artifactId>gs-core</artifactId>
<version>1.2</version>```

## GraphStream's 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 events modifies the structure of a graph.

## GraphStream's Event Model

### Sources

They produce such stream of events.

### Sinks

They can receive such stream of event and process it.

### Pipes

They are both source and sink. A graph is a pipe.

Source
Sink
Pipe

## Pipelining

Sources send their events to sinks.

• Observer design pattern
• Publish / Subscribe
• Java Swing listeners

Sources, pipes and sinks can be connected in a pipeline of elements.

Example of an often used pipeline:

File

Graph

Viewer

## Pipelining

```Graph graph = new SingleGraph("Some Graph");
graph.display();
FileSource source = new FileSourceDGS();
source.begin("someFile.dgs");
while( source.nextEvents() ){
// Do whatever between two events
}
source.end();```

File

Graph

Viewer

## Pipelining

The stream of events can flow between sources and sinks:

• across the network,
• processes,

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

## Pipelining

```Graph g = new SingleGraph("RWP");
ThreadProxyPipe pipe = getPipeFromElsewhere(); //fake function
g.display(false);

while (true) {
pipe.pump();
}```

## Graph components

Several classes for various 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:

• fast data retrieval,
• data compactness.

Representation of a graph at a given time (static). But this representation can evolve.

## Data Attributes

• 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.
```g.addAttribute("My attribute", aValue);
Node n = g.getNode("A");
n.setAttribute("xy", 23.4, 55.0);
Edge e = g.getEdge("AB");
e.removeAttribute("selected");
double w = e.getNumber("weight");```

## Algorithms

### Searches

random searches, shortest paths, spanning trees, etc.

### Metrics

modularity, centrality, degree distributions, connectivity, density, etc.

### Generators

random, regular, preferential attachment, small world, from GIS, from the web, etc.

## Focus on Dynamic Connected Components

```import org.graphstream.algorithm.ConnectedComponents;
//...
ConnectedComponents cc = new ConnectedComponents();
cc.init(graph);
while(something) {
cc.getConnectedComponentsCount();
canDoSomethingWithGraph();
}```

## Focus on Dynamic Shortest Paths

```import org.graphstream.algorithm
.networksimplex.DynamicOneToAllShortestPath;
//...
DynamicOneToAllShortestPath algorithm =
new DynamicOneToAllShortestPath(null);
algorithm.init(graph);
algorithm.setSource("0");
while(something) {
algorithm.compute();
canDoSomethingWithGraph();
}```

## Visualization

### Aims

• Dynamic Visualization: the graph is evolving, so does the visualization.

## Extra visual information

### CSS

```graph { padding: 50px; }
node {
size-mode: fit; shape: rounded-box;
fill-color: white; stroke-mode: plain;
icon: url('data/Smiley_032.png');
}
```

## Extra visual information

### CSS classes

```graph.addAttribute("stylesheet",
+ "node {size: 100px; fill-mode: image-scaled;}"
+ "node.fun {fill-image: url('fun.gif');}"
+ "node.dull {fill-image: url('dull.png');}");

## Extra visual information

### CSS classes

...and of course it is dynamic.

## Extra visual information

### Sprites

Graphical objects that give extra information on the application you deal with.

```SpriteManager sman = new SpriteManager(graph);

Sprites are also tuneable with CSS:

```sprite#pin {
shape: box;
size: 32px, 52px;
fill-mode: image-scaled;
fill-image: url('mapPinSmall.png');
}```

## Extra visual information

### Some tutorials to go farther:

The CSS specification :
http://graphstream-project.org/doc/Tutorials/GraphStream-CSS-Reference_1.0/

A thorough tutorial on visualisation:
http://graphstream-project.org/doc/Tutorials/Graph-Visualisation_1.0/

Interactions

## Offline interactions

• Tulip
• Gephi
• GML
• Pajek
• DOT
• LGL
• ncol
• DGS

### DataBase(s)

• Neo4J
```DGS004
"graph.dgs" 0 0
an A x:1 y:2.3 label:"Node A"
an B x:0 y:0
an C xy:2.3,1
an D xyz:1,1
ae AB A B weight:23.3
ae AC A C weight:2
st 1.0
ae BC B > C
ae BD B > D
st 1.1
dn B```

## Online interactions: NetStream

• Export streams of events to other applications / machines / languages
• Both ways. From GS to other and from other to GS
• Binary network protocol
• TCP socket (and WebSocket) implementation
• Several languages (Java, C++, Python, JS)
```import org.graphstream.stream.netstream.NetStreamReceiver;
//...
https://github.com/graphstream/gs-talk/tree/iccsa2014 (branch `iccsa2014`)