Graph compression, also known as graph summarization or graph reduction/simplification aims to construct a summary which is a smaller graph or a simpler representation of it.   Existing work show that graph compression is not only a tool to reduce the memory size needed for massive graphs, but also an interesting preprocessing step that can improve the complexity of graph algorithms. Compression also finds application in learning where finding a way to represent or encode the graph structure is necessary to exploit existing machine learning models. Several lossy and lossless compression methods are proposed in the literature. However, most of the compression algorithms proposed in the literature are not incremental and cannot be used to build or update the summary of a dynamic graph.

The main objective of this thesis is to explore the incrementality aspects of graph compression algorithms in order to be able to build summaries for dynamic graphs or graph streams.