A Dynamic Graph Library

Politechnika Poznańska – April 24th 2018

Codes and Presentations are on GitHub

- Code : github.com/graphstream/gs-talk
- Slides : graphstream.github.io/gs-talk

- General Presentation of GraphStream (this presentation)
- Dynamic Graphs
- GraphStream
- The Event Model
- Algorithms
- Visualisation
- Interaction with other tools

- Demonstrations and Examples

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

- graph colouring problems
- routing problems
- flow problems
- covering problems
- sub-graphs problems

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

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

Many graph models consider dynamics in some ways. But they are usually bounded to their application domain.

- Is there a general-enough model that can be used in a broad range of applications?
- What about a
**Dynamic Graph Theory**with algorithms for colouring, routing, flows, etc.?

**Exploration**: Analysis of “real world” networks (web graphs, biological networks, social networks)**Modelling**: Build artificial networks (Barabasi-Albert, Watts-Strogatz, Dorogovtsev-Mendes, Golomb , etc.)

- Measures on graphs: community, distribution, dimensions, etc.
- Iterative Construction/Iteration: we see dynamic graphs here!

All the evolution is known **in advance**, the dynamic graph is aggregated into a static graph. (Temporal Networks, Evolving Graphs, Time-Varying Graphs, etc.)

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

Build and maintain structures on dynamic graphs (e.g. spanning trees) **without** prior knowledge of the evolution.

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

**Study interaction networks and their dynamics**

- Dynamic Algorithms
- Dynamic Visualisation

A free and open-Source project supported by the University of Le Havre.

A Java library with a handy public API

```
Graph g = new SingleGraph("MyGraph");
g.read("some-file.tlp");
System.out.println("Average Degree: "+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

`org.graphstream`

`.graph`

`.stream`

`.ui`

`.algorithm`

`gs-core`

,`gs-algo`

,`gs-ui-swing`

,`gs-ui-javafx`

,`gs-ui-android`

`gs-netstream`

,`gs-boids`

,`gs-netlogo`

,`gs-geography`

, …

- graphstream-project.org
- legacy release (v1.3) of
`gs-core`

,`gs-algo`

,`gs-ui`

- github.com/graphstream
- bug tracker on the
`gs-core`

project - New Official Releases (v2.0)

Use any version of GraphStream with `jitpack.io`

The dynamics of the graph is expressed by an **event model**

Events

- 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.

Produce streams of events.

Receive streams of events.

Both source and sink. A **graph** is a pipe.

Sources send events to sinks.

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

Sources, pipes and sinks can be connected to form pipelines.

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.

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

- Single graph (1-graph),
- Multi-graph (p-graph), graphs where several edges can connect two given nodes.
- Directed and/or undirected graphs.

- fast data retrieval,
- data compactness.

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

- Any number of data attributes can be associated with any element of the graph.
- An attribute is
**key**,**value**pair that can be any Java Object. - You can place attributes on nodes, edges and on the graph itself.

random searches, shortest paths, spanning trees, etc.

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

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

Some tutorials to go further

- Dynamic Visualization: the graph is evolving, so does the visualization.
- Get more information than the graph itself: sprites.

```
graph.setAttribute("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.setAttribute("ui.class", "fun");
b.setAttribute("ui.class", "fun");
c.setAttribute("ui.class", "dull");
```

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

Sprites are also customised with CSS

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

- 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)

- NetLogo agents (turtles, links and observer) send graph events to external application
- The external application maintains a dynamic graph and runs algorithms on it
- It sends the computed results back to NetLogo
- Agents can receive and use them to take their decisions