Hannu Reittu | A graph compression method inspired by Szemerédi's Regularity Lemma

Hannu Reittu (Technical Research Centre of Finland, VTT), joint work with Fülöp Bazsó and Ilkka Norros

Abstract:
A large scale graph compression method and algorithms are proposed. Our method is inspired by the Szemerédi's regularity lemma. Another ingredient of the method is the Rissanen's minimum description length principle (MDL). In the proposed modelling framework several cases of graphs are considered, undirected, directed and weighted. Our approach is also applicable for finding similar structure in matrices with real and non-negative elements.