text: Let @math be a simple connected graph and @math an ordered subset of vertices. The metric representation of a vertex @math with respect to @math is the @math -vector @math , where @math represents the length of a shortest @math path in @math . The set @math is called a resolving set for @math if @math implies @math for every @math . The smallest cardinality of a resolving set is the metric dimension of @math . 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 @math a @math -antiresolving set if @math is the largest positive integer such that for every vertex @math there exist other @math different vertices @math with @math , , @math and @math have the same metric representation with respect to @math . The @math -metric antidimension of @math is the minimum cardinality among all the @math -antiresolving sets for @math . In this article, we introduce a novel privacy measure, named @math -anonymity and based on the @math -metric antidimension problem, aimed at evaluating the resistance of social graphs to active attacks. We, therefore, propose a true-biased algorithm for computing the @math -metric antidimension of random graphs. The success rate of our algorithm, according to empirical results, is above @math and @math when looking for a @math -antiresolving basis and a @math -antiresolving set respectively. We also investigate theoretical properties of the @math -antiresolving sets and the @math -metric antidimension of graphs. In particular, we focus on paths, cycles, complete bipartite graphs and trees.
  @cite_14: Nowadays, partly driven by many Web 2.0 applications, more and more social network data has been made publicly available and analyzed in one way or another. Privacy preserving publishing of social network data becomes a more and more important concern. In this paper, we present a brief yet systematic review of the existing anonymization techniques for privacy preserving publishing of social network data. We identify the new challenges in privacy preserving publishing of social network data comparing to the extensively studied relational case, and examine the possible problem formulation in three important dimensions: privacy, background knowledge, and data utility. We survey the existing anonymization methods for privacy preservation in two categories: clustering-based approaches and graph modification approaches.
  @cite_10: 
  @cite_11: The rise of the social web has traditionally been accompanied by privacy concerns. Research on social web privacy has been conducted from various directions including law, social and computer sciences contributing to the body of literature. In this paper, we argue for an interdisciplinary approach to capture the multidimensional concept of privacy. For this purpose, we propose a three-layered framework to systematically analyze the privacy impact of various research directions. Subsequently, we conduct an interdisciplinary literature analysis, highlighting areas for improvement as well dependencies between different research directions.
summary: Interested readers could refer to @cite_11 @cite_10 @cite_14 for further reading on privacy-preserving publication of social graphs.