Change Detection in a sequence of Graphs

This package is the reference code for most of my publications, please consider citing them.

Some are the following

• Change-Point Methods on a Sequence of Graphs
• Concept Drift and Anomaly Detection in Graph Streams
• Change Detection in Graph Streams by Learning Graph Embeddings on Constant-Curvature Manifolds
• Anomaly and Change Detection in Graph Streams through Constant-Curvature Manifold Embeddings
• Detecting Changes in Sequences of Attributed Graphs

Tutorial

Please have a look at this notebook tutorial.ipynb.

The package

The code is written in python3. In the package you will find following folders

• cdg/graph interface for datasets of graphs and dissimilarities.
• cdg/embedding several types of numeric representations of graphs, such as, dissimilarity representation and manifold embeddings.
• cdg/changedetection tests for change detection.
• cdg/utils utilities for the module.
• cdg/simulation utilities for repeated experiments.

Requirements and suggested packages

You may need:

• networkx (available pip install networkx)
• GraKel (available here)
• graph-matching-toolkit (available here) to compute graph edit distances. A good place to save it is ./graph-matching-toolkit/graph-matching-toolkit.jar.
• graphviz for visualize graphs.
• ecp R package (available here) in order to run certain multi change point methods.

Installation

Go to your preferred directory, then

git clone https://github.com/dzambon/cdg
cd cdg
sudo pip3 install -e .

Credits

Author: Daniele Zambon
Affiliation: Università della Svizzera italiana
eMail: daniele.zambon@usi.ch
Licence: BSD-3-Clause