WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams

Overview

WRS (Waiting Room Sampling) is a single-pass streaming algorithm for global and local triangle counting in (fully dynamic) real graph streams.
WRS exploits a temporal dependency pattern in real dynamic graph streams.
WRS has the following properties:

• Fast and Any time: WRS scales linearly with the number of edges in the input graph stream, and gives estimates at any time while the input graph grows
• Effective: estimation error in WRS is up to 47% smaller than those in state-of-the-art methods
• Theoretically Sound: WRS gives unbiased estimates with small variance under the temporal locality.

Paper

WRS is described in the following paper:

• WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams.
  Kijung Shin
  IEEE International Conference on Data Mining (ICDM) 2017, New Orleans, USA
  [PDF] [Supplementary Document] [BIBTEX]
  
  
• Temporal Locality-Aware Sampling for Accurate Triangle Counting in Real Graph Streams.
  Dongjin Lee, Kijung Shin, and Christos Faloutsos
  The VLDB Journal, 2020,
  [PDF] [BIBTEX]
  
  

Code

The source code used in the paper is available. [Github Repository]

Datasets

People

• Dongjin Lee (KAIST)
• Kijung Shin (KAIST)
• Christos Faloutsos (Carnegie Mellon University)