Social Network Anonymization Techniques

Introduction

In the previous chapter we have talked about anonymization of social networks and some general approaches for that. In this chapter we shall move into some detail of specific anonymization techniques. In fact, we shall be considering an anonymisation procedure to prevent neighbourhood attack and the other one being a greedy algorithm for social network anonymisation. In order to explain the concept of background knowledge and how it can help an adversary in identifying a respondent in a social network let us consider the following situation.

Figure 1.

A friend network

Figure 2.

The network with anonymous nodes

Let us consider the social network of friends given in Figure 1. The anonymised network is given in Figure 2. Suppose, an adversary knows that F has four friends. Even though the network is anonymised, it can be observed that there is only one node in Figure 2 having degree 4, B can be identified by the adversary. So, through the 1-neighbourhood graph helps in this identification. Of course, the background knowledge plays an important role here. In this chapter we shall discuss on the anonymisation algorithms which can provide security against neighbourhood attacks.

Anonymisation Against Neighbourhood Attack

First we shall present the anonymisation techniques used for privacy preservation against neighbourhood attacks.

The concept of level hierarchy was used by Zhou and Pei (2008) for developing an anonymisation technique to prevent neighbourhood attacks. There is a meta symbol * generalising all levels. Other levels are arranged downward manner from general ones to specific one.

We recall the definition of a neighbourhood, which is as follows:

• Definition 1: In a social network G, the neighbourhood of a vertex ‘u’ is the induced subgraph of the neighbours of u, denoted by , where.

The components of the neighbourhood graph of a vertex are the neighbourhood components. In a social network G, a subgraph C of G is a neighbourhood component of if C is a maximal connected subgraph in .

• Definition 2: The d-neighbourhood graph of a vertex ‘u’ includes all the vertices that are within the distance d from the vertex u.

The aim of the anonymisation process in Zhou and Pei (2008) is to enable the anonymised graph to be able to provide answers to aggregate network queries.

• Definition 3: Two graphs G and H are said to be isomorphic, if there exists a bijection ‘f’ between the vertices V and W of G and H respectively such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H.

This kind of bijection is commonly described as “edge-preserving bijection”, in accordance with the general notion of isomorphism being a structure-preserving bijection.