MASCOT

Memory-efficient Accurate Sampling for Counting LOcal Triangles in Graph Streams

Overview

We propose local triangle counting algorithms in a graph stream based on edge sampling: MASCOT for a single graph stream, and MultiBMASCOT and MultiWMASCOT for a multigraph stream. To develop MASCOT, We first devise two edge sampling based naive algorithms MASCOT-C and MASCOT-A which have the advantages of memory-efficiency and low variance. Our proposed algorithm MASCOT takes both advantages by the strategy of "unconditional counting before sampling"

For a multigraph stream, MultiBMASCOT provides binary triangle counting, i.e. ignoring the effect of duplicated edges. This is the same as counting local triangles for the correponding simple graph. MultiWMASCOT provides weighted triangle counting where a weight of an edge is determined by the number of its repeated occurences. Concretely, MultiWMASCOT counts each triangle as the product of the weights of the participating three edges.

Code

Here is a download link for our MASCOT implementation. [Download]

Paper

MASCOT is described in the following paper.

Dataset

Simple Graphs

Name # Nodes # Edges Description Name # Nodes # Edges Description
Advogato 5,155 39,285 Trust network NotreDame 325,729 1,090,108 Web graph of Notre Dame
Enron 36,692 183,831 Enron email excahnges Petster 623,766 15,699,276 Social websites for cat and dog owners
Wiki-Conflict 116,836 2,027,871 Edit confliction BerkStan 685,230 6,649,470 Web graph of Berkeley and Stanford
Gowalla 196,591 950,327 Online social network DBLP 1,314,050 5,362,414 Co-author network in DBLP
Movies9 253,045 6,611,899 Co-reviewed movies in Amazon LiveJournal 4,846,609 42,851,237 LiveJournal online social network
Stanford 281,903 1,992,636 Web graph of Stanford.edu

Multigraphs

Name # Nodes # Edges Description Name # Nodes # Edges Description
Actor 382,219 33,115,812 Actor collaboration in movies ItWiki 1,703,605 86,548,398 Hyperlinks in Italian Wikipedia
Baidu 415,641 3,284,387 "related to" links in encyclopedia Baidu ChinWiki 1,930,275 3,284,387 Hyperlinks in Chinese Wikipedia
DBLP 1,314,050 18,986,618 Co-author network in DBLP

People