GraphStream

A Dynamic Graph Library

Politechnika Poznańska – April 24th 2018

Sources

Codes and Presentations are on GitHub

Sources for Codes and Presentations
Sources for Codes and Presentations

Outline

  • General Presentation of GraphStream (this presentation)
    • Dynamic Graphs
    • GraphStream
    • The Event Model
    • Algorithms
    • Visualisation
    • Interaction with other tools
  • Demonstrations and Examples

First, static graphs

Structure:

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

First, static graphs

Algorithms: Graphs Theory

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

When we add dynamics…

What kind of dynamics?

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

When we add dynamics…

Problem with algorithms

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

Dynamic Graph Models

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

Complex Networks

  1. Exploration: Analysis of “real world” networks (web graphs, biological networks, social networks)

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

Aggregative Methods

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.

Aggregative Methods
Aggregative Methods

Re-optimisation

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.

Re-optimization
Re-optimization

GraphStream

Study interaction networks and their dynamics

  • Dynamic Algorithms
  • Dynamic Visualisation

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

In a nutshell

A Java library with a handy public API

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 graphstream-project.org/doc/API

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

Organised into sub-projects github.com/graphstream

  • gs-core, gs-algo,
  • gs-ui-swing, gs-ui-javafx, gs-ui-android
  • gs-netstream, gs-boids, gs-netlogo, gs-geography, …

Get GraphStream!

On the Website

On Github

On Maven

Use any version of GraphStream with jitpack.io

GraphStream’s Event Model

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.

GraphStream’s Event Model

Sources

Produce streams of events.

Sinks

Receive streams of events.

Pipes

Both source and sink. A graph is a pipe.

Pipelining

Sources send events to sinks.

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

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

Example Pipeline
Example Pipeline

Pipelining

File-Graph-Viewer Pipeline
File-Graph-Viewer Pipeline

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.

Proxy Pipe
Proxy Pipe

Pipelining

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

Graph components

Various graph structures

  • Single graph (1-graph),
  • Multi-graph (p-graph), graphs where several edges can connect two given nodes.
  • Directed and/or 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 key, value pair that can be any Java Object.
  • You can place attributes on nodes, edges and on the graph itself.

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

Focus on Dynamic Shortest Paths

Algorithms

Some tutorials to go further

graphstream-project.org/doc/Algorithms/

Visualization

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

CSS

Extra visual information

CSS

css1css2css3css4

Extra visual information

CSS classes

Extra visual information

CSS classes

…and of course it is dynamic.
…and of course it is dynamic.

Extra visual information

Sprites

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

Sprites are also customised with CSS pin

LH
LH

Interactions with other Tools

Offline interactions

File formats

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

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)

NetLogo Extension

  • 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
NetLogo Extension
NetLogo Extension