An Effective Method for Utility Preserving Social Network Graph Anonymization Based on Mathematical Modeling


School of Engineering, Damghan University, Damghan, Iran


In recent years, privacy concerns about social network graph data publishing has increased due to the widespread use of such data for research purposes. This paper addresses the problem of identity disclosure risk of a node assuming that the adversary identifies one of its immediate neighbors in the published data. The related anonymity level of a graph is formulated and a mathematical model is proposed to solve the problem. The application of the method on a number of synthetic and real-world datasets confirms that the method is general and can be used in different contexts to produce superior results in terms of the utility of the anonymized graph.


1.     Asadi Saeed Abad, F. and Hamidi, H., "An Architecture for Security and Protection of Big Data", International Journal of Engineering, Vol. 30, No. 10, (2017), 1479-1486.

2.     Hemati, H., Ghasemzadeh, M. and Meinel, C., "A Hybrid Machine Learning Method for Intrusion Detection", International Journal of Engineering, Transactions C: Aspects, Vol. 29, No. 9, (2016), 1242-1246. 

3.     Sharma, P. and Kaur, P. D., "Effectiveness of web-based social sensing in health information dissemination-A review", Telematics and Informatics, Vol. 34, No. 1, (2017), 194–219.

4.     Feder, T., Nabar, S. U. and Terzi, E., "Anonymizing graphs",CoRR, abs/0810.5578, (2008).

5.     Casas-Roma, J., Herrera-Joancomartí, J. and Torra, V., "k-Degree anonymity and edge selection: improving data utility in large networks", Knowledge and Information Systems, Vol. 50, No. 2, (2017), 447–474.

6.     Sweeney, L., "k-anonymity: A model for protecting privacy", International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, Vol. 10, No. 5, (2002), 557–570.

7.     Mortazavi, R. and Jalili, S., "Enhancing aggregation phase of microaggregation methods for interval disclosure risk minimization", Data Mining and Knowledge Discovery, Vol. 30, No. 3, (2016), 605–639.

8.     Salari, M., Jalili, S. and Mortazavi, R., "TBM, a transformation based method for microaggregation of large volume mixed data", Data Mining and Knowledge Discovery, Vol. 31, No. 1, (2017), 65–91.

9.     Machanavajjhala, A., Kifer, D., Gehrke, J. and Venkitasubramaniam, M., "L-diversity: Privacy beyond k-anonymity", ACM Transaction on Knowledge Discovery from Data (TKDD), Vol. 1, No. 1, (2007), 1–52.

10.   Ying, X. and Wu, X., "Randomizing social networks: a spectrum preserving approach", in Proceedings of the 2008 SIAM International Conference on Data Mining, SIAM, (2008), 739–750.

11.   Liu, K. and Terzi, E., "Towards identity anonymization on graphs", in Proceedings of the 2008 ACM SIGMOD international conference on Management of data, ACM, (2008), 93–106.

12.   Stokes, K. and Torra, V., "Reidentification and k-anonymity: A model for disclosure risk in graphs", Soft Computing, Vol. 16, No. 10, (2012), 1657–1670.

13.   Ninggal, M. I. H. and Abawajy, J. H., "Utility-aware social network graph anonymization", Journal of Network and Computer Applications, Vol. 56, (2015), 137–148.

14.   Floyd, R. W., "Algorithm 97: Shortest Path", Communications of the ACM, Vol. 5, No. 6, (June 1962), 345. doi>10.1145/367766.368168

15.   Hadian, A. and Nobari, S., Minaei-Bidgoli, B., Qu, Q., "Roll: Fast in-memory generation of gigantic scale-free networks", in Proceedings of the 2016 International Conference on Management of Data, SIGMOD ’16, ACM, New York, NY, USA, (2016), 1829–1842.

16.   Girvan, M. and Newman, M. E., "Community structure in social and biological networks", in Proceedings of the national academy of sciences, Vol. 99, No. 12, (2002), 7821–7826.

17. Watts, D. J. and Strogatz, S. H., "Collective dynamics of ‘small-world’ networks", Nature, Vol. 393, No. 6684, (1998), 440-442.

18.   Mohammadi, A. and Hamidi, H., "Analysis and evaluation of privacy protection behavior and information disclosure concerns in online social networks", International Journal of Engineering, Vol. 31, No. 8, (2018), 1234-1239.