document: Layered label propagation : a multiresolution coordinate-free ordering for compressing social networks 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 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 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 analyze in main memory significantly larger graphs .
doc_bio_tags: O O O O O O O O O O B I O O O O O O O B I O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O B I O O O O O O O O O O O O O O O