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

By Paolo Boldi, Marco Rosa, Massimo Santini, Sebastiano Vigna. The Web Conference, 2010

709 citations recorded by the source corpus.

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 analyse in main memory significantly larger graphs.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/e41956966fbbde4a25b420ab0cf32b62ab6e2589

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Direction-optimizing Breadth-First Search (2012, background): “The real social networks are taken from a variety of web crawls [6, 7, 12, 16, 21, 23, 25, 26].”
Random Graphs and Complex Networks (2016, methodology): “Interestingly, the configuration model was invented by Bollobás (1980) to study uniform random regular graphs (see also (Bollobás, 2001, Section 2.”
FAST-PPR: scaling personalized pagerank estimation for large graphs (2014, methodology): “The DBLP-2011 [26], Twitter-2010 [26] and UK 2007-05 Web Graph [26, 27] were downloaded from the Laboratory for Web Algorithmics [19].”
From "Think Like a Vertex" to "Think Like a Graph" (2013, methodology): “These datasets were provided by the WebGraph [4] and the LLP [3] projects.”
PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs (2012, neutral): “5B Amazon [6, 5] 0.”
The Limits of Popularity-Based Recommendations, and the Role of Social Ties (2016, neutral): “Twitter LAW The twitter-2010 graph by the Laboratory for Web Algorithmics, Univ. Milan [4, 3].”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, methodology): “Following [6], we optimize a quadratic penalty relaxation for vertex cover eswiki-2013 where n ≈ 970K, and d ≈ 23M and wordassociation-2011 with n ≈ 10K and d ≈ 72K [18, 19, 20].”
PyTorch-BigGraph: A Large-scale Graph Embedding System (2019, methodology): “We embed a publicly available Twitter 12 subgraph (Kwak et al., 2010) (Boldi & Vigna, 2004) (Boldi et al., 2011) containing a social network be-tween 41,652,230 nodes and 1,468,365,182 edges with a single relation called “follow”.”
Four degrees of separation (2011, background): “…the information-theoretical lower bound) for the current graphs in the original order and for the same graphs permuted by layered label propagation [2]. l itseitseusfb l l l l l l l l l l l Figure 2: The probability mass functions of the distance distributions of the current graphs (truncated at…”
DEMON: a local-first discovery method for overlapping communities (2012, background): “To efficiently detect these structures is very useful for a number of applications, ranging from targeted vaccinations and outbreak prevention [23], to viral marketing [16] and to many web data analysis tasks such as finding tribes in online information exchanges [12, 25], data compressing, clusteri”
GPS: a graph processing system (2013, methodology): “(2)These datasets were provided by “The Labaratory for Web Algorithmics” [23], using software packages WebGraph [7], LLP [6] and UbiCrawler [5].”
Fast exact shortest-path distance queries on large networks by pruned landmark labeling (2013, background): “Indochina: This is a web graph of web pages in the country domains of Indochina countries, crawled in 2004 [9,8].”
Gemini: A Computation-Centric Distributed Graph Processing System (2016, neutral): “Table 2: Graph datasets [5, 6, 7, 20] used in evaluation.”