k-Metric Antidimension: a Privacy Measure for Social Graphs

Let $G=(V,E)$ be a simple connected graph and $S = {w_1, \cdots, w_t} \subseteq V$ an ordered subset of vertices. The metric representation of a vertex $u\in V$ with respect to $S$ is the $t$-vector $r(u|S) = (d_G(u, w_1), \cdots, d_G(u, w_t))$,where$d_G(u, v)$representsthelengthofashortest$u-v$pathin$G$\mathrm{.}Theset$S$iscalledaresolvingsetfor$G$if$r(u|S) = r(v|S)$implies$u = v$forevery$u, v \in 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\in V-S$ there exist other $k-1$ different vertices $v_1,\cdots ,v_{k-1}\in V-S$ with $r(v\mathrm{\mid }S)=r(v_1\mathrm{\mid }S)=\cdots =r(v_{k-1}\mathrm{\mid }S)$, \emph{i.e.}, $v$ and $v_1, \cdots, v_{k-1}$havethesamemetricrepresentationwithrespectto$S$\mathrm{.}The$k$-metricantidimensionof$G$istheminimumcardinalityamongallthe$k$-antiresolvingsetsfor$G$. In this article, we introduce a novel privacy measure, named $(k, \ell)$-anonymityandbasedonthe$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\mathrm{\%}$ and $90\mathrm{\%}$ 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.