Toward inference attacks for k-anonymity

Current research still cannot effectively prevent an inference attacker from inferring privacy information for k-anonymous data sets. To solve the issue, we must first study all kinds of aggressive reasoning behaviors and process for the attacker thoroughly. Our work focuses on describing comprehensively the inference attack and analyzing their privacy disclosures for k-anonymous data sets. In this paper, we build up a privacy inference graph based on attack graph theory, which is an extension of attack graph. The privacy inference graph describes comprehensively the inference attack in k-anonymous databases by considering attacker background knowledge and external factors. In the privacy inference graph, we introduce a concept of valid inference path to analyze the privacy disclosures in face of inference attack. According to both above, we design an algorithm to compute the n-valid inference paths. These paths can deduce some privacy information resulting in privacy disclosure. Moreover, we study the optimal privacy strategies to resist inference attack by key attribute sets and valid inference paths in the attack graph. An approximate algorithm is designed to obtain the approximate optimal privacy strategy set. At last, we prove the correctness in theory and analyze the performance of the approximate algorithm and their time complexity.     

Providing <Emphasis Type="Italic">k</Emphasis>-anonymity in data mining

In this paper we present extended definitions of k-anonymity and use them to prove that a given data mining model does not violate the k-anonymity of the individuals represented in the learning examples. Our extension provides a tool that measures the amount of anonymity retained during data mining. We show that our model can be applied to various data mining problems, such as classification, association rule mining and clustering. We describe two data mining algorithms which exploit our extension to guarantee they will generate only k-anonymous output, and provide experimental results for one of them. Finally, we show that our method contributes new and efficient ways to anonymize data and preserve patterns during anonymization.     

On induced-universal graphs for the class of bounded-degree graphs

For a family F of graphs, a graph U is said to be F-induced-universal if every graph of F is an induced subgraph of U. We give a construction for an induced-universal graph for the family of graphs on n vertices with degree at most k. For k even, our induced-universal graph has O(nk/2) vertices and for k odd it has O(n⌈k/2⌉−1/klog2+2/kn) vertices. This construction improves a result of Butler by a multiplicative constant factor for the even case and by almost a multiplicative n1/k factor for the odd case. We also construct induced-universal graphs for the class of oriented graphs with bounded incoming and outgoing degree, slightly improving another result of Butler.     

Multilayer grid embeddings for VLSI

In this paper we propose two new multilayer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes “exist” only on one layer, we prove a tight area × (number of contact cuts) = Θ(n ²) tradeoff for embeddingn-node planar graphs of bounded degree in two layers. For the second model in which nodes “exist” simultaneously on all layers, we give a number of upper bounds on the area needed to embed groups using no contact cuts. We show that anyn-node graph of thickness 2 can be embedded on two layers inO(n ²) area. This bound is tight even if more layers and any number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers inO(n ^3/2(logn)²) area. Some of our embedding algorithms have the additional property that they can respect prespecified grid placements of the nodes of the graph to be embedded. We give an algorithm for embeddingn-node graphs of thicknessk ink layers usingO(n ³) area, using no contact cuts, and respecting prespecified node placements. This area is asymptotically optimal for placement-respecting algorithms, even if more layers are allowed, as long as a fixed fraction of the edges do not use contact cuts. Our results use a new result on embedding graphs in a single-layer grid, namely an embedding ofn-node planar graphs such that each edge makes at most four turns, and all nodes are embedded on the same line.     

A note on the online First-Fit algorithm for coloring k-inductive graphs

In a FOCS 1990 paper, S. Irani proved that the First-Fit online algorithm for coloring a graph uses at most O(klogn) colors for k-inductive graphs. In this note we provide a very short proof of this fact.     

A secure distributed framework for achieving k-anonymity

k-anonymity provides a measure of privacy protection by preventing re-identification of data to fewer than a group of k data items. While algorithms exist for producing k-anonymous data, the model has been that of a single source wanting to publish data. Due to privacy issues, it is common that data from different sites cannot be shared directly. Therefore, this paper presents a two-party framework along with an application that generates k-anonymous data from two vertically partitioned sources without disclosing data from one site to the other. The framework is privacy preserving in the sense that it satisfies the secure definition commonly defined in the literature of Secure Multiparty Computation.     

Boolean-width of graphs

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods-Boolean sums of neighborhoods-across a cut of a graph. For many graph problems, this number is the runtime bottleneck when using a divide-and-conquer approach. For an n-vertex graph given with a decomposition tree of boolean-width k, we solve Maximum Weight Independent Set in time O(n²k2^2k) and Minimum Weight Dominating Set in time O(n²+nk2^3k). With an additional n² factor in the runtime, we can also count all independent sets and dominating sets of each cardinality.Boolean-width is bounded on the same classes of graphs as clique-width. boolean-width is similar to rank-width, which is related to the number of GF(2)-sums of neighborhoods instead of the Boolean sums used for boolean-width. We show for any graph that its boolean-width is at most its clique-width and at most quadratic in its rank-width. We exhibit a class of graphs, the Hsu-grids, having the property that a Hsu-grid on Θ(n²) vertices has boolean-width Θ(logn) and rank-width, clique-width, tree-width, and branch-width Θ(n).     

Tight bounds for the cover time of multiple random walks

We study the cover time of multiple random walks on undirected graphs G=(V,E). We consider k parallel, independent random walks that start from the same vertex. The speed-up is defined as the ratio of the cover time of a single random walk to the cover time of these k random walks. Recently, Alon et al. (2008) [5] derived several upper bounds on the cover time, which imply a speed-up of Ω(k) for several graphs; however, for many of them, k has to be bounded by O(logn). They also conjectured that, for any 1?k?n, the speed-up is at most O(k) on any graph. We prove the following main results:

•

We present a new lower bound on the speed-up that depends on the mixing time. It gives a speed-up of Ω(k) on many graphs, even if k is as large as n.

•

We prove that the speed-up is O(klogn) on any graph. For a large class of graphs we can also improve this bound to O(k), matching the conjecture of Alon et al.

•

We determine the order of the speed-up for any value of 1?k?n on hypercubes, random graphs and degree restricted expanders. For d-dimensional tori with d>2, our bounds are tight up to logarithmic factors.

•

Our findings also reveal a surprisingly sharp threshold behaviour for certain graphs, e.g., the d-dimensional torus with d>2 and hypercubes: there is a value T such that the speed-up is approximately min{T,k} for any 1?k?n.

     

Resisting re-identification mining on social graph data

Varieties of sensitive personal information become a privacy concern for social networks. However, characteristics of social graphs could be utilized by attackers to re-identify target entities of social networks. In this paper, we first analyze a new attack model named bin-based attack, which re-identifies social individuals in social networks, according to their graph structure characteristics. For bin-based attack, we propose a novel k-anonymity scheme. With this scheme, social individuals are completely k-anonymity protection. Experiments illustrate the effectiveness of the proposed scheme. The utility of anonymized networks are demonstrated with the results of vertex degree, and betweenness.     

k-tuple domination in graphs

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current paper studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the k-tuple domination problem in strongly chordal graphs, which is a subclass of chordal graphs and includes trees, block graphs, interval graphs and directed path graphs. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and for bipartite graphs.     

Path bipancyclicity of hypercubes

A bipartite graph is vertex-bipancyclic (respectively, edge-bipancyclic) if every vertex (respectively, edge) lies in a cycle of every even length from 4 to |V(G)| inclusive. It is easy to see that every connected edge-bipancyclic graph is vertex-bipancyclic. An n-dimensional hypercube, or n-cube denoted by Qn, is well known as bipartite and one of the most efficient networks for parallel computation. In this paper, we study a stronger bipancyclicity of hypercubes. We prove that every n-dimensional hypercube is (2n−4)-path-bipancyclic for n?3. That is, for any path P of length k with 1?k?2n−4 and any integer l with max{2,k}?l?²n−1, an even cycle C of length 2l can be found in Qn such that the path P is included in C for n?3.     

Spanners of bounded degree graphs

A k-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most k times the distance in G. We prove that for fixed k,w, the problem of deciding if a given graph has a k-spanner of treewidth w is fixed-parameter tractable on graphs of bounded degree. In particular, this implies that finding a k-spanner that is a tree (a tree k-spanner) is fixed-parameter tractable on graphs of bounded degree. In contrast, we observe that if the graph has only one vertex of unbounded degree, then Treek-Spanner is NP-complete for k?4.     

Some results on graphs without long induced paths

Many NP-hard graph problems remain difficult on P_k-free graphs for certain values of k. Our goal is to distinguish subclasses of P_k-free graphs where several important graph problems can be solved in polynomial time. In particular, we show that the independent set problem is polynomial-time solvable in the class of (P_k,K_1,n)-free graphs for any positive integers k and n, thereby generalizing several known results.     

Anonymity preserving sequential pattern mining

The increasing availability of personal data of a sequential nature, such as time-stamped transaction or location data, enables increasingly sophisticated sequential pattern mining techniques. However, privacy is at risk if it is possible to reconstruct the identity of individuals from sequential data. Therefore, it is important to develop privacy-preserving techniques that support publishing of really anonymous data, without altering the analysis results significantly. In this paper we propose to apply the Privacy-by-design paradigm for designing a technological framework to counter the threats of undesirable, unlawful effects of privacy violation on sequence data, without obstructing the knowledge discovery opportunities of data mining technologies. First, we introduce a k-anonymity framework for sequence data, by defining the sequence linking attack model and its associated countermeasure, a k-anonymity notion for sequence datasets, which provides a formal protection against the attack. Second, we instantiate this framework and provide a specific method for constructing the k-anonymous version of a sequence dataset, which preserves the results of sequential pattern mining, together with several basic statistics and other analytical properties of the original data, including the clustering structure. A comprehensive experimental study on realistic datasets of process-logs, web-logs and GPS tracks is carried out, which empirically shows how, in our proposed method, the protection of privacy meets analytical utility.     

Extended k-anonymity models against sensitive attribute disclosure

p-Sensitive k-anonymity model has been recently defined as a sophistication of k-anonymity. This new property requires that there be at least p distinct values for each sensitive attribute within the records sharing a set of quasi-identifier attributes. In this paper, we identify the situations when the p-sensitive k-anonymity property is not enough for the sensitive attributes protection. To overcome the shortcoming of the p-sensitive k-anonymity principle, we propose two new enhanced privacy requirements, namely p⁺-sensitive k-anonymity and (p,α)-sensitive k-anonymity properties. These two new introduced models target at different perspectives. Instead of focusing on the specific values of sensitive attributes, p⁺-sensitive k-anonymity model concerns more about the categories that the values belong to. Although (p,α)-sensitive k-anonymity model still put the point on the specific values, it includes an ordinal metric system to measure how much the specific sensitive attribute values contribute to each QI-group. We make a thorough theoretical analysis of hardness in computing the data set that satisfies either p⁺-sensitive k-anonymity or (p,α)-sensitive k-anonymity. We devise a set of algorithms using the idea of top-down specification, which is clearly illustrated in the paper. We implement our algorithms on two real-world data sets and show in the comprehensive experimental evaluations that the two new introduced models are superior to the previous method in terms of effectiveness and efficiency.     

A refined search tree technique for Dominating Set on planar graphs

We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8^kn) and O(8^kk+n³), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.     

Optimal 1-edge fault-tolerant designs for ladders

A graph G∗ is 1-edge fault-tolerant with respect to a graph G, denoted by 1-EFT(G), if every graph obtained by removing any edge from G∗ contains G. A 1-EFT(G) graph is optimal if it contains the minimum number of edges among all 1-EFT(G) graphs. The kth ladder graph, L_k, is defined to be the cartesian product of the P_k and P₂ where P_n is the n-vertex path graph. In this paper, we present several 1-edge fault-tolerant graphs with respect to ladders. Some of these graphs are proven to be optimal.     

(<Emphasis Type="Italic">α</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-anonymous data publishing

Privacy preservation is an important issue in the release of data for mining purposes. The k-anonymity model has been introduced for protecting individual identification. Recent studies show that a more sophisticated model is necessary to protect the association of individuals to sensitive information. In this paper, we propose an (α, k)-anonymity model to protect both identifications and relationships to sensitive information in data. We discuss the properties of (α, k)-anonymity model. We prove that the optimal (α, k)-anonymity problem is NP-hard. We first present an optimal global-recoding method for the (α, k)-anonymity problem. Next we propose two scalable local-recoding algorithms which are both more scalable and result in less data distortion. The effectiveness and efficiency are shown by experiments. We also describe how the model can be extended to more general cases.     

Strong computational lower bounds via parameterized complexity

We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k)no(k) for any function f, even if we restrict the parameter values to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be of the order Θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds on the computational complexity are also derived for other NP-hard problems in the above class. Our techniques can be further extended to derive computational lower bounds on polynomial time approximation schemes for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/?)no(1/?) for any function f unless an unlikely collapse occurs in parameterized complexity theory.     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.