روش بهبودیافته برای بی‌نامسازی داده‌های گراف با تاکید بر حفظ متوسط فاصله بین گره‌ها

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

An Improved Method for Graph Data Anonymization with Emphasis on Preserving the Average Path length

In recent decades, in view of the widespread use of graph data in different applications, for instance     in social networks, communications networks, etc. many researchers have investigated different                anonymization approaches for such data. Although relational data anonymization is mature enough, graph data anonymization is a challenging and relatively new field of research. One of the most important     anonymization models against identity disclosure risk in graph data addresses the number of links a node’s neighbors have, in the graph. In this paper, an improved method is proposed that realizes this model using both edge addition and deletion to the original graph. The application of the method to a number of        different realworld graphs confirms that the method can produce more useful graphs in terms of one of the most important characteristics in such data, i.e., the Average Path Length in the graph and graph structure will undergo less change.