IJE TRANSACTIONS A: Basics Vol. 31, No. 10 (October 2018) 1624-1632   

downloaded Downloaded: 67   viewed Viewed: 481

R. Mortazavi and S. H. Erfani
( Received: March 19, 2018 – Accepted in Revised Form: August 17, 2018 )

Abstract    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.


Keywords    mathematical modeling, graph anonymization, graph modification, social network, privacy, database security



در سال‌های اخیر، نگرانی کاربران از انتشار داده‌های شبکه‌های اجتماعی با توجه به استفاده گسترده از این اطلاعات برای اهداف پژوهشی افزایش یافته است. در این مقاله به خطر افشای شناسه یک گره در شبکه با فرض اینکه مهاجم اطلاعات یکی از همسایه‌های بلافصل آن گره را در اختیار دارد، پرداخته می‌شود. ابتدا سطح بی‌نامی یک گراف شبکه بر اساس این خطر فرمول‌بندی ‌شده و در ادامه یک مدل ریاضی برای حل این خطر ارائه می‌شود. استفاده از روش فوق بر روی تعدادی از مجموعه داده‌های مصنوعی و واقعی نشان‌دهنده عمومیت روش فوق است که می‌تواند در کاربردهای مختلف نتایج مناسبی را بر حسب سودمندی داده‌های بی‌نام‌سازی شده به‌دست آورد.


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.

International Journal of Engineering
E-mail: office@ije.ir
Web Site: http://www.ije.ir