On compressing social networks

By Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael M. Mitzenmacher, Alessandro Panconesi, Prabhakar Raghavan. 2009

393 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Computer Vision and Pattern Recognition, Graph Learning, Algorithms & Complexity

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Graph Learning

In Algorithms & Complexity

Citations in the corpus

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “A brute force scan of all elements of S can be prohibitively costly in applications which deal with massive data and care about the latency (e.g., search).”
Min-Max Kernels (2015, methodology): “In contrast, the resemblance kernel (2) has been widely used in practice on binary (or binarized) data [4, 5, 28, 9, 26, 7, 6, 11, 8, 16, 13, 1].”
Asymmetric Minwise Hashing (2014, background): “…for creating hash buckets leading to efﬁcient algorithms for numerous applications including spam detection [6], collaborative ﬁltering [4], news personalization [15], compressing social networks [13], graph sampling [14], record linkage [24], duplicate detection [20], all pair similarity [5], etc.”
Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks (2010, methodology): “The considerations above explain why this problem is lately emerging as one of the central algorithmic issues in the field of information retrieval [10, 7]; it should also be noted that improving the compression performance on a class of networks, apart for its obvious practical consequences, implie”
PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs (2019, neutral): “) [38] 42M 1.47B UK-2005 ( UK ) [4] 40M 936M Wiki ( WK ) [28] 5.7M 130M LJournal ( LJ ) [18] 5.4M 79M GWeb ( GW ) [42] 0.9M”
Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment (2015, background): “Later, because of its locality sensitive property [22], minhash became a widely used hash function for creating hash buckets leading to efficient algorithms for numerous applications including spam detection [6], collaborative filtering [4], news personalization [15], compressing social networks [13”
b-Bit Minwise Hashing for Estimating Three-Way Similarities (2010, methodology): “These techniques have been successfully applied to many tasks in machine learning, databases, data mining, and information retrieval [18, 36, 11, 22, 16, 39, 28, 41, 27, 5, 2, 37, 7, 24, 21].”
In Defense of Minhash over Simhash (2014, background): “…in the search industry, with numerous applications, for example, large-sale machine learning systems [23, 21], Web spam [29, 18], content matching for online advertising [25], compressing social networks [9], advertising diversiﬁcation [13], graph sampling [24], Web graph compression [5], etc.”
Improved Densification of One Permutation Hashing (2014, background): “…hashing is a popular indexing technique for a variety of large-scale data processing applications, which include duplicate detection [4, 13], all-pair similarity [3], fast linear learning [19], temporal correlation [10], 3-way similarity & retrieval [17, 23], graph algorithms [6, 11, 21], and more.”
WTF: the who to follow service at Twitter (2013, background): “Note that these calculations do not take into account the possibility of graph compression [5], which would reduce storage requirements substantially, although at the cost of slower access and restrictions on the types of graph operations supported.”
GraphChi: Large-Scale Graph Computation on Just a PC (2012, neutral): “Compact representation of realworld graphs is a well-studied problem, the best algorithms can store web-graphs in only 4 bits/edge (see [9, 13, 18, 25]).”