Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs

Abstract

Graphs are used to model interactions in a variety of contexts, and there is a growing need to quickly assess the structure of such graphs. Some of the most useful graph metrics are based on triangles, such as those measuring social cohesion. Algorithms to compute them can be extremely expensive, even for moderately-sized graphs with only millions of edges. Previous work has considered node and edge sampling; in contrast, we consider wedge sampling, which provides faster and more accurate approximations than competing techniques. Additionally, wedge sampling enables estimation local clustering coefficients, degree-wise clustering coefficients, uniform triangle sampling, and directed triangle counts. Our methods come with provable and practical probabilistic error estimates for all computations. We provide extensive results that show our methods are both more accurate and faster than state-of-the-art alternatives.

Full version of SDM 2013 paper "Triadic Measures on Graphs: The Power of Wedge Sampling" (arxiv:1202.5230)

References in corpus (5)

• Community structure and scale-free collections of Erdös-Rényi graphs
• Triadic Measures on Graphs: The Power of Wedge Sampling
• Counting Triangles in Massive Graphs with MapReduce
• Degree Relations of Triangles in Real-world Networks and Models
• Directed closure measures for networks with reciprocity

Cited by in corpus (14)

• Higher-order organization of complex networks
• The Power of Pivoting for Exact Clique Counting
• Graph Sample and Hold: A Framework for Big-Graph Analytics
• Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
• Slim Graph: Practical Lossy Graph Compression for Approximate Graph Processing, Storage, and Analytics
• Attributed Hypergraph Generation with Realistic Interplay Between Structure and Attributes
• Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE
• Accurate and Fast Estimation of Temporal Motifs using Path Sampling
• How to Count Triangles, without Seeing the Whole Graph
• Sampling Multiple Nodes in Large Networks: Beyond Random Walks
• Counting Triangles in Real-World Graph Streams: Dealing with Repeated Edges and Time Windows
• On the Complexity of Sampling Nodes Uniformly from a Graph
• Efficient and Adaptive Estimation of Local Triadic Coefficients
• A space efficient streaming algorithm for triangle counting using the birthday paradox