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 <span id="mmlsi6" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0020025515006477&_mathId=si6.gif&_user=111111111&_pii=S0020025515006477&_rdoc=1&_issn=00200255&md5=0a6d1c0428b97d72b5c71a3f098296d0" title="Click to view the MathML source">G=(V,E)span><span class="mathContainer hidden"><span class="mathCode">$G=(V,E)$span>span>span> be a simple connected graph and <span id="mmlsi7" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0020025515006477&_mathId=si7.gif&_user=111111111&_pii=S0020025515006477&_rdoc=1&_issn=00200255&md5=5508a18add02451d8e1d2a1187c1de3e" title="Click to view the MathML source">S={w₁,…,w_t}⊆Vspan><span class="mathContainer hidden"><span class="mathCode">$S=\{w_1,\dots ,w_t\}\subseteq V$span>span>span> an ordered subset of vertices. The metric representation of a vertex u ∈ V with respect to S is the t  -vector <span id="mmlsi8" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0020025515006477&_mathId=si8.gif&_user=111111111&_pii=S0020025515006477&_rdoc=1&_issn=00200255&md5=da7fd80fde0e5ca055e38fd9ec3a33cd" title="Click to view the MathML source">r(u|S)=(d_G(u,w₁),…,d_G(u,w_t)),span><span class="mathContainer hidden"><span class="mathCode">$r\left(u\right|S)=(d_G(u,w_1),\dots ,d_G(u,w_t)),$span>span>span> where d_G(u, v  ) represents the length of a shortest <span id="mmlsi9" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0020025515006477&_mathId=si9.gif&_user=111111111&_pii=S0020025515006477&_rdoc=1&_issn=00200255&md5=308213a0dc8d8b868b90b33e95e48d4f" title="Click to view the MathML source">u−vspan><span class="mathContainer hidden"><span class="mathCode">$u-v$span>span>span> path in G. We call S a k-antiresolving set if k   is the largest positive integer such that for every vertex <span id="mmlsi10" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0020025515006477&_mathId=si10.gif&_user=111111111&_pii=S0020025515006477&_rdoc=1&_issn=00200255&md5=7b4ec655440a0a47db0eb2ecce0d0b94" title="Click to view the MathML source">v∈V−Sspan><span class="mathContainer hidden"><span class="mathCode">$v\in V-S$span>span>span> there exist other <span id="mmlsi11" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0020025515006477&_mathId=si11.gif&_user=111111111&_pii=S0020025515006477&_rdoc=1&_issn=00200255&md5=8b81a76e181f54a9aafc95e672b923a2" title="Click to view the MathML source">k−1span><span class="mathContainer hidden"><span class="mathCode">$k-1$span>span>span> different vertices <span id="mmlsi12" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0020025515006477&_mathId=si12.gif&_user=111111111&_pii=S0020025515006477&_rdoc=1&_issn=00200255&md5=cd967b4a2de693303d9095d296a90d70" title="Click to view the MathML source">v₁,…,v_k−1∈V−Sspan><span class="mathContainer hidden"><span class="mathCode">$v_1,\dots ,v_{k-1}\in V-S$span>span>span> with <span id="mmlsi13" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0020025515006477&_mathId=si13.gif&_user=111111111&_pii=S0020025515006477&_rdoc=1&_issn=00200255&md5=e48e91432ab28666baf41aa07ffea46d" title="Click to view the MathML source">r(v|S)=r(v₁|S)=鈰?r(v_k−1|S)span><span class="mathContainer hidden"><span class="mathCode">span>span>span>. 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.