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

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-2016