2015 MASCOTMemoryEfficientandAccurat

• (Lim & Kang, 2015) ⇒ Yongsub Lim, and U Kang. (2015). “MASCOT: Memory-efficient and Accurate Sampling for Counting Local Triangles in Graph Streams.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783285

Subject Headings: Graph Stream Mining; Triangle Counting.

Cited By

• http://scholar.google.com/scholar?q=%222015%22+MASCOT%3A+Memory-efficient+and+Accurate+Sampling+for+Counting+Local+Triangles+in+Graph+Streams
• http://dl.acm.org/citation.cfm?id=2783258.2783285&preflayout=flat#citedby

Quotes

Author Keywords

• Anomaly detection; data mining; edge sampling; graph algorithms; graph stream mining; local triangle counting.

Abstract

How can we estimate local triangle counts accurately in a graph stream without storing the whole graph? The local triangle counting which counts triangles for each node in a graph is a very important problem with wide applications in social network analysis, anomaly detection, web mining, etc. In this paper, we propose MASCOT, a memory-efficient and accurate method for local triangle estimation in a graph stream based on edge sampling. To develop MASCOT, we first present two naive local triangle counting algorithms in a graph stream: MASCOT-C and MASCOT-A. MASCOT-C is based on constant edge sampling, and MASCOT-A improves its accuracy by utilizing more memory spaces. MASCOT achieves both accuracy and memory-efficiency of the two algorithms by an unconditional triangle counting for a new edge, regardless of whether it is sampled or not. In contrast to the existing algorithm which requires prior knowledge on the target graph and appropriately set parameters, MASCOT requires only one simple parameter, the edge sampling probability. Through extensive experiments, we show that for the same number of edges sampled, MASCOT provides the best accuracy compared to the existing algorithm as well as MASCOT-C and MASCOT-A. Thanks to MASCOT, we also discover interesting anomalous patterns in real graphs, like core-peripheries in the web and ambiguous author names in DBLP.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 MASCOTMemoryEfficientandAccurat	U Kang Yongsub Lim			MASCOT: Memory-efficient and Accurate Sampling for Counting Local Triangles in Graph Streams				10.1145/2783258.2783285		2015