Method To Prevent Re-Identification Of Individual Nodes By Combining K-Degree Anonymity With L-Diversity

M Vamsi Krishna, K V.V.S.Narayana Murthy


A range of privacy models as well as anonymization algorithms have been developed. In tabular micro data some of the no responsive attributes called quasi identifiers can be used to reidentify individuals and their sensitive attributes. When publishing social network data graph structures are also published with equivalent social relationships. As a result it may be oppressed as a new means to compromise privacy. ITH the rapid growth of social networks such as Face book and LinkedIn more and more researchers establish that it is a great opportunity to get hold of useful information from these social network data such as the user behavior, community growth, disease spreading etc. Though it is supreme that published social network data should not disclose private information of individuals. Therefore how to protect individual’s privacy and at the same time protect the utility of social network data becomes a challenging topic. In this paper we believe a graph model where each highest point in the graph is associated with a sensitive label.


Social networks, privacy, anonymous.


L. Backstrom, C. Dwork, and J.M. Kleinberg, “Wherefore Art Thou r3579x?: Anonymized Social Networks, Hidden Patterns, and Structural Steganography,” Proc. Int’l Conf. World Wide Web (WWW), pp. 181-190, 2007.

A.-L. Baraba´si and R. Albert, “Emergence of Scaling in Random Networks,” Science, vol. 286, pp. 509-512, 1999.

S. Bhagat, G. Cormode, B. Krishnamurthy, and D. Srivastava, “Class-Based Graph Anonymization for Social Network Data,” Proc. VLDB Endowment, vol. 2, pp. 766-777, 2009.

A. Campan and T.M. Truta, “A Clustering Approach for Data and Structural Anonymity in Social Networks,” Proc. Second ACM SIGKDD Int’l Workshop Privacy, Security, and Trust in KDD (PinKDD ’08), 2008.

A. Campan, T.M. Truta, and N. Cooper, “P-Sensitive K-Anonymity with Generalization Constraints,” Trans. Data Privacy, vol. 2, pp. 65-89, 2010.

J. Cheng, A.W.-c. Fu, and J. Liu, “K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks,” Proc. Int’l Conf. Management of Data, pp. 459-470, 2010.

G. Cormode, D. Srivastava, T. Yu, and Q. Zhang, “Anonymizing Bipartite Graph Data Using Safe Groupings,” Proc. VLDB Endowment, vol. 1, pp. 833-844, 2008.

S. Das, O. Egecioglu, and A.E. Abbadi, “Privacy Preserving in Weighted Social Network,” Proc. Int’l Conf. Data Eng. (ICDE ’10), pp. 904-907, 2010.

W. Eberle and L. Holder, “Discovering Structural Anomalies in Graph-Based Data,” Proc. IEEE Seventh Int’l Conf. Data Mining Workshops (ICDM ’07), pp. 393-398, 2007.

K.B. Frikken and P. Golle, “Private Social Network Analysis: How to Assemble Pieces of a Graph Privately,” Proc. Fifth ACM Workshop Privacy in Electronic Soc. (WPES ’06), pp. 89-98, 2006.

S.R. Ganta, S. Kasiviswanathan, and A. Smith, “CompositionAttacks and Auxiliary Information in Data Privacy,” Proc. ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining, pp. 265- 273, 2008.

G. Ghinita, P. Karras, P. Kalnis, and N. Mamoulis, “Fast Data Anonymization with Low Information Loss,” Proc. 33rd Int’l Conf. Very Large Data Bases (VLDB ’07), pp. 758-769, 2007.

G. Ghinita, P. Karras, P. Kalnis, and N. Mamoulis, “A Framework for Efficient Data Anonymization Under Privacy and Accuracy Constraints,” ACM Trans. Database Systems, vol. 34, pp. 9:1-9:47, July 2009.

J. Han, Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, Inc., 2005.

M. Hay, G. Miklau, D. Jensen, D. Towsley, and P. Weis, “Resisting Structural Re-Identification in Anonymized Social Networks,” Proc. VLDB Endowment, vol. 1, pp. 102-114, 2008.

E.M. Knorr, R.T. Ng, and V. Tucakov, “Distance-Based Outliers: Algorithms and applications,”The VLDB J., vol.8,pp.237-253, Feb.2000.



  • There are currently no refbacks.

Copyright © 2013, All rights reserved.|

Creative Commons License
International Journal of Science Engineering and Advance Technology is licensed under a Creative Commons Attribution 3.0 Unported License.Based on a work at IJSEat , Permissions beyond the scope of this license may be available at