{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T17:45:45Z","timestamp":1772905545323,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>The recent rise in popularity of social networks, such as Facebook and MySpace, has created large quantities of data about interactions within these networks. Such data contains many private details about individuals so anonymization is required prior to attempts to make the data more widely available for scientific research. Prior work has considered simple graph data to be anonymized by removing all non-graph information and adding or deleting some edges. Since social network data is richer in details about the users and their interactions, loss of details due to anonymization limits the possibility for analysis. We present a new set of techniques for anonymizing social network data based on grouping the entities into classes, and masking the mapping between entities and the nodes that represent them in the anonymized graph. Our techniques allow queries over the rich data to be evaluated with high accuracy while guaranteeing resilience to certain types of attack. To prevent inference of interactions, we rely on a critical \"safety condition\" when forming these classes. We demonstrate utility via empirical data from social networking settings. We give examples of complex queries that may be posed and show that they can be answered over the anonymized data efficiently and accurately.<\/jats:p>","DOI":"10.14778\/1687627.1687714","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"766-777","source":"Crossref","is-referenced-by-count":126,"title":["Class-based graph anonymization for social network data"],"prefix":"10.14778","volume":"2","author":[{"given":"Smriti","family":"Bhagat","sequence":"first","affiliation":[{"name":"Rutgers University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs--Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balachander","family":"Krishnamurthy","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs--Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs--Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/76894.76895"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242598"},{"key":"e_1_2_1_3_1","volume-title":"Int. Conf. on Weblogs and Social Media","author":"Bhagat S.","year":"2007","unstructured":"S. Bhagat , G. Cormode , S. Muthukrishnan , I. Rozenbaum , and H. Xue . No blog is an island analyzing connections across information networks . In Int. Conf. on Weblogs and Social Media , 2007 . S. Bhagat, G. Cormode, S. Muthukrishnan, I. Rozenbaum, and H. Xue. No blog is an island analyzing connections across information networks. In Int. Conf. on Weblogs and Social Media, 2007."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401904"},{"key":"e_1_2_1_5_1","volume-title":"PinKDD","author":"Campan A.","year":"2008","unstructured":"A. Campan and T. M. Truta . A clustering approach for data and structural anonymity in social networks . In PinKDD , 2008 . A. Campan and T. M. Truta. A clustering approach for data and structural anonymity in social networks. In PinKDD, 2008."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453947"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1162\/qjec.2006.121.2.673"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453873"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458082.1458123"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1397735.1397744"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367856"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376629"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367858"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247554"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.971193"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218488502001648"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150499"},{"key":"e_1_2_1_19_1","volume-title":"VLDB","author":"Wong R. C.-W.","year":"2007","unstructured":"R. C.-W. Wong , A. W.-C. Fu , K. Wang , and J. Pei . Minimality attack in privacy preserving data publishing . In VLDB , 2007 . R. C.-W. Wong, A. W.-C. Fu, K. Wang, and J. Pei. Minimality attack in privacy preserving data publishing. In VLDB, 2007."},{"key":"e_1_2_1_20_1","volume-title":"VLDB","author":"Xiao X.","year":"2006","unstructured":"X. Xiao and Y. Tao . Anatomy: Simple and effective privacy preservation . In VLDB , 2006 . X. Xiao and Y. Tao. Anatomy: Simple and effective privacy preservation. In VLDB, 2006."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367857"},{"key":"e_1_2_1_22_1","volume-title":"PinKDD","author":"Zheleva E.","year":"2007","unstructured":"E. Zheleva and L. Getoor . Preserving the privacy of sensitive relationships in graph data . In PinKDD , 2007 . E. Zheleva and L. Getoor. Preserving the privacy of sensitive relationships in graph data. In PinKDD, 2007."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497459"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687714","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:31:51Z","timestamp":1672227111000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687714"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687714","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}