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.
Other types of active attacks exist. For instance, the maximal vertex coverage (MVC) attack consists in attacking a few nodes so as to delete as many edges of the network as possible. In this attack, the attacker tries to convince some users to leave the social network in order to reduce the number of residual social ties. Metrics to quantify the impact of MVC attacks have been studied in @cite_20 . MVC is not a privacy attack, though.
@cite_20
2137313157 2032186932 2004973717 2040480264
Measuring the impact of network attack is an important issue in network science. In this paper, we study the impact of maximal vertex coverage (MVC) attack in large complex networks, where the attacker aims at deleting as many edges of the network as possible by attacking a small fraction of nodes. First, we present two metrics to measure the impact of MVC attack. To compute these metrics, we propose an efficient randomized greedy algorithm with near-optimal performance guarantee. Second, we generalize the MVC attack into an uncertain setting, in which a node is deleted by the attacker with a prior probability. We refer to the MVC attack under such uncertain environment as the probabilistic MVC attack. Based on the probabilistic MVC attack, we propose two adaptive metrics, and then present an adaptive greedy algorithm for calculating such metrics accurately and efficiently. Finally, we conduct extensive experiments on 20 real datasets. The results show that P2P and co-authorship networks are extremely robust under the MVC attack while both the online social networks and the Email communication networks exhibit vulnerability under the MVC attack. In addition, the results demonstrate the efficiency and effectiveness of the proposed algorithms for computing the proposed metrics. Serious concerns on privacy protection in social networks have been raised in recent years; however, research in this area is still in its infancy. The problem is challenging due to the diversity and complexity of graph data, on which an adversary can use many types of background knowledge to conduct an attack. One popular type of attacks as studied by pioneer work [2] is the use of embedding subgraphs. We follow this line of work and identify two realistic targets of attacks, namely, NodeInfo and LinkInfo. Our investigations show that k-isomorphism, or anonymization by forming k pairwise isomorphic subgraphs, is both sufficient and necessary for the protection. The problem is shown to be NP-hard. We devise a number of techniques to enhance the anonymization efficiency while retaining the data utility. A compound vertex ID mechanism is also introduced for privacy preservation over multiple data releases. The satisfactory performance on a number of real datasets, including HEP-Th, EUemail and LiveJournal, illustrates that the high symmetry of social networks is very helpful in mitigating the difficulty of the problem. Abstract We consider the max-vertex-cover (MVC) problem, i.e., find k vertices from an undirected and edge-weighted graph G =( V , E ), where | V |= n ⩾ k , such that the total edge weight covered by the k vertices is maximized. There is a 3 4-approximation algorithm for MVC, based on a linear programming relaxation. We show that the guaranteed ratio can be improved by a simple greedy algorithm for k >(3 4) n , and a simple randomized algorithm for k >(1 2) n . Furthermore, we study a semidefinite programming (SDP) relaxation based approximation algorithms for MVC. We show that, for a range of k , our SDP-based algorithm achieves the best performance guarantee among the four types of algorithms mentioned in this paper. Given a simple undirected graph @math and a positive integer @math , the maximum vertex coverage problem (MVC) is the problem of finding a set @math of @math vertices of @math such that the number of edges having at least one endpoint in @math is as large as possible. The problem is NP-hard even in bipartite graphs, as shown in two recent papers [N. Apollonio and B. Simeone, Discrete Appl. Math., 165 (2014), pp. 37--48; G. Joret and A. Vetta, Reducing the Rank of a Matroid, preprint, arXiv:1211.4853v1 [cs.DS], 2012]. By exploiting the structure of the fractional optimal solutions of a linear programming formulation for the maximum coverage problem, we provide a @math -approximation algorithm for the problem. The algorithm immediately extends to the weighted version of MVC.