# A Differentiated Anonymity Algorithm for Social Network Privacy Preservation
## 2 Problem Description  
We first present the terminology that will be used in this paper. We focus on the attribute privacy-preserving problem for an un-weighted, undirected, simple graph with a privacy attribute. Figure 2 shows an example of such a graph. A social network graph is defined as follows:  
**Definition 1**. : _Social Network Graph [14]. The social network data is modeled by a graph with a four tuple G = (V, E, A, S). V is a set of nodes representing users; E \(\subseteq\) V \(\times\) V is a set of edges representing social relations between users; A= {A_1, A_2,..., A_n_} _is a set of attribute nodes representing all users' possible values of the privacy attribute, and A_\({}_{i}\) _corresponds to any privacy attribute values in a social network. For example, for the attribute called health-state, pneumonia and influenza, as two different property values form two different attribute nodes showed by A_1 = pneumonia, A_2 = influenza. S = {H, M, L}, is the set of the sensitivity of privacy attribute values; S(A_\({}_{i}\)) represents the sensitivity of attribute value Ai, and Si is the short name of S(Ai), as shown in Figure 2._  
**Definition 2**. : _Structural Re-identification Attack (SRA) [15]. Given a social network G(V, E), its published graph G'(V', E'), a target entity t\(\in\)V, and the attacker background knowledge F(t), the attacker performs the structural re-identification attack by searching for all of the vertices in G' that could be mapped to t, i.e., VF (t) = {v\(\in\) V' \(|\) F(v) = F(t)}. If \(|\) VF (t) \(|\)\(<<\) \(|\) V' \(|\), then t has a high probability to be re-identified._  
Figure 2: A simple Social-Attribute graph. **Definition 3**. : _K-degree Anonymity [15]. Given a graph \(G\) = (\(V\), \(E\)) with \(V\) = {v\({}_{1}\), \(v_{2}\),..., \(v_{n}\)} and \(d(v_{i})\) = \(|\) {u\(\in\)\(V\) : (\(u\), \(v_{i}\))\(\in\)\(E\)}\(|\), and the type of attacker's background knowledge F, the degree sequence of \(G\) is defined to be the sequence \(P\) = (\(d(v_{1})\), \(d(v_{2})\),..., \(d(v_{n})\)). \(P\) can be divided into a group of subsequences [[\(d(1)\),..., \(d(i_{1})\)], [\(d(i_{1}\) + 1),..., \(d(i_{2})\)],..., [\(d(i_{m}+1)\),..., \(P(i)\)]] such that \(G\) satisfies k-degree anonymity if, for every vertex \(v_{i}\)\(\in\)V, there exist at least k-1 other vertices in \(G\) with the same degree as \(v_{i}\). In other words, for any subsequences \(P_{y}\) = [\(d(i_{y}+1)\),..., \(d(i_{y+1})\)], \(P_{y}\) satisfies two constraints: (1) All of the elements in \(P_{y}\) share the same degree (\(d(i_{y}+1)\) = \(d(i_{y}+2)\) =... = \(d(i_{y+1})\)); and (2) \(P_{y}\) has size of at least k, namely ( \(|\) {i\({}_{y+1}-i_{y}\)} \(|\)\(\geq\) k)._  
**Definition 4**. : _L-diversity Anonymity [16]. Given an anonymized graph \(G^{\prime}\) = (\(V^{\prime}\), \(E^{\prime}\), \(A^{\prime}\), S), \(G^{\prime}\) satisfies l-diversity anonymity if, for any privacy attribute values \(A_{i}{}^{{}^{\prime}}\), there exists at least l-1 different attribute values in an equivalence group._  
**Definition 5**. : _Attribute Value Sensitivity Function. The sensitivity of privacy attribute values are usually established by a membership function. We use a trapezoidal distribution membership function sensitivity(x) which ranges from [0, 1] to determine the attribute value sensitivity S as shown in Equation (1). The independent variable x is any privacy attribute value from the set A, the sensitivity of x is written S(x), and we classify the privacy sensitivity into three categories which are denoted by H (high), M (middle), and L (low). The following three parts show the details of three categories._  
\[ \begin{split}& sensitivity(x)=\left\{\begin{array}{l}0,x \leq a\\ \frac{x-a}{b-a},a<x\leq b\\ 1,x>b\end{array}\right.\\ & s.t.\left\{\begin{array}{l}x\leq a:S=L\\ a<x\leq b:S=M\\ x>b:S=H\end{array}\right.\\ \end{split}  \tag{1}\]  
(1) When x \(\leq\) a, S(x) = L, L is the shorthand of low.