The DOI matches its Crossref record; 41 of the 41 references it cites were found in a registry or an index.
CatchSync: catching synchronized behavior in large directed graphs
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Finally, we highlight that our work can complement other methods used in prior work to detect fake and compromised accounts, such as using unsupervised anomaly detection techniques [50], temporal features [23, 24], IP addresses [45], as well as generic supervised learning [3].”
From Measuring, Characterizing, and Detecting Facebook Like Farms (2017) · cites this paper as [23]
Citations
Cites
An introduction to ROC analysis
Fawcett, T. (2006) · Pattern Recognition Letters · doi:10.1016/j.patrec.2005.10.010 · Cited by 21,879
Chandola, V., Banerjee, A., & Kumar, V. (2009) · ACM Computing Surveys · doi:10.1145/1541880.1541882 · Cited by 11,687
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 9,032
What is Twitter, a social network or a news media?
Kwak, H., Lee, C., Park, H., & Moon, S. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772751 · Cited by 6,652
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/316188.316229 · Cited by 4,279
Self-citationBroder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., & Wiener, J. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00083-9 · Cited by 2,810
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · ACM SIGCOMM Computer Communication Review · doi:10.1145/316194.316229 · Cited by 2,643
Self-citationOutlier detection for high dimensional data
Aggarwal, C. C., & Yu, P. S. (2001) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/375663.375668 · Cited by 1,066
The average distances in random graphs with given expected degrees
Chung, F., & Lü, L. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.252631999 · Cited by 891
Aggarwal, C. C. (2011) · Springer eBooks · doi:10.1007/978-1-4419-8462-3 · Cited by 785
Yan, X., & Han, J. (2003) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/956750.956784 · Cited by 646
oddball: Spotting Anomalies in Weighted Graphs
Akoglu, L., McGlohon, M., & Faloutsos, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13672-6_40 · Cited by 545
Self-citationNoble, C. C., & Cook, D. J. (2003) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/956750.956831 · Cited by 483
Outlier detection for high dimensional data
Aggarwal, C. C., & Yu, P. S. (2001) · ACM SIGMOD Record · doi:10.1145/376284.375668 · Cited by 464
Aiding the detection of fake accounts in large scale social online services
Cao, Q., Sirivianos, M., Yang, X., & Pregueiro, T. (2012) · Cited by 449
Structure and Evolution of Online Social Networks
Kumar, R., Novak, J., & Tomkins, A. (2010) · Springer eBooks · doi:10.1007/978-1-4419-6515-8_13 · Cited by 438
Cook, D. J., & Holder, L. B. (2006) · Wiley-Interscience eBooks · Cited by 396
Netprobe: a fast and scalable system for fraud detection in online auction networks
Pandit, S., Chau, D. H., Wang, S., & Faloutsos, C. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242600 · Cited by 382
Self-citationCopyCatch: stopping group attacks by spotting lockstep behavior in social networks
Beutel, A., Xu, W., Guruswami, V., Palow, C., & Faloutsos, C. (2013) · Proceedings of the 22nd international conference on World Wide Web · doi:10.1145/2488388.2488400 · Cited by 335
Self-citationNeighborhood Formation and Anomaly Detection in Bipartite Graphs
Sun, J., Qu, H., Chakrabarti, D., & Faloutsos, C. (2006) · Proceedings · doi:10.1109/icdm.2005.103 · Cited by 313
Self-citationAn Introduction to Social Network Data Analytics
Aggarwal, C. C. (2011) · Springer eBooks · doi:10.1007/978-1-4419-8462-3_1 · Cited by 312
Denser than the densest subgraph
Tsourakakis, C. E., Bonchi, F., Gionis, A., Gullo, F., & Tsiarli, M. A. (2013) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2487575.2487645 · Cited by 289
Dense Subgraph Extraction with Application to Community Detection
Chen, J., & Saad, Y. (2011) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.271 · Cited by 270
On mining cross-graph quasi-cliques
Pei, J., Jiang, D., & Zhang, A. (2005) · doi:10.1145/1081870.1081898 · Cited by 249
Combining Collective Classification and Link Prediction
Bilgic, M., Namata, G. M. S., & Getoor, L. C. (2007) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw.2007.35 · Cited by 190
AutoPart: Parameter-Free Graph Partitioning and Outlier Detection
Chakrabarti, D. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30116-5_13 · Cited by 189
Social spammer detection in microblogging
Hu, X., Tang, J., Zhang, Y., & Liu, H. (2013) · Cited by 168
Detecting graph-based spatial outliers
Shekhar, S., Lu, C., & Zhang, P. (2001) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/502512.502567 · Cited by 168
Mining Frequent Subgraph Patterns from Uncertain Graph Data
Zou, Z., Li, J., Gao, H., & Zhang, S. (2010) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.80 · Cited by 156
Detecting Fraudulent Personalities in Networks of Online Auctioneers
Chau, D. H., Pandit, S., & Faloutsos, C. (2006) · Lecture notes in computer science · doi:10.1007/11871637_14 · Cited by 153
Self-citationEigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs
Prakash, B. A., Sridharan, A., Seshadri, M., Sridhar Machiraju, B., & Faloutsos, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13672-6_42 · Cited by 141
Self-citationMining Behavior Graphs for “Backtrace” of Noncrashing Bugs
Liu, C., Yan, X., Yu, H., Han, J., & Yu, P. S. (2005) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.26 · Cited by 129
D-cores: measuring collaboration of directed graphs based on degeneracy
Giatsidis, C., Thilikos, D. M., & Vazirgiannis, M. (2012) · Knowledge and Information Systems · doi:10.1007/s10115-012-0539-0 · Cited by 106
Wang, X., & Davidson, I. A. K. (2010) · Proceedings · doi:10.1109/icdm.2010.119 · Cited by 87
Outlier detection using classifier instability
Tax, D. M. J., & Duin, R. P. W. (1998) · Lecture notes in computer science · doi:10.1007/bfb0033283 · Cited by 85
Inferring Strange Behavior from Connectivity Pattern in Social Networks
Jiang, M., Cui, P., Beutel, A., Faloutsos, C., & Yang, S. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-06608-0_11 · Cited by 82
Self-citationOutRank: A GRAPH-BASED OUTLIER DETECTION FRAMEWORK USING RANDOM WALK
Moonesinghe, H. D. K., & Tan, P. (2008) · International Journal of Artificial Intelligence Tools · doi:10.1142/s0218213008003753 · Cited by 76
Advances in Pattern Recognition
Amin, A., Freeman, H., Pudil, P., & Dori, D. (1998) · Lecture notes in computer science · doi:10.1007/bfb0033222 · Cited by 49
Detecting suspicious following behavior in multimillion-node social networks
Jiang, M., Cui, P., Beutel, A., Faloutsos, C., & Yang, S. (2014) · International World Wide Web Conference (WWW) · doi:10.1145/2567948.2577306 · Cited by 36
Self-citationSPOT 1.0: Scoring Suspicious Profiles on Twitter
Pérez, C., Lemercier, M., Birregah, B., & Corpel, A. (2011) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1109/asonam.2011.63 · Cited by 15
Cited by
Sorted by citations
Collective Opinion Spam Detection: Bridging Review Networks and Metadata
Rayana, S., & Akoglu, L. (2015) · Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2783258.2783370 · Cited by 604
Fraud detection: A systematic literature review of graph-based anomaly detection approaches
Pourhabibi, T., Ong, K., Kam, B., & Boo, Y. L. (2020) · Decision Support Systems · doi:10.1016/j.dss.2020.113303 · Cited by 518
Kumar, S., Hooi, B., Makhija, D., Kumar, M., Faloutsos, C., & Subrahmanian, V. S. (2018) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3159652.3159729 · Cited by 381
Self-citationFRAUDAR: Bounding Graph Fraud in the Face of Camouflage
Hooi, B., Song, H. A., Beutel, A., Shah, N., Shin, K., & Faloutsos, C. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939747 · Cited by 305
Self-citationVosoughi, S., Mohsenvand, M. ‘., & Roy, D. K. (2017) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3070644 · Cited by 202
Metadata
- Authors
- Jiang, M., Cui, P., Beutel, A., Faloutsos, C., & Yang, S.
- Affiliations
- Tsinghua University (CN)
- Carnegie Mellon University (US)
- Venue
- Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2014-08-24
- Pages
- 941-950
- OpenAlex
- W2101447063
- Cited by
- 151
- References
- 41
- Citations by year
- 2026: 2 · 2025: 3 · 2024: 7 · 2023: 5 · 2022: 6 · 2021: 15 · 2020: 20 · 2019: 12 · 2018: 19 · 2017: 32 · 2016: 16 · 2015: 14
- FWCI
- 19.02
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (publishedVersion)
- Funders
- Division of Computer and Network Systems (CNS-1314632)
- Army Research Office (W911NF-11-C-0088)
- U.S. Army Research Laboratory (W911NF-09-2-0053)
- Media Development Authority - Singapore (WBS:R-252-300-001-490)
- National Natural Science Foundation of China (61210008, 61303075, 61370022)
- Defense Advanced Research Projects Agency (W911NF-11-C-0088)
- Ministry of Science and Technology of the People's Republic of China (2013DFG12870, 2011CB302206)
- Topics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Computer Science › Information Systems › Spam and Phishing Detection
- Physical Sciences › Computer Science › Artificial Intelligence › Anomaly Detection Techniques and Applications
- Keywords
- directed graphs, synchronicity, normality, connectivity patterns, bot detection, fake followers, parameter-free algorithms, Weibo, large-scale graphs
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
