2014 CatchSyncCatchingSynchronizedBe

• (Jiang et al., 2014) ⇒ Meng Jiang, Peng Cui, Alex Beutel, Christos Faloutsos, and Shiqiang Yang. (2014). “CatchSync: Catching Synchronized Behavior in Large Directed Graphs.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623632

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+CatchSync%3A+Catching+Synchronized+Behavior+in+Large+Directed+Graphs
• http://dl.acm.org/citation.cfm?id=2623330.2623632&preflayout=flat#citedby

Quotes

Author Keywords

• Anomalous behavior; on-line information services; outlier detection; zombie follower

Abstract

Given a directed graph of millions of nodes, how can we automatically spot anomalous, suspicious nodes, judging only from their connectivity patterns? Suspicious graph patterns show up in many applications, from Twitter users who buy fake followers, manipulating the social network, to botnet members performing distributed denial of service attacks, disturbing the network traffic graph. We propose a fast and effective method, CatchSync, which exploits two of the tell-tale signs left in graphs by fraudsters: (a) synchronized behavior: suspicious nodes have extremely similar behavior pattern, because they are often required to perform some task together (such as follow the same user); and (b) rare behavior: their connectivity patterns are very different from the majority. We introduce novel measures to quantify both concepts ("synchronicity" and "normality ") and we propose a parameter-free algorithm that works on the resulting synchronicity-normality plots. Thanks to careful design, CatchSync has the following desirable properties: (a) it is scalable to large datasets, being linear on the graph size; (b) it is parameter free; and (c) it is side-information-oblivious: it can operate using only the topology, without needing labeled data, nor timing information, etc., while still capable of using side information, if available. We applied CatchSync on two large, real datasets 1-billion-edge Twitter social graph and 3-billion-edge Tencent Weibo social graph, and several synthetic ones; CatchSync consistently outperforms existing competitors, both in detection accuracy by 36% on Twitter and 20% on Tencent Weibo, as well as in speed.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 CatchSyncCatchingSynchronizedBe	Christos Faloutsos Alex Beutel Peng Cui Shiqiang Yang Meng Jiang			CatchSync: Catching Synchronized Behavior in Large Directed Graphs				10.1145/2623330.2623632		2014