{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:18:05Z","timestamp":1763468285910,"version":"3.37.3"},"reference-count":14,"publisher":"Proceedings of the National Academy of Sciences","issue":"4","license":[{"start":{"date-parts":[[2016,1,11]],"date-time":"2016-01-11T00:00:00Z","timestamp":1452470400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.pnas.org\/preview_site\/misc\/userlicense.xhtml"}],"funder":[{"DOI":"10.13039\/100000183","name":"DOD | Army Research Office","doi-asserted-by":"publisher","award":["W911NF-12-1-0509"],"award-info":[{"award-number":["W911NF-12-1-0509"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1101389"],"award-info":[{"award-number":["CCF 1101389"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2016,1,26]]},"abstract":"<jats:title>Significance<\/jats:title>\n          <jats:p>Motivated by tensions between data privacy for individual citizens, and societal priorities such as counterterrorism, we introduce a computational model that distinguishes between parties for whom privacy is explicitly protected, and those for whom it is not (the \u201ctargeted\u201d subpopulation). Within this framework, we provide provably privacy-preserving algorithms for targeted search in social networks. We validate the utility of our algorithms with extensive computational experiments on two large-scale social network datasets.<\/jats:p>","DOI":"10.1073\/pnas.1510612113","type":"journal-article","created":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T04:24:36Z","timestamp":1452572676000},"page":"913-918","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":22,"title":["Private algorithms for the protected in social network search"],"prefix":"10.1073","volume":"113","author":[{"given":"Michael","family":"Kearns","sequence":"first","affiliation":[{"name":"Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aaron","family":"Roth","sequence":"additional","affiliation":[{"name":"Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiwei Steven","family":"Wu","sequence":"additional","affiliation":[{"name":"Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grigory","family":"Yaroslavtsev","sequence":"additional","affiliation":[{"name":"Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"341","published-online":{"date-parts":[[2016,1,11]]},"reference":[{"key":"e_1_3_2_1_2","unstructured":"Greenwald G (June 6 2013) NSA collecting phone records of millions of Verizon customers daily. The Guardian . Available at www.theguardian.com\/world\/2013\/jun\/06\/nsa-phone-records-verizon-court-order."},{"key":"e_1_3_2_2_2","volume-title":"Bulk Collection of Signals Intelligence: Technical Options","author":"National Research Council","year":"2015","unstructured":"; National Research Council Bulk Collection of Signals Intelligence: Technical Options (The National Academies Press, Washington, DC, 2015)."},{"key":"e_1_3_2_3_2","unstructured":"J Allen (October 25 2014) U.S. nurse quarantined over Ebola calls treatment \u201cfrenzy of disorganization.\u201d Reuters . Available at www.reuters.com\/article\/health-ebola-usa-obama-idUSL6N0SK0IN20141026."},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","unstructured":"C Dwork F McSherry K Nissim A Smith Calibrating noise to sensitivity in private data analysis. Proceedings of Third Theory of Cryptography Conference (Springer New York) pp. 265\u2013284. (2006).","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.2307\/40041279"},{"key":"e_1_3_2_6_2","unstructured":"C Dwork FD McSherry Selective privacy guarantees. US Patent 7 818 335. (2010)."},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","unstructured":"X He A Machanavajjhala B Ding Blowfish privacy: Tuning privacy-utility trade-offs using policies. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (ACM New York) pp 1447\u20131458. (2014).","DOI":"10.1145\/2588555.2588581"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","unstructured":"M Hay C Li G Miklau D Jensen Accurate estimation of the degree distribution of private networks. Ninth IEEE International Conference on Data Mining (IEEE New York) pp 169\u2013178. (2009).","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"SP Kasiviswanathan K Nissim S Raskhodnikova A Smith Analyzing graphs with node differential privacy. Theory of Cryptography Conference (Springer New York) pp 457\u2013476. (2013).","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","unstructured":"J Blocki A Blum A Datta O Sheffet Differentially private data analysis of social networks via restricted sensitivity. Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (ACM New York) pp 87\u201396. (2013).","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","unstructured":"R Bassily A Groce J Katz A Smith Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. IEEE 54th Annual Symposium on Foundations of Computer Science (IEEE New York) pp 439\u2013448. (2013).","DOI":"10.1109\/FOCS.2013.54"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"Kearns M Pai M M Roth A Ullman J (2014) Mechanism design in large games: Incentives and privacy. Am Econ Rev 104(5):431\u2013435.","DOI":"10.1257\/aer.104.5.431"},{"key":"e_1_3_2_14_2","unstructured":"M Alaggan S Gambs A-M Kermarrec Heterogeneous differential privacy. arXiv:1504.06998. (2015)."}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.pnas.org\/syndication\/doi\/10.1073\/pnas.1510612113","content-type":"unspecified","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.1510612113","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,13]],"date-time":"2022-04-13T04:30:19Z","timestamp":1649824219000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.1510612113"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,11]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,1,26]]}},"alternative-id":["10.1073\/pnas.1510612113"],"URL":"https:\/\/doi.org\/10.1073\/pnas.1510612113","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"type":"print","value":"0027-8424"},{"type":"electronic","value":"1091-6490"}],"subject":[],"published":{"date-parts":[[2016,1,11]]},"assertion":[{"value":"2016-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}