k-Metric Antidimension: a Privacy Measure for Social Graphs

Original · EN

Let G = (V, E) be a simple connected graph and S = {w₁,, wₜ} 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, w₁),, dG(u, wₜ)), where dG(u, v) represents the length of a shortest u-v path in G. The set S is called a resolving set for G if r(u|S) = r(v|S) implies u = v for every u, v ∈ V. The smallest cardinality of a resolving set is the metric dimension of G. In this article we propose, to the best of our knowledge, a new problem in Graph Theory that resembles to the aforementioned metric dimension problem. 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₁,, vₖ₋₁ ∈ V-S with r(v|S) = r(v₁|S) = = r(vₖ₋₁|S), i.e., v and v₁,, vₖ₋₁ have the same metric representation with respect to S. The k-metric antidimension of G is the minimum cardinality among all the k-antiresolving sets for G. In this article, we introduce a novel privacy measure, named (k, ℓ)-anonymity and based on the k-metric antidimension problem, aimed at evaluating the resistance of social graphs to active attacks. We, therefore, propose a true-biased algorithm for computing the k-metric antidimension of random graphs. The success rate of our algorithm, according to empirical results, is above 80 % and 90 % when looking for a k-antiresolving basis and a k-antiresolving set respectively. We also investigate theoretical properties of the k-antiresolving sets and the k-metric antidimension of graphs. In particular, we focus on paths, cycles, complete bipartite graphs and trees.