arXiv preprint ·
Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Triangle counting is one of the most fundamental problems in network analysis. Given the massive sizes of real-world graphs, there is a long history of small-space streaming algorithms providing accurate estimates for this problem. However, most of the results focus on estimating the total triangle count or the number of triangles incident to individual nodes. In practice, one often wants fine-grained information to understand how triangles are distributed, as captured by clustering coefficients. In particular, a standard network analysis task requires computing the binned degree-wise clustering coefficient distribution, which provides a rich and informative summary of the structure of the graph. In this work we present BOLIDE, the first efficient and practical algorithm for estimating binned degree-wise clustering coefficients in streaming. Our algorithm makes a single pass over the edge stream, and is allowed to store only a small fraction of the total number of edges. BOLIDE carefully combines different sampling strategies to efficiently gather degree and triangle information across sets of nodes. As a result, our algorithm provably approximates the binned degree-wise clustering coefficients, and provides guarantees on the amount of memory used. Our experimental evaluation shows that BOLIDE accurately estimates clustering coefficient distributions while efficiently processing large datasets with billions of edges and triangles.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Inverse Lyndon Array
High-Dimensional Ultra-Log-Concave Distributions
An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem
Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata
On Deterministically Computing Total Variation Distance via Zonotope Compression
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.