k-Metric Antidimension: a Privacy Measure for Social Graphs

Abstract

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)$ 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\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|S)=r(v_1|S)=\cdots =r(v_{k-1}|S)$, \emph{i.e.}, $v$ and $v_1,\cdots ,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,\ell )$-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.

24 pages