Performance analysis of K-Degree anonymization on Barabási-Albert Graph

Abstract

Anonymity is one the most important problems that emerged with the increasing number of graphbased social networks. It is not straightforward to ensure anonymity by adding or removing some nodes from the graph. Therefore, a more sophisticated approach is required. The consideration of the degree of the nodes in a graph may facilitate having knowledge about specific nodes. To handle this problem, one of the prominent solutions is k-degree anonymization where some nodes involving particular degree values are anonymized by masking its information from the attackers. Our objective is to evaluate the achievement of k-degree anonymization with a well-known graph structure, namely, Barabási-Albert graph, which is similar to the graphs on social networks. Hence, we generate multiple synthetic Barabási-Albert graphs and evaluate the k-degree anonymization performance on these graphs. According to experimental results, the success of k-degree anonymity approximately proportional to the number of edges or nodes.

Anonimlik, çizge tabanlı sosyal ağların sayısının artmasıyla ortaya çıkan en önemli sorunlardan biridir. Çizgeye bazı düğümler ekleyerek veya çıkararak anonimliği sağlamak kolay değildir. Bu nedenle, daha komplike bir yaklaşım gereklidir. Çizgenin yapısı veya çizgedeki düğümlerin derecesi, belirli düğümler hakkında bilgi sahibi olmayı kolaylaştırabilir. Bu sorun için öne çıkan çözümlerden biri olan k-derece anonimleştirme, belirli dereceleri içeren bazı düğümlerin bilgilerinin saldırganlardan gizlenerek anonimleştirilmesidir. Amacımız, sosyal ağlardaki çizgelere benzeyen Barabási-Albert çizgesi gibi iyi bilinen bir çizge yapısı ile k-derece anonimleştirmenin başarısını değerlendirmektir. Bu nedenle, birden çok sentetik Barabási-Albert çizgesi değerlendiriyoruz. Deneysel sonuçlara göre, k-derece anonimliğin başarısı, yaklaşık olarak kenar veya düğüm sayısı ile orantılıdır.