DOULION: counting triangles in massive graphs with a coin

361 citations recorded by the source corpus.

How researchers see this paper

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

Wedge sampling for computing clustering coefficients and triangle counts on large graphs † (2013, methodology): “However, the Doulion estimate can suffer from high variance [29].”
PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations (2009, methodology): “, PageRank [17] and HITS [18]), computing the number of triangles [19], [20], computing the diameter [21], topic detection [22], attack detection [23], with too-many-to-list alternatives for each of the above tasks.”
Mining of Massive Datasets (2011, methodology): “[17] discusses randomized algorithms for triangle finding.”
Max-cover in map-reduce (2010, neutral): “[36].”
Bernstein-like Concentration and Moment Inequalities for Polynomials of Independent Random Variables: Multilinear Case (2011, methodology): “ected graph which has applications in ﬁnding the hidden thematic structure of the web [5] and usage as a feature to assist the classiﬁcation of web activity as spamming or not [3]. Tsourakakis et al. [12] introduced the technique of randomly sampling each edge with probability p and then estimating ”