Protecting Sensitive Labels in Social Network Data

Abstract

Privacy is one of the major concerns when publishing or sharing social network data for social science research and business analysis. Recently, researchers have developed privacy models similar to k-anonymity to prevent node re-identification through structure information. However, even when these privacy models are enforced, an attacker may still be able to infer one's private information if a group of nodes largely share the same sensitive labels (i. e. , attributes). In other words, the label-node relationship is not well protected by pure structure anonymization methods. Furthermore, existing approaches, which rely on edge editing or node clustering, may significantly alter key graph properties. In this paper, we define a k-degree-l-diversity anonymity model that considers the protection of structural information as well as sensitive labels of individuals. We had seen a novel anonymization methodology based on adding noise nodes. We implemented that algorithm by adding noise nodes into the original graph with the consideration of introducing the least distortion to graph properties. We here propose novel approach to reduce number of noise node so that decrease the complexity within networks. We implement this protection model in a distributed environment, where different publishers publish their data independently Most importantly, we provide a rigorous analysis of the theoretical bounds on the number of noise nodes added and their impacts on an important graph property. We conduct extensive experiments to evaluate the effectiveness of the proposed technique.

References

• K. Le-Fevre, D. DeWitt, R. Ramakrishnan. Mondrian multidimensional k-anonymity In International Conference on Data Engineering 2006.
• M. Hay, G. Miklau, D. Jensen, D. Towsley, P. Weis, "Resisting Structural re-Identification in the Anonymized Social Networks," Proc. VLDB Endowment, vol. 1, pp. 102-114, 2008.
• B. Zhou and J. Pei, "Preserving Privacy in Social Networks Against Neighborhood Attacks," Proc. IEEE 24th Int'l Conf. Data Eng. (ICDE '08), pp. 506-515, 2008. 08), 2008.
• Hay, Michael; Miklau, Gerome; Jensen, David; Weis, Philipp; and Srivastava, Siddharth, "Anonymizing Social Networks" (2007). Computer Science Department Faculty Publication Series paper 180.
• K. Le-Fevre, D. DeWitt, R. Ramakrishnan. Mondrian multidimensional k-anonymity In International Conference on Data Engineering 2006
• A. Meyerson and R. Williams. On the complexity of optimal k-anonymity in ACM Symposium on Principles of Database Systems 2004
• B. S. Hettich and C. Merz. UCI repository of machine learning databases, 1998
• P. Samarat,- Protecting respondent's privacy in micro data release IEEE Transactions on Knowledge and Data Engineering, 13, 2001.
• L. sweeney, achieving k-anonymity privacy protection using generalization and suppression. International journal on uncertainty, Fuzziness and knowledge based system, 2002.
• A. -L. Baraba´ si and R. Albert, "Emergence of Scaling in Random Networks," Science, vol. 286, pp. 509-512, 1999.
• Bruce Kapron, GautamSrivastava, S. Venkatesh -IEEE international Conference 2011, Social Network anonymization via Edge Addition.
• Benjamin C. M. Fung, Ke Wang, and Philip S. Yu, Fellow, IEEE Data Engineering 2007 AnonymizingClassication Data for Privacy Preservation.
• Ping Xiong, Tianqing Zhu management of e-Commerce and e Government (ICMeCG), 2012 Conference on An AnonymizationMethod Based on Tradeoff between Utility and Privacy for Data Publishing.
• Gionis A. ; Tassa, T, IEEE Knowledge and data engineering 2009. K anonymization with minimal loss of information.
• Shapiro, S S. (SysCon) IEEE Knowledge and data engineering 2012, Situating Anonymization within a Privacy risk model.

Index Terms

Keywords