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.
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 |
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 |