Wedge sampling for computing clustering coefficients and triangle counts on large graphs†. (8th May 2014)

• Record Type: Journal Article
• Authors: Seshadhri, C.; Pinar, Ali; Kolda, Tamara G.
• Is Part Of: Statistical analysis and data mining. Volume 7:Number 4(2014)
• Page Start: 294
• Page End: 307
• Publication Date: 2014-05-08
• Subjects: Data mining -- Statistical methods -- Periodicals; 006.312
• DOI: 10.1002/sam.11224
• Languages: English
• ISSNs: 1932-1864

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>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 <italic>triangles</italic>, 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 <italic>wedge sampling</italic>, which provides faster and more accurate approximations than competing techniques. Additionally, wedge sampling enables estimating 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.</p> </abstract>