Sampling and Merging for Graph Anonymization

详细信息    查看全文

• 关键词：Degree sequence ; Graph anonymization ; Graph sampling ; Network privacy ; k ; anonymity
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9880
• 期：1
• 页码：250-260
• 全文大小：430 KB
• 参考文献：1.Adamic, L.A., Glance, N.: The political blogosphere and the 2004 US election. In: Proceedings of the WWW-2005 Workshop on the Weblogging Ecosystem (2005)
  2.Barabasi, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)MathSciNet CrossRef MATH
  3.Backstrom, L., Dwork, C., Kleinberg, J.: Where art thou R3579X? Anonymized social networks, hidden patterns, and structural steganography. In: Proceedings of 16th International World Wide Web Conference (2007)
  4.Campan, A., Truta, T.M.: A clustering approach for data and structural anonymity in social networks. In: Proceedings of the 2nd ACM SIGKDD International Workshop on Privacy, Security, and Trust in KDD (PinKDD 2008), in conjunction with KDD 2008, Las Vegas, Nevada, USA (2008)
  5.Campan, A., Truta, T.M.: Data and structural k-anonymity in social networks. In: Bonchi, F., Ferrari, E., Jiang, W., Malin, B. (eds.) PinKDD 2008. LNCS, vol. 5456, pp. 33–54. Springer, Heidelberg (2009)CrossRef
  6.Chester, S., Kapron, B.M., Ramesh, G., Srivastava, G., Thomo, A., Venkatesh, S.: Why Waldo befriended the dummy? k-Anonymization of social networks with pseudo-nodes. Soc. Netw. Anal. Min. 3(3), 381–399 (2013)
  7.Chester, S., Kapron, B., Srivastava, G., Venkatesh, S.: Complexity of social network anonymization. Soc. Netw. Anal. Min. 3(2), 151–166 (2013)CrossRef
  8.Domingo-Ferrer, J., Mateo-Sanz, J.M.: Practical data-oriented microaggregation for statistical disclosure control. IEEE Trans. Knowl. Data Eng. 14(1), 189–201 (2002)CrossRef
  9.Domingo-Ferrer, J., Torra, V.: Ordinal, continuous and heterogeneous k-anonymity through microaggregation. Data Min. Knowl. Discov. 11(2), 195–212 (2005)MathSciNet CrossRef
  10.Freeman, L.C.: Centrality in social networks: conceptual clarification. Soc. Netw. 1(3), 215–239 (1979)CrossRef
  11.Hay, M., Miklau, G., Jensen, D., Towsley, D.: Resisting structural identification in anonymized social networks. In: Proceedings of the 34th International Conference on Very Large Databases (VLDB 2008). ACM (2008)
  12.Hansen, S.L., Mukherjee, S.: A polynomial algorithm for optimal univariate microaggregation. IEEE Trans. Knowl. Data Eng. 15(4), 1043–1044 (2003)CrossRef
  13.Krebs, V.: (unpublished). http://​www.​orgnet.​com/​
  14.Krishnamurthy, V., Faloutsos, M., Chrobak, M., Cui, J., Lao, L., Percus, A.: Sampling large internet topologies for simulation purposes. Comput. Netw. 51(15), 4284–4302 (2007)CrossRef
  15.Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 93–106 (2008)
  16.Nettleton, D.F., Dries, A.: Local neighbourhood sub-graph matching method, European Patent application number: 13382308.8 (Priority 30/7/2013). PCT application number: PCT/ES2014/065505 (Priority 18 July 2014)
  17.Nettleton, D.F., Salas, J.: A data driven anonymization system for information rich online social network graphs. Expert Syst. Appl. 55, 87–105 (2016)CrossRef
  18.Newman, M.E.J.: Finding community structure in networks using the eigenvectors of matrices. Preprint Physics/0605087 (2006)
  19.Samarati, P.: Protecting respondents identities in microdata release. IEEE Trans. Knowl. Data Eng. 13(6), 1010–1027 (2001)CrossRef
  20.Salas, J., Torra, V.: Graphic sequences, distances and k-degree anonymity. Disc. Appl. Math. 188, 25–31 (2015)MathSciNet CrossRef MATH
  21.Salas, J., Torra, V.: Improving the characterization of P-stability for applications in network privacy. Disc. Appl. Math. 206, 109–114 (2016)MathSciNet CrossRef MATH
  22.Stokes, K., Torra, V.: Reidentification and k-anonymity: a model for disclosure risk in graphs. Soft Comput. 16(10), 1657–1670 (2012)CrossRef MATH
  23.Sweeney, L.: k-anonymity: a model for protecting privacy. Int. J. Uncertainty Fuzziness Knowl.-Based Syst. 10(5), 557–570 (2002)MathSciNet CrossRef MATH
  24.Truta, T.M., Campan, A., Ralescu, A.L.: Preservation of structural properties in anonymized social networks. In: CollaborateCom, pp. 619–627 (2012)
  25.Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)CrossRef
  26.Zachary, W.W.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33(4), 452–473 (1977)CrossRef
  27.Zheleva, E., Getoor, L.: Preserving the privacy of sensitive relationships in graph data. In: Bonchi, F., Malin, B., Saygın, Y. (eds.) PInKDD 2007. LNCS, vol. 4890, pp. 153–171. Springer, Heidelberg (2008)CrossRef
  28.Zhou, B., Pei, J.: Preserving privacy in social networks against neighborhood attacks. In: ICDE (2008)
  29.Zhou, B., Pei, J., Luk, W.S.: A brief survey on anonymization techniques for privacy preserving publishing of social network data. ACM SIGKDD Explor. Newsl. 10(2), 12–22 (2008)CrossRef
  
• 作者单位：Julián Salas (17)
  
  17. Department of Computer Engineering and Mathematics, Universitat Rovira i Virgili, Tarragona, Spain
  
• 丛书名：Modeling Decisions for Artificial Intelligence
• ISBN：978-3-319-45656-0
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9880

文摘

We propose a method for network anonymization that consists on sampling a subset of vertices and merging its neighborhoods in the network. In such a way, by publishing the merged graph of the network together with the sampled vertices and their locally anonymized neighborhoods, we obtain a complete anonymized picture of the network. We prove that the anonymization of the merged graph incurs in lower information loss, hence, it has more utility than the direct anonymization of the graph. It also yields an improvement on the quality of the anonymization of the local neighbors of a given subset of vertices.