Search

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 ) be a simple connected graph and S = { w 1 , … , w t } ⊆ V an ordered subset of vertices. The metric representation of a vertex u ∈ V with respect to S is the t -vector r ( u | S ) = ( d G ( u , w 1 ) , … , d G ( u , w t ) ) , where d G ( u, v ) represents the length of a shortest 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 there exist other k − 1 different vertices v 1 , … , v k − 1 ∈ V − S with r ( v | S ) = r ( v 1 | 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. [ABSTRACT FROM AUTHOR]