{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T15:54:33Z","timestamp":1774194873062,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T00:00:00Z","timestamp":1461196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006754","name":"US Army Research Laboratory","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100013986","name":"UK Government","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100013986","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Kennesaw State University College of Science and Mathematics Interdisciplinary Research Opportunities (IDROP) Program"},{"name":"UK Ministry of Defence","award":["W911NF-06-3-0001"],"award-info":[{"award-number":["W911NF-06-3-0001"]}]},{"name":"U.S. Government"},{"name":"National Science and Technology Support Program of China","award":["2014BAH24F01"],"award-info":[{"award-number":["2014BAH24F01"]}]},{"name":"UK Ministry of Defense"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2016,5,6]]},"abstract":"<jats:p>\n                    When people utilize social applications and services, their privacy suffers a potential serious threat. In this article, we present a novel, robust, and effective de-anonymization attack to mobility trace data and social data. First, we design a Unified Similarity (US) measurement, which takes account of local and global structural characteristics of data, information obtained from auxiliary data, and knowledge inherited from ongoing de-anonymization results. By analyzing the measurement on real datasets, we find that some data can potentially be de-anonymized accurately and the other can be de-anonymized in a coarse granularity. Utilizing this property, we present a US-based De-Anonymization (DA) framework, which iteratively de-anonymizes data with accuracy guarantee. Then, to de-anonymize large-scale data without knowledge of the overlap size between the anonymized data and the auxiliary data, we generalize DA to an Adaptive De-Anonymization (ADA) framework. By smartly working on two\n                    <jats:italic toggle=\"yes\">core matching subgraphs<\/jats:italic>\n                    , ADA achieves high de-anonymization accuracy and reduces computational overhead. Finally, we examine the presented de-anonymization attack on three well-known mobility traces: St Andrews, Infocom06, and Smallblue, and three social datasets: ArnetMiner, Google+, and Facebook. The experimental results demonstrate that the presented de-anonymization framework is very effective and robust to noise.\n                  <\/jats:p>\n                  <jats:p>The source code and employed datasets are now publicly available at SecGraph [2015].<\/jats:p>","DOI":"10.1145\/2894760","type":"journal-article","created":{"date-parts":[[2016,4,22]],"date-time":"2016-04-22T09:53:06Z","timestamp":1461318786000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["General Graph Data De-Anonymization"],"prefix":"10.1145","volume":"18","author":[{"given":"Shouling","family":"Ji","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}]},{"given":"Weiqing","family":"Li","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}]},{"given":"Mudhakar","family":"Srivatsa","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, NY, USA"}]},{"given":"Jing Selena","family":"He","sequence":"additional","affiliation":[{"name":"Kennesaw State University, GA, USA"}]},{"given":"Raheem","family":"Beyah","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}]}],"member":"320","published-online":{"date-parts":[[2016,4,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","unstructured":"L. Alvisi A. Clement A. Epasto S. Lattanzi and A. Panconesi. 2013. SoK: The evolution of Sybil defense via social networks. In S&P. 10.1109\/SP.2013.33","DOI":"10.1109\/SP.2013.33"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","unstructured":"L. Backstrom C. Dwork and J. Kleinberg. 2007. Wherefore art thou R3579X? Anonymized social networks hidden patterns and structural steganography. In WWW. 10.1145\/1242572.1242598","DOI":"10.1145\/1242572.1242598"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(88)90004-2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1121\/1.1906679"},{"key":"e_1_2_1_5_1","unstructured":"G. Bigwood D. Rehunathan M. Bateman T. Henderson and S. Bhatti. 2011. CRAWDAD dataset st_andrews\/sassy. Retrieved from http:\/crawdad.cs.dartmouth.edu\/st_andrews\/sassy."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2013.865686"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30551-4_18"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"A. Campan and T. M. Truta. 2008. A clustering approach for data and structural anonymity in social networks. In PinKDD.","DOI":"10.1007\/978-3-642-01718-6_4"},{"key":"e_1_2_1_9_1","unstructured":"Centrality. 2015. Centrality - Wikipedia the free encyclopedia. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Centrality."},{"key":"e_1_2_1_10_1","unstructured":"CRAWDAD. 2014. Retrieved from http:\/\/crawdad.cs.dartmouth.edu\/."},{"key":"e_1_2_1_11_1","unstructured":"M. Egele C. Kruegel E. Kirda and G. Vigna. 2011. PiOS: Detecting privacy leaks in iOS applications. NDSS (2011)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(78)90021-7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"M. Garg. 2009. Axiomatic foundations of centrality in networks. Social Sci. Res. Netw. (2009) 1--37.","DOI":"10.2139\/ssrn.1372441"},{"key":"e_1_2_1_14_1","unstructured":"N. Z. Gong A. Talwalkar L. Mackey L. Huang E. C. R. Shin E. Stefanov E. Shi and D. Song. 2012a. Jointly predicting links and inferring attributes using a social-attribute network (SAN). In SNA-KDD."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","unstructured":"N. Z. Gong W. Xu L. Huang P. Mittal E. Stefanov V. Sekar and D. Song. 2012b. Evolution of social-attribute networks: Measurements modeling and implications using Google+. In IMC. 10.1145\/2398776.2398792","DOI":"10.1145\/2398776.2398792"},{"key":"e_1_2_1_16_1","unstructured":"R. Hanneman and M. Riddle. 2005. Introduction to Social Network Methods: Table of Contents. Retrieved from http:\/\/faculty.ucr.edu\/&sim;hanneman\/nettext\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","unstructured":"M. Hay G. Miklau D. Jensen D. Towsley and P. Weis. 2008. Resisting structural re-identification in anonymized social networks. In VLDB. 10.14778\/1453856.1453873","DOI":"10.14778\/1453856.1453873"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","unstructured":"P. Hornyack S. Han J. Jung S. Schechter and D. Wetherall. 2011. These aren\u2019t the droids you\u2019re looking for: Retrofitting android to protect data from imperious applications. In CCS. 10.1145\/2046707.2046780","DOI":"10.1145\/2046707.2046780"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","unstructured":"S. Ji W. Li P. Mittal X. Hu and R. Beyah. 2014. Structural data de-anonymization: Quantification practice and implications. In CCS. 10.1145\/2660267.2660278","DOI":"10.1145\/2660267.2660278"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"S. Ji W. Li P. Mittal X. Hu and R. Beyah. 2015a. On your social network de-anonymizablity: Quantification and large scale evaluation with seed knowledge. In NDSS.","DOI":"10.14722\/ndss.2015.23096"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","unstructured":"S. Ji W. Li P. Mittal X. Hu and R. Beyah. 2015b. SecGraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization. In USENIX Security.","DOI":"10.5555\/2831143.2831163"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"J. Kruskal and M. Wish. 1978. Multidimensional Scaling. Sage Publications.","DOI":"10.4135\/9781412985130"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","unstructured":"K. Liu and E. Terzi. 2008. Towards identity anonymization on graphs. SIGMOD (2008). 10.1145\/1376616.1376629","DOI":"10.1145\/1376616.1376629"},{"key":"e_1_2_1_24_1","unstructured":"J. McAuley and J. Leskovec. 2012. Learning to discover social circles in ego networks. In NIPS."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","unstructured":"A. Narayanan and V. Shmatikov. 2008. Robust de-anonymization of large sparse datasets (de-anonymizing the Netflix prize dataset). In S&P. 10.1109\/SP.2008.33","DOI":"10.1109\/SP.2008.33"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","unstructured":"A. Narayanan and V. Shmatikov. 2009. De-anonymizing social networks. In S&P. 10.1109\/SP.2009.22","DOI":"10.1109\/SP.2009.22"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1809753"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","unstructured":"S. Nilizadeh A. Kapadia and Y.-Y. Ahn. 2014. Community-enhanced de-anonymization of online social networks. In CCS. 10.1145\/2660267.2660324","DOI":"10.1145\/2660267.2660324"},{"key":"e_1_2_1_29_1","volume-title":"Closeness centrality in networks with disconnected components &verbar","author":"Opsahl T.","year":"2010","unstructured":"T. Opsahl. 2010. Closeness centrality in networks with disconnected components &verbar; Tore Opsahl. Retrieved from http:\/\/toreopsahl.com\/2010\/03\/20\/closeness-centrality-in-networks-with-disconnected-components\/."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2010.03.006"},{"key":"e_1_2_1_31_1","unstructured":"Y. Rochat. 2009. Closeness centrality extended to unconnected graphs: The harmonic centrality index. In ASNA. 1--14."},{"key":"e_1_2_1_32_1","unstructured":"J. Scott R. Gass J. Crowcroft P. Hui C. Diot and A. Chaintreau. 2009. CRAWDAD dataset cambridge\/haggle. Retrieved from http:\/\/crawdad.cs.dartmouth.edu\/cambridge\/haggle."},{"key":"e_1_2_1_33_1","unstructured":"SecGraph. 2015. Retrieved from http:\/\/www.ece.gatech.edu\/cap\/secgraph\/."},{"key":"e_1_2_1_34_1","unstructured":"Similarity. 2015. Similarity (network science) - Wikipedia the free encyclopedia. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Similarity\\_(network_science)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","unstructured":"K. Singh S. Bhola and W. Lee. 2009. xBook: Redesigning privacy control in social networking platforms. In USENIX.","DOI":"10.5555\/1855768.1855784"},{"key":"e_1_2_1_36_1","unstructured":"Smallblue. 2009. SmallBlue Research Projects. Retrieved from http:\/\/domino.research.ibm.com\/comm\/research_projects.nsf\/pages\/smallblue.index.html."},{"key":"e_1_2_1_37_1","unstructured":"SNAP. 2014. Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","unstructured":"M. Srivatsa and M. Hicks. 2012. Deanonymizing mobility traces: Using social networks as a side-channel. In CCS. 10.1145\/2382196.2382262","DOI":"10.1145\/2382196.2382262"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","unstructured":"J. Tang J. Zhang L. Yao J. Li L. Zhang and Z. Su. 2008. ArnetMiner: Extraction and mining of academic social networks. In KDD. 10.1145\/1401890.1402008","DOI":"10.1145\/1401890.1402008"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","unstructured":"B. Viswanath A. N. Mislove M. Cha and K. P. Gummadi. 2009. On the evolution of user interaction in facebook. In WOSN. 10.1145\/1592665.1592675","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","unstructured":"H. Yu P. B. Gibbons M. Kaminsky and F. Xiao. 2008a. SybilLimit: A near-optimal social network defense against Sybil attacks. In S&P. 10.1109\/SP.2008.13","DOI":"10.1109\/SP.2008.13"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.923723"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","unstructured":"H. Yu C. Shi M. Kaminsky P. B. Gibbons and F. Xiao. 2009. DSybil: Optimal Sybil-resistance for recommendation systems. In S&P. 10.1109\/SP.2009.26","DOI":"10.1109\/SP.2009.26"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","unstructured":"E. Zheleva and L. Getoor. 2007. Preserving the privacy of sensitive relationships in graph data. In PinKDD.","DOI":"10.5555\/1793474.1793485"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","unstructured":"Y. Zhou H. Cheng and J. X. Yu. 2009. Graph clustering based on structural\/attribute similarities. In VLDB. 10.14778\/1687627.1687709","DOI":"10.14778\/1687627.1687709"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2894760","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2894760","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2894760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:16:22Z","timestamp":1763457382000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2894760"}},"subtitle":["From Mobility Traces to Social Networks"],"short-title":[],"issued":{"date-parts":[[2016,4,21]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,5,6]]}},"alternative-id":["10.1145\/2894760"],"URL":"https:\/\/doi.org\/10.1145\/2894760","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"value":"1094-9224","type":"print"},{"value":"1557-7406","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,21]]},"assertion":[{"value":"2015-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}