k-Metric antidimension: A privacy measure for social graphs

详细信息    查看全文

• 作者：Rolando Trujillo-Rasua ; ^a ; ^{rolando.trujillo@uni.lu" class="auth_mail" title="E-mail the corresponding author} ; ^{rolando.trujillo@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Ismael G. Yero^b
• 关键词：Anonymity ; Active attack ; Social network ; Graph ; Resolving set ; k-Metric antidimension
• 刊名：Information Sciences
• 出版年：2016
• 出版时间：20 January 2016
• 年：2016
• 卷：328
• 期：Complete
• 页码：403-417
• 全文大小：595 K

文摘

The study and analysis of social graphs impacts on a wide range of applications, such as community decision making support and recommender systems. With the boom of online social networks, such analyses are benefiting from a massive collection and publication of social graphs at large scale. Unfortunately, individuals’ privacy right might be inadvertently violated when publishing this type of data. In this article, we introduce (k, 鈩?-anonymity; a novel privacy measure aimed at evaluating the resistance of social graphs to active attacks. (k, 鈩?-anonymity is based on a new problem in Graph Theory, the k-metric antidimension defined as follows.

Let G=(V,E)$G=(V,E)$ be a simple connected graph and 08a18add02451d8e1d2a1187c1de3e" title="Click to view the MathML source">S={w₁,…,w_t}⊆V$S=\{w_1,\dots ,w_t\}\subseteq V$ an ordered subset of vertices. The metric representation of a vertex u ∈ V with respect to S is the t  -vector a055e38fd9ec3a33cd" title="Click to view the MathML source">r(u|S)=(d_G(u,w₁),…,d_G(u,w_t)),$r\left(u\right|S)=(d_G(u,w_1),\dots ,d_G(u,w_t)),$ where d_G(u, v  ) represents the length of a shortest u−v$u-v$ path in G. We call S a k-antiresolving set if k   is the largest positive integer such that for every vertex v∈V−S$v\in V-S$ there exist other k−1$k-1$ different vertices v₁,…,v_k−1∈V−S$v_1,\dots ,v_{k-1}\in V-S$ with r(v|S)=r(v₁|S)=鈰?r(v_k−1|S). The k-metric antidimension of G is the minimum cardinality among all the k-antiresolving sets for G.

We address the k-metric antidimension problem by proposing a true-biased algorithm with success rate above 80% when considering random graphs of size at most 100. The proposed algorithm is used to determine the privacy guarantees offered by two real-life social graphs with respect to (k, 鈩?-anonymity. We also investigate theoretical properties of the k-metric antidimension of graphs. In particular, we focus on paths, cycles, complete bipartite graphs and trees.