AN EXPERIMENTAL STUDY ON COMPRESSED REPRESENTATIONS OF WEB GRAPHS AND SOCIAL NETWORKS BASED ON DENSE SUBGRAPH EXTRACTION

Abstract

The compressed web graph and social networks structures proposed by Hernandez and Navarro (Compressed representations for web and social graphs. Knowl. Inf. Syst. 40(2): 279-313 (2014)) support more queries than alternative approaches, including in-neighbor, out-neighbour, and mining queries. Their main strategy is to extract dense subgraphs from the given graph, and encode them using succinct data structures such as wavelet trees. Previous experimental studies on wavelet trees, however, test performance using textual data, which are drastically different from the data generated from web graphs. We thus engineer wavelet tree implementations for compressed web graph and social network structures. In particular, we propose a new wavelet tree encoding approach called combined encoding which can provide better time/space tradeoffs than previous approaches when used in Hernandez and Navarroa's framework to represent web graphs.