Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks

Details Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks

2010-11-24

arxiv.org/abs/1011.5425v2

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-241455