Pushing the Envelope in Graph Compression
Panagiotis Liakos
Katia Papakonstantinopoulou
Michael Sioutis
Date published: 
Published In: 
23rd ACM International Conference on Information and Knowledge Management (CIKM 2014), Shanghai, China
Conference Article

We improve the state-of-the-art method for the compression of web and other similar graphs by introducing an elegant technique which further exploits the clustering properties observed in these graphs. The analysis and experimental evaluation of our method shows that it outperforms the cur- rently best method of Boldi et al. by achieving a better compression ratio and retrieval time. Our method exhibits vast improvements on certain families of graphs, such as so- cial networks, by taking advantage of their compressibility characteristics, and ensures that the compression ratio will not worsen for any graph, since it easily falls back to the state-of-the-art method.

Keywords: Graph compression, compact graph representation, social network graphs, graph clustering.

Related files: 

MaDgIK 2009-2018