Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks

We continue the line of research on graph compression started in [BV04], but we move our focus to the compression of so-cial networks in a proper sense (e.g., LiveJournal): the ap-proaches that have been used for a long time to compress web graphs rely on a specific ordering of the nodes (lexico-graphical 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 algo-rithm, called Layered Label Propagation, that builds on pre-vious work on scalable clustering and can be used to reorder very large graphs (billions of nodes). Our implementation uses task decomposition to perform aggressively on multi-core architecture, making it possible to reorder graphs of more than 600 millions nodes in a few hours. Experiments per-formed on a wide array of web graphs and social networks show that combining the order produced by the proposed al-gorithm 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 net-works. These improvements make it possible to analyse in main memory significantly larger graphs.