Triadic Measures on Graphs: The Power of Wedge Sampling
arXiv:1202.5230 · doi:10.1137/1.9781611972832.2
Abstract
Graphs are used to model interactions in a variety of contexts, and there is a growing need to quickly assess the structure of a graph. Some of the most useful graph metrics, especially those measuring social cohesion, are based on triangles. Despite the importance of these triadic measures, associated algorithms can be extremely expensive. We propose a new method based on wedge sampling. This versatile technique allows for the fast and accurate approximation of all current variants of clustering coefficients and enables rapid uniform sampling of the triangles of a graph. Our methods come with provable and practical time-approximation tradeoffs for all computations. We provide extensive results that show our methods are orders of magnitude faster than the state-of-the-art, while providing nearly the accuracy of full enumeration. Our results will enable more wide-scale adoption of triadic measures for analysis of extremely large graphs, as demonstrated on several real-world examples.
References in corpus (2)
Cited by in corpus (20)
- A Scalable Generative Graph Model with Community Structure
- A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets
- Counting Triangles in Massive Graphs with MapReduce
- Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs
- Detecting Strong Ties Using Network Motifs
- TRUST: Triangle Counting Reloaded on GPUs
- Capturing Dynamics of Information Diffusion in SNS: A Survey of Methodology and Techniques
- Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs
- Directed closure measures for networks with reciprocity
- A General Framework for Estimating Graphlet Statistics via Random Walk
- Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
- Graph Distance from the Topological View of Non-backtracking Cycles
- A sampling framework for counting temporal motifs
- EGBTER: Capturing degree distribution, clustering coefficients, and community structure in a single random graph model
- Counting Triangles in Real-World Graph Streams: Dealing with Repeated Edges and Time Windows
- Efficient Butterfly Counting for Large Bipartite Networks
- Number of Connected Components in a Graph: Estimation via Counting Patterns
- PES: Priority Edge Sampling in Streaming Triangle Estimation
- How the Degeneracy Helps for Triangle Counting in Graph Streams
- A space efficient streaming algorithm for triangle counting using the birthday paradox