{
  "id": "1408.2154",
  "version": "v2",
  "published": "2014-08-09T21:08:48.000Z",
  "updated": "2015-03-21T20:46:30.000Z",
  "title": "k-Metric Antidimension: a Privacy Measure for Social Graphs",
  "authors": [
    "Rolando Trujillo-Rasua",
    "Ismael G. Yero"
  ],
  "comment": "24 pages",
  "categories": [
    "math.CO",
    "cs.DB"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-08-09T21:08:48.000Z",
      "comment": "23 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-03-21T20:46:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "91D30",
      "05C82",
      "05C85",
      "05C90"
    ],
    "keywords": [
      "social graphs",
      "k-metric antidimension",
      "antiresolving set",
      "metric representation",
      "novel privacy measure"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}