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:

Paper

ThinkD is described in the following papers:


Code

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

Datasets

Name#Nodes#EdgesDescriptionSourceDownload
Epinion132K711K Trust network Network Repository, SNAP Link
Facebook63.7K817K Friendship network MPI SWS Link
Enron87.0K1.13MEmail network KONECT, CMU Link
BerkStan675K6.65M Web graph SNAP Link
Youtube3.22M9.37M Friendship network Network Repository, MPI SWS Link
Patent3.77M16.5M Patent citation network SNAP, NBER Link
DBLP1.28M18.2MAuthor collaboration network KONECT Link
Flickr2.30M22.8MFriendship network KONECT, MPI-SWS Link
Wikipedia2.86M19.3M Communication network KONECT Link
Movie382K33.1M Actor collaboration network KONECT Link
Orkut3.07M117MFriendship network SNAP and MPI-SWS Link
FriendSter65.6M1.81BFriendship network KONECT Link

People