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.
This leads to the privacy notion (k, )-anonymity REF .
k-Metric Antidimension: a Privacy Measure for Social Graphs
ArXiv
ArXiv
Mathematics Computer Science