Question

course of privacy and anonymity:

•Present a well written summary of a k-anonymization algorithm of your choice, along with an illustration of the algorithm

•The summary should not exceed one page

•The illustration should not exceed one page

Answer 1

A k-Anonymization Algorithm on Social Network Data that Reduces Distances between Nodes

Algorithm Illustration :

Anonymization measures and their algorithms for SNS data have been proposed in [1] [3][4]. They assume that the SNS data are expressed via graph structures. In these graphs, user accounts are expressed as nodes and relationships between users are expressed as edges. As an example, consider anonymizing the SN data shown in Fig. 1. At a minimum, identifiers such as the name of each node should be removed, but this is not enough. Assume that the SN data shown in Fig. 1 is published after removing each user's name, and an adversary wants to identify the “Alice” node from the published data. If the adversary knows that Alice has four friends in advance, he or she can identify Alice's node because there is only one node whose degree is four.

To protect private information from such attacks, privacy measures have indeed been proposed, including k-degree [4], k-neighbor [1], and k-isomorphism [5]. These measures are defined based on the k-anonymity [3], and their anonymization processes modify the graph structure to satisfy the privacy measures by adding noise edges or nodes, removing existing nodes or edges, or generalizing attribute values of some nodes. For example, k-degree [4] is a measure ensure that for every node v, there exists at least k−1 nodes with the same degree as v. If we add a noise edge between “Ian” and Greg in the figure, we have at least two nodes whose degrees are four, i.e., the graph satisfies 2-degree (k is 2), and the possibility that an adversary identifies the node v1 as Alice becomes no more than 12.

The k- neighbor [1] metric focuses on the neighborhood subgraph for a node v, which consists of the neighbor nodes of v. This metric ensures that the neighborhood subgraph of every node in the anonymized graph is isomorphic to at least k other neighborhood subgraphs. For example, k-neighbor assumes that an adversary knows the neighborhood subgraph for Alice, which consists of nodes v1,v2,v3,v4,v5; i.e., the adversary knows all friend relationships among Alice's friends in the SN. In this case, if two noise edges (v10,vi) and (v9,vi) are added, the subgraph consisting of nodes v8,v9,v10,v11,vi is isomorphic to the neighborhood subgraph of v1. Therefore, the adversary can not determine whether Alice's node is the node v1 or node vi.

The anonymization process modifies the structure of the original relationships between users in the SNS. Although it is necessary to prevent revealing private information, if the structure of the original relationships is changed, the anonymized data becomes worthless. The anonymization process should maintain the features of the original data to the possible extent while satisfying the privacy measures. In this paper, we propose an anonymization algorithm for applying the k-neighbor privacy measure that suppresses the change of distances between nodes. Our key contribution is to maintain the structural features of the original graph, which the existing algorithm [1] does not do.

chemist chemist nurse chemistV2) Bob Jack V CharlesV Distance 10 Martin Daniel nurse Laura %) Alice doctor doct urse Flora doctor Har urse nurse Ellen (V doctor doctor Greg

Proposed Algorithm

In this section, we propose an anonymization algorithm for k-neighbor metrics. Our proposed algorithm extends the node selection function (Algorithm 2) such that the change in the distances between nodes is suppressed. Algorithm 3 is our proposed algorithm for selecting a node that is appropriate for connecting to node u in neighborhood subgraph Neiqhbor (t) to make Neiohbor (s) and NeighboT (t)isomorphic.

Our algorithm preferentially selects a node that satisfies the conditions as follows:

• The node is closest to node u among the unanonymized nodes

• The degree of the node is the smallest

• The node's label is most similar to label l

In addition, nodes that satisfy the following conditions can not be connected to u:

• Nodes that are already in Neighbor (t)

• Nodes that are already anonymized

chemist chemist nurse chemist V2 medical nurse Distance 10 docto urse doctor doctor nurse nurse V. doctor doctor

Fig. 4.

An anonymized graph example adapts Algorithm 3

View All

To select such a node, our algorithm starts from node u, and traverses the using a greedy approach based on Dijkstra's shortest path algorithm. First, for all nodes except for u, our algorithm sets the distance from u to infinity. Next, our algorithm selects neighbor nodes of u, sets the distance from u to 1 for each of them, and adds them to the set of candidate nodes Q. In the while loop iteration, our algorithm selects, from Q, the node v that is nearest to u, whose degree is the smallest and whose label is similar to furthaer, if vsatisfies the conditions to connect to u as described above, our algorithm returns v. If vdoes not satisfy the conditions to connect to u,v is removed from Q and our algorithm selects the neighbor nodes of v, updates their shortest distances from u, and adds them to Q. In addition, if distance between u and v is greater than the distance threshold d, the algorithm generates noise node vn and returns the noise node added to NodeList to anonymize it.

In Fig. 4, we show an example of anonymization that uses Algorithm 3. In this example, assume that we want to anonymize the two nodes v1 and v9, as in Fig. 3. The algorithm indentifies adjacent isomorphism components by selecting v6, since it has the shortest distance from v9, and satisfies the required conditions; therefore, the algorithm adds noise edges between v9 and v6, as well as v11 and v6. Finally, the algorithm generalizes labels if necessary, i.e., the label of v11 is changed from nurse to medical. In this case, the distance between v9 and v6 is changed from 3 to 1 via anonymization. Thus, we conclude that the distance between nodes is much more preserved than the existing algorithm.