k-Metric antidimension: A privacy measure for social graphs

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 S={w1,…,wt}⊆VS={w1,…,wt}⊆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)=(dG(u,w1),…,dG(u,wt)),r(u|S)=(dG(u,w1),…,dG(u,wt)), where dG(u, v  ) represents the length of a shortest u−vu−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−Sv∈V−S there exist other k−1k−1 different vertices v1,…,vk−1∈V−Sv1,…,vk−1∈V−S with r(v|S)=r(v1|S)=⋯=r(vk−1|S)r(v|S)=r(v1|S)=⋯=r(vk−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.