Overview
WRS (Waiting Room Sampling) is a singlepass 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 stateoftheart 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 LocalityAware 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