The week's pick
Random Articles
Reseach Article
A Comparison of Clustering and Modification based Graph Anonymization Methods with Constraints
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 95 - Number 20 |
| Year of Publication: 2014 |
| Authors: David F. Nettleton, Vicenc Torra, Anton Dries |
10.5120/16712-6870
|
David F. Nettleton, Vicenc Torra, Anton Dries . A Comparison of Clustering and Modification based Graph Anonymization Methods with Constraints. International Journal of Computer Applications. 95, 20 ( June 2014), 31-38. DOI=10.5120/16712-6870
Abstract
In this paper a comparison is performed on two of the key methods for graph anonymization and their behavior is evaluated when constraints are incorporated into the anonymization process. The two methods tested are node clustering and node modification and are applied to online social network (OSN) graph datasets. The constraints implement user defined utility requirements for the community structure of the graph and major hub nodes. The methods are benchmarked using three real OSN datasets and different levels of k?anonymity. The results show that the constraints reduce the information loss while incurring an acceptable disclosure risk. Overall, it is found that the modification method with constraints gives the best results for information loss and risk of disclosure.
References
- Hay, M. , Miklau, G. , Jensen, D. , Towsley D. and Weis, P. 2008. Resisting structural re-identi?cation in anonymized social networks, Proc. of the VLDB Endowment (SESSION: Privacy and authentication) Vol. 1 , Issue 1, pages 102-114.
- Zhou, B. , Pei, J. 2008. Preserving Privacy in Social Networks against Neighborhood Attacks, IEEE 24th International Conference on Data Engineering (ICDE), 2008, pp. 506 - 515.
- Wondracek, G. , Holz, T. , Kirda, E. , Kruegel, C. 2010. A Practical Attack to De-Anonymize Social Network Users, Proc. of the 2010 IEEE Symp. on Security and Privacy, pp. 223-238.
- Backstrom, L. , Dwork, C. and Kleinberg, J. 2007. Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography, WWW '07, Proc. 16th Int. Conf. on WWW, pp. 181 - 190, ACM, NY, USA, 2007.
- Cheng, J. , Fu, A. W. C. and Liu, J. 2010. K?Isomorphism: Privacy Preserving Network Publication against Structural Attacks, Proc. ACM SIGMOD Int. Conf. on Mgt. of Data, pp. 459-470.
- Sweeney, L. 2002. k?anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems (IJUFKS). Vol. 10, Issue: 5(2002) pp. 557-570.
- De Capitani di Vimercati, S. , Foresti, S. , Livraga, G. and Samarati, P. 2012. Data Privacy: Definitions and Techniques, Int. J. of Uncert. , Fuzziness and Know. Based Sys. , Vol. 20, Iss. 6, Dec. 2012, p. 793.
- Zhou, B. , Pei, J. 2011. The k?anonymity and l?diversity approaches for privacy preservation in social networks against neighborhood Attacks, Know. and Inf. Sys. , July 2011, Vol. 28, Iss. 1, pp 47-77.
- Nettleton, D. F. , Sáez-Trumper, D. , Torra, V. 2011. A Comparison of Two Different Types of Online Social Network from a Data Privacy Perspective, Proc. MDAI 2011. LNAI, Vol. 6820, pp. 223-234.
- Hay, M. , Miklau, G. , Jensen, D. , Weis P. and Srivastava, S. 2007. Anonymizing Social Networks, SCIENCE Technical Report 07-19 (2007) pp. 107--3, Vol. 245.
- Skarkala, M. E. , Maragoudakis, M. , Gritzalis, S. , Mitrou, L. , Toivonen, H. , and Moen, P. 2012. Privacy Preservation by k?Anonymization of Weighted Social Networks, ASONAM, page 423-428. IEEE Computer Society.
- Nettleton, D. F. 2012. Information Loss Evaluation based on Fuzzy and Crisp Clustering of Graph Statistics. Proc. WCCI 2012, World Congress on Comp. Intelligence 2012, FUZZ-IEEE, pp. 1-8.
- Bonchi, F. , Gionis A. and Tassa, T. 2011. Identity Obfuscation in Graphs Through the Information Theoretic Lens, ICDE '11, Proceedings of the 2011 IEEE 27th Int. Conf. on Data Engineering, pp. 924-935, IEEE Computer Society Washington, DC, USA.
- Ying, X. and Wu, X. 2008. Randomizing Social Networks: a Spectrum Preserving Approach, In Proc. SIAM Int. Conf. on Data Mining (2008), pp. 739-750.
- Kleinberg, J. 1999. Authoratitive sources in a hyperlinked environment, Journal of the ACM, 46(5):604-632.
- Blondel, V. D. , Guillaume, J. L. , Lambiotte, R. , Lefebure, E. 2008. Fast unfolding of communities in large networks, in Journal of Statistical Mechanics: Theory and Experiment (10), 2008, pp. 1000.
- Nettleton, D. F. and Dries, A. 2013. Local Neighbourhood Sub-Graph Matching Method, European Patent application number: 13382308. 8.
- Bastian, M. , Heymann, S. and Jacomy, M. 2009. Gephi: An Open Source Software for Exploring and Manipulating Networks, in: Proc. 3rd. Int. Conf. on Weblogs and Social Media, 2009, pp. 361–362.
- Leskovec, J. , Kleinberg, J. , Faloutsos, C. 2007. Graph Evolution: Densification and Shrinking Diameters, ACM Transactions on Knowledge Discovery from Data (ACM TKDD), 1(1).
- Shetty, J. and Adibi, J. 2005. Discovering Important Nodes through Graph Entropy - The Case of Enron Email Database, KDD '2005, Chicago, Illinois.
- Leskovec, J. , Huttenlocher, D. and Kleinberg, J. 2010. Signed Networks in Social Media, CHI '10 Proc. 28th Int. Conf. on Human Factors in Computing Systems, pp. 1361-1370, ACM, NY, USA.
Index Terms
Keywords