Graph Twiddling in a MapReduce World

By Jonathan Cohen. 2009

423 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Information Systems

How researchers see this paper

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

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Information Systems

Citations in the corpus

Truss Decomposition in Massive Networks (2012, methodology): “We also show that our algorithm is signiﬁcantly more efﬁcient than the existing algorithms for truss decomposition [15, 16] in small networks.”
Wedge sampling for computing clustering coefficients and triangle counts on large graphs † (2013, methodology): “Recent work by Cohen [16] and Suri and Vassilvitskii [17] give MapReduce implementations of these algorithms.”
Max-cover in map-reduce (2010, methodology): “See the wishful thinking article by Cohen [7] and the inspiration and frustration expressed by Muthukrishnan [30].”
Fast personalized PageRank on MapReduce (2011, methodology): “MapReduce provides an excellent tool for large scale graph processing as well, and graph algorithms have been designed for it in the literature [15, 16, 6].”
Book Reviews: Data-Intensive Text Processing with MapReduce by Jimmy Lin and Chris Dyer (2010, methodology): “[80] presented an approach to estimating the diameter of large graphs using MapReduce and a library for graph mining [81]; Cohen [39] discussed a number of algorithms for processing undirected graphs, with social network analysis in mind; Rao and Yarowsky [128] described an implementation of label p”
The Combinatorial BLAS: design, implementation, and applications (2011, background): “On the other hand, it is possible to implement some clustering and connected components algorithms using the MapReduce model (Dean and Ghemawat, 2008), but the approaches are quite unintuitive and the performance is unknown (Cohen, 2009).”
Querying k-truss community in large and dynamic graphs (2014, methodology): “Core decomposition and truss decomposition have been studied in various settings, including in-memory algorithms [2, 7, 26], external-memory algorithms [4, 21], and MapReduce algorithm [8].”
The Stratosphere platform for big data analytics (2014, methodology): “Thealgorithm is formulated in [21] as a sequence of two MapReduce jobs, where the ﬁrst reducer is responsible for building all triads (pairs of connected edges), while the second reducer simulates a join between triads and edges to ﬁlter out all triads that cannot be closed by a matching edge.”
Pregel: a system for large-scale graph processing (2010, background): “Graph algorithms can be written as a series of chained MapReduce invocations [11, 30].”
Handbook of Big Data (2016, background): “Just like the correlations r ( x, y ), the values n ( x, y ) and m ( x, y ) form n × n tables; hence, they can be easily visualized with blockplots in their fractional forms n ( x, y ) /n and m ( x, y ) /n .”