We continue the line of research on graph compression started with WebGraph, but we move our focus to the compression of social networks in a proper sense (e.g., LiveJournal): the approaches that have been used for a long time to compress web graphs rely on a specific ordering of the nodes (lexicographical URL ordering) whose extension to general social networks is not trivial. In this paper, we propose a solution that mixes clusterings and orders, and devise a new algorithm, called Layered Label Propagation, that builds on previous work on scalable clustering and can be used to reorder very large graphs (billions of nodes). Our implementation uses overdecomposition to perform aggressively on multi-core architecture, making it possible to reorder graphs of more than 600 millions nodes in a few hours. Experiments performed on a wide array of web graphs and social networks show that combining the order produced by the proposed algorithm with the WebGraph compression framework provides a major increase in compression with respect to all currently known techniques, both on web graphs and on social networks. These improvements make it possible to analyse in main memory significantly larger graphs.
@cite_18: Abstract Since the first investigations on web-graph compression, it has been clear that the ordering of the nodes of a web graph has a fundamental influence on the compression rate (usually expressed as the number of bits per link). The authors of the LINK database [ 02], for instance, investigated three different approaches: an extrinsic ordering (URL ordering) and two intrinsic orderings based on the rows of the adjacency matrix (lexicographic and Gray code); they concluded that URL ordering has many advantages in spite of a small penalty in compression. In this paper we approach this issue in a more systematic way, testing some known orderings and proposing some new ones. Our experiments are made in the WebGraph framework [Boldi and Vigna 04], and show that the compression technique and the structure of the graph can produce significantly different results. In particular, we show that for a transposed web graph, URL ordering is significantly less effective, and that some new mixed orderi...
@cite_1: The Web Graph is a large-scale graph that does not fit in main memory, so that lossless compression methods have been proposed for it. This paper introduces a compression scheme that combines efficient storage with fast retrieval for the information in a node. The scheme exploits the properties of the Web Graph without assuming an ordering of the URLs, so that it may be applied to more general graphs. Tests on some datasets of use achieve space savings of about 10 over existing methods.
The only coordinate-free compression algorithm we are aware of The quite extensive survey in @cite_18 shows that many other approaches to web-graph compression, not quoted here, either fail to compress social networks, or are strongly dependent on the initial ordering of the graph. is that proposed by Apostolico and Drovandi in @cite_1 ; Our experiments show in fact a very limited variation in compression (10--15 URL ordering or from a random permutation, except for the altavista-nd dataset, which however is quite pathological. they exploit a breadth-first search (BFS) to obtain an ordering of the graph and they devise a new compression scheme that takes full advantage of it. Their algorithm has a parameter, the , which can be tuned to obtain different trade-offs between compression performance and time to retrieve the adjacency list of a node: at level 8 they attain better compression performances than those obtained by BV with Gray orderings and have a similar speed in retrieving the adjacency list. Even in this optimal setting, though, their approach is outperformed by the one we are going to present (see Table ).