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


GraphStream


Simtools Workshop
Paris, June 5th 2013

GS Logo

Outlook

  1. Dynamic Graphs
  2. GraphStream
  3. The Event Model
  4. Algorithms
    1. Search, Metrics, Generators
    2. Focus on Dynamic Connected Components & Dynamic Shortest Paths
  5. Visualisation
    • Layout, Sprites, Style Sheets
  6. Realtime Interaction (NetStream)
    • with NetLogo, with Gephi, and more...

First, static graphs

Structure:

  • Nodes, Vertices
  • (undirected) Edges, Links
  • (directed) Arcs

Algorithms: Graphs Theory

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

When we add dynamics...

What kind of dynamics?

  • values/weight on edges or nodes?
  • nodes and/or edges added/removed?

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

What about Dynamic Graph Theory?

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


In a nutshell

Java library with a handy public API

  Graph g = new DefaultGraph("MyGraph");
  g.read("some-file.tlp");
  g.getDegree();
  g.display();

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

Interaction with over tools

Architecture

Public API

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

Organised into sub-projects

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

Get GraphStream!

On the website

On Github

On Maven

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

GraphStream's Event Model

The dynamics of the graph is expressed by an event model

Events can be:

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.

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.addSink( graph );
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:

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

Pipelining

Receive events from another some other process/thread/programme/machine

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

while (true) {
  pipe.pump();
  Thread.sleep(1);
}

Graph components

Several classes for various graph structures.

Several internal representations:

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

Data Attributes

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();
}

Algorithms

Some tutorials to go farther


http://graphstream-project.org/doc/Algorithms/

Visualization

Aims

Extra visual information

CSS

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

Extra visual information

CSS classes

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

Node a = graph.addNode("A");
Node b = graph.addNode("B");
Node c = graph.addNode("C");
graph.addEdge("AB", "A", "B");
graph.addEdge("CB", "C", "B");
graph.addEdge("AC", "A", "C");
a.addAttribute("ui.class", "fun");
b.addAttribute("ui.class", "fun");
c.addAttribute("ui.class", "dull");

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);
Sprite pin = sman.addSprite("pin");

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

files

  • 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

import org.graphstream.stream.netstream.NetStreamReceiver;
//...
NetStreamReceiver net = new NetStreamReceiver(2001);
ThreadProxyPipe pipe = net.getDefaultStream();
pipe.addSink(graph);
while (true) {
  pipe.pump();
  Thread.sleep(100);
}

Interactions with Gephi

GraphStream is co-mentoring a Google Summer of Code project with André Panisson along with the Gephi consortium.


Slides and Material



Get the Slides and Materials online:

http://graphstream-project.org/doc/Tutorials/Lab-Sessions/Simtools-2013/

https://github.com/graphstream/gs-talk-simtools