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 real graph streams.
WRS exploits a temporal dependency pattern in real dynamic graph streams.
WRS has the following properties:

Paper

WRS is described in the following paper:

Codes

The source codes used in the paper are available. [Github Repository]

Datasets

Name#Nodes#EdgesDescriptionSourceDownload
ArXiv3.06K346K Paper citation network SNAP, KDD Cup Graph, Time info
Facebook61.1K615K Friendship network MPI SWS Dynamic Graph
Email87.0K297K Email network KONECT, CMU Dynamic Graph
Youtube3.18M7.50M Friendship network Network Repository, MPI SWS Dynamic Graph
Patent3.77M16.5M Patent citation network SNAP, NBER Graph, Time info

People