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 tocompress web graphs rely on a specific ordering of the nodes (lexicographicalURL ordering) whose extension to general social networks is not trivial. Inthis paper, we propose a solution that mixes clusterings and orders, and devisea new algorithm, called Layered Label Propagation, that builds on previous workon scalable clustering and can be used to reorder very large graphs (billionsof nodes). Our implementation uses overdecomposition to perform aggressively onmulti-core architecture, making it possible to reorder graphs of more than 600millions nodes in a few hours. Experiments performed on a wide array of webgraphs and social networks show that combining the order produced by theproposed algorithm with the WebGraph compression framework provides a majorincrease in compression with respect to all currently known techniques, both onweb graphs and on social networks. These improvements make it possible toanalyse in main memory significantly larger graphs.
展开▼
