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) 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 1 , · · · , v k−1 ∈ V − S with r(v|S) = r(v 1 |S) = · · · = r(v k−1 |S), i.e., v and v 1 , · · · , v k−1 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.
To the best of our knowledge, the first privacy measure to evaluate the resistance of social graphs to active attacks was proposed just recently in REF .
k-Metric Antidimension: a Privacy Measure for Social Graphs
ArXiv
ArXiv
Mathematics Computer Science