Think before You Discard:
Accurate Triangle Counting
in Graph Streams with Deletions

Overview

ThinkD (Think before you Discard) is a streaming algorithm for triangle counting in a fully dynamic graph stream with edge additions and deletions.
ThinkD estimates the counts of global and local triangles by making a single pass over the stream.
ThinkD has the following advantages:

• Accurate: ThinkD is up to 4.3X more accurate than its best competitors within the same memory budget
• Fast: ThinkD is up to 2.2X faster for the same accuracy requirements
• Theoretically Sound: ThinkD always maintains unbiased estimates

Paper

ThinkD is described in the following papers:

• Think before You Discard: Accurate Triangle Counting in Graph Streams with Deletions
  Kijung Shin, Jisu Kim, Bryan Hooi, and Christos Faloutsos
  European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD) 2018, Dublin, Ireland
  [Paper] [Supplementary Document] [BIBTEX]
  
  
• Fast, Accurate and Provable Triangle Counting in Fully Dynamic Graph Streams
  Kijung Shin, Sejoon Oh, Jisu Kim, Bryan Hooi, and Christos Faloutsos
  ACM Transactions on Knowledge Discovery from Data (TKDD) (Accepted)
  [Paper] [BIBTEX]
  

Code

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

Datasets