{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T18:30:35Z","timestamp":1773513035060,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642195709","type":"print"},{"value":"9783642195716","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19571-6_26","type":"book-chapter","created":{"date-parts":[[2011,3,22]],"date-time":"2011-03-22T12:04:42Z","timestamp":1300795482000},"page":"432-449","source":"Crossref","is-referenced-by-count":60,"title":["Towards Privacy for Social Networks: A Zero-Knowledge Based Definition of Privacy"],"prefix":"10.1007","author":[{"given":"Johannes","family":"Gehrke","sequence":"first","affiliation":[]},{"given":"Edward","family":"Lui","sequence":"additional","affiliation":[]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Backstrom, L., Dwork, C., Kleinberg, J.: Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In: WWW 2007: Proc. of the 16th International Conference on World Wide Web, pp. 181\u2013190 (2007)","DOI":"10.1145\/1242572.1242598"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Blum, A., Ligett, K., Roth, A.: A learning theory approach to non-interactive database privacy. In: STOC 2008: Proc. of the 40th Annual ACM Symposium on Theory of Computing, pp. 609\u2013618 (2008)","DOI":"10.1145\/1374376.1374464"},{"issue":"6","key":"26_CR3","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput.\u00a034(6), 1370\u20131379 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1-2","key":"26_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/1900000008","volume":"2","author":"B.C. Chen","year":"2009","unstructured":"Chen, B.C., Kifer, D., LeFevre, K., Machanavajjhala, A.: Privacy-preserving data publishing. Foundations and Trends in Databases\u00a02(1-2), 1\u2013167 (2009)","journal-title":"Foundations and Trends in Databases"},{"key":"26_CR5","first-page":"429","volume":"15","author":"T. Dalenius","year":"1977","unstructured":"Dalenius, T.: Towards a methodology for statistical disclosure control. Statistik Tidskrift\u00a015, 429\u2013444 (1977)","journal-title":"Statistik Tidskrift"},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1007\/978-3-642-00457-5_29","volume-title":"Theory of Cryptography","author":"C. Dwork","year":"2009","unstructured":"Dwork, C.: The differential privacy frontier. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 496\u2013502. Springer, Heidelberg (2009)"},{"key":"26_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11787006_1","volume-title":"Automata, Languages and Programming","author":"C. Dwork","year":"2006","unstructured":"Dwork, C.: Differential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04052, pp. 1\u201312. Springer, Heidelberg (2006)"},{"key":"26_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/11681878_14","volume-title":"Theory of Cryptography","author":"C. Dwork","year":"2006","unstructured":"Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol.\u00a03876, pp. 265\u2013284. Springer, Heidelberg (2006)"},{"key":"26_CR9","unstructured":"Dwork, C., Naor, M.: On the difficulties of disclosure prevention in statistical databases or the case for differential privacy (2008)"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Dwork, C., Rothblum, G., Vadhan, S.: Boosting and differential privacy. In: Proc. of the 51st Annual IEEE Symposium on Foundations of Computer Science (2010)","DOI":"10.1109\/FOCS.2010.12"},{"issue":"4","key":"26_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1749603.1749605","volume":"42","author":"B.C.M. Fung","year":"2010","unstructured":"Fung, B.C.M., Wang, K., Chen, R., Yu, P.S.: Privacy-preserving data publishing: A survey of recent developments. ACM Comput. Surv.\u00a042(4), 1\u201353 (2010)","journal-title":"ACM Comput. Surv."},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Gehrke, J., Lui, E., Pass, R.: Towards privacy for social networks: A zero-knowledge based definition of privacy (2011) (manuscript)","DOI":"10.1007\/978-3-642-19571-6_26"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. In: Proc. of the 29th annual ACM Symposium on Theory of Computing, pp. 406\u2013415 (1997)","DOI":"10.1145\/258533.258627"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: A sublinear bipartiteness tester for bounded degree graphs. In: Proc. of the 30th Annual ACM Symposium on Theory of Computing, pp. 289\u2013298 (1998)","DOI":"10.1145\/276698.276767"},{"issue":"4","key":"26_CR15","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1002\/rsa.20203","volume":"32","author":"O. Goldreich","year":"2008","unstructured":"Goldreich, O., Ron, D.: Approximating average parameters of graphs. Random Struct. Algorithms\u00a032(4), 473\u2013493 (2008)","journal-title":"Random Struct. Algorithms"},{"key":"26_CR16","doi-asserted-by":"crossref","first-page":"102","DOI":"10.14778\/1453856.1453873","volume":"1","author":"M. Hay","year":"2008","unstructured":"Hay, M., Miklau, G., Jensen, D., Towsley, D., Weis, P.: Resisting structural re-identification in anonymized social networks. Proc. VLDB Endow.\u00a01, 102\u2013114 (2008)","journal-title":"Proc. VLDB Endow."},{"key":"26_CR17","unstructured":"Jernigan, C., Mistree, B.: Gaydar (2009), \n                    \n                      http:\/\/www.telegraph.co.uk\/technology\/facebook\/6213590\/Gay-men-can-be-identified-by-their-Facebook-friends.html"},{"issue":"6","key":"26_CR18","doi-asserted-by":"publisher","first-page":"1441","DOI":"10.1137\/S0097539703436424","volume":"33","author":"T. Kaufman","year":"2004","unstructured":"Kaufman, T., Krivelevich, M., Ron, D.: Tight bounds for testing bipartiteness in general graphs. SIAM J. Comput.\u00a033(6), 1441\u20131483 (2004)","journal-title":"SIAM J. Comput."},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Kifer, D.: Attacks on privacy and definetti\u2019s theorem. In: SIGMOD Conference, pp. 127\u2013138 (2009)","DOI":"10.1145\/1559845.1559861"},{"key":"26_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/11422778_27","volume-title":"NETWORKING 2005. Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems","author":"V. Krishnamurthy","year":"2005","unstructured":"Krishnamurthy, V., Faloutsos, M., Chrobak, M., Lao, L., Cui, J.-H., Percus, A.G.: Reducing large internet topologies for faster simulations. In: Boutaba, R., Almeroth, K.C., Puigjaner, R., Shen, S., Black, J.P. (eds.) NETWORKING 2005. LNCS, vol.\u00a03462, pp. 328\u2013341. Springer, Heidelberg (2005)"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Faloutsos, C.: Sampling from large graphs. In: KDD 2006: Proc. of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 631\u2013636 (2006)","DOI":"10.1145\/1150402.1150479"},{"issue":"2","key":"26_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1497290.1497298","volume":"5","author":"S. Marko","year":"2009","unstructured":"Marko, S., Ron, D.: Approximating the distance to properties in bounded-degree and general sparse graphs. ACM Trans. Algorithms\u00a05(2), 1\u201328 (2009)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"26_CR23","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0378-8733(02)00039-4","volume":"25","author":"M.E.J. Newman","year":"2003","unstructured":"Newman, M.E.J.: Ego-centered networks and the ripple effect. Social Networks\u00a025(1), 83\u201395 (2003)","journal-title":"Social Networks"},{"issue":"2","key":"26_CR24","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/rsa.10013","volume":"20","author":"M. Parnas","year":"2002","unstructured":"Parnas, M., Ron, D.: Testing the diameter of graphs. Random Struct. Algorithms\u00a020(2), 165\u2013183 (2002)","journal-title":"Random Struct. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19571-6_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:25Z","timestamp":1606186105000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19571-6_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642195709","9783642195716"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19571-6_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}