Advertisement
Published in:
2018 | OriginalPaper | Chapter
Tri-Fly: Distributed Estimation of Global and Local Triangle Counts in Graph Streams
Authors : Kijung Shin, Mohammad Hammoud, Euiwoong Lee, Jinoh Oh, Christos Faloutsos
Published in: Advances in Knowledge Discovery and Data Mining
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Given a graph stream, how can we estimate the number of triangles in it using multiple machines with limited storage?
Counting triangles (i.e., cycles of length three) is a classical graph problem whose importance has been recognized in diverse fields, including data mining, social network analysis, and databases. Recently, for triangle counting in massive graphs, two approaches have been intensively studied. One approach is streaming algorithms, which estimate the count of triangles incrementally in time-evolving graphs or in large graphs only part of which can be stored. The other approach is distributed algorithms for utilizing computational power and storage of multiple machines.
Can we have the best of both worlds? We propose Tri-Fly, the first distributed streaming algorithm for approximate triangle counting. Making one pass over a graph stream, Tri-Fly rapidly and accurately estimates the counts of global triangles and local triangles incident to each node. Compared to state-of-the-art single-machine streaming algorithms, Tri-Fly is (a) Accurate: yields up to 4.5\(\times \) smaller estimation error, (b) Fast: runs up to 8.8\(\times \) faster with linear scalability, and (c) Theoretically sound: gives unbiased estimates with smaller variances.