A Review of Several Privacy Violation Measures for Large Networks under Active Attacks

Abstract

It is by now a standard practice to use the concepts and terminologies of network science to analyze social networks of interconnections between people such as Facebook, Twitter and LinkedIn. The powers and implications of such social network analysis are indeed indisputable; for example, such analysis may uncover previously unknown knowledge on community-based involvements, media usages and individual engagements. However, all these benefits are not necessarily cost-free since a malicious individual could compromise privacy of users of these social networks for harmful purposes that may result in the disclosure of sensitive data that may be linked to its users. A natural way to avoid this consists of an “anonymization process” of the relevant social network. However, since such anonymization processes may not always succeed, an important research goal is to quantify and measure how much privacy a given social network can achieve. Toward this goal, some recent research works have aimed at evaluating the resistance of a social network against active privacy-violating attacks by introducing and studying a new and meaningful privacy measure for social networks. In this chapter, we review both theoretical and empirical aspects of such privacy violation measures of large networks under active attacks.

1. Introduction

In recent years, social networks have become an indisputable part of people’s lives. The emergence of such networks has altered how we interact with the world. A given individual’s day-to-day activities like media consumption, job hunting and social interaction have changed, along with how businesses and other beneficial entities interact with them through marketing, advertising, and information diffusion. This has led to an unstoppable race of collecting information and interaction from social networks by researchers, governments, and business entities for various purposes. From a research point of view, social networks and their interaction mechanisms provide valuable insight in many fields of study, such as sociology, psychology, advertising, and recommendation systems. It is only natural that the information contained in these networks and the value they hold have been and will be targeted by bad actors for malicious activities. The importance of these networks and the value of information that can be retrieved from them have led social network researchers to take a closer look at methods to combat such bad actors as well as formulate network measures that can provide an insight to the privacy of these networks. In this survey, we will look at one such measure known as $\left(k,\mathrm{\ell }\right)$ -anonymity [1] and will discuss some theoretical and empirical results regarding this measure.

1.1 Overview of the paper

Given the irrefutable importance of social networks in our daily lives and the ever increasing risk of compromising valuable personal data through privacy attacks against these networks, it is preferable to know how secure a given social network is against privacy attacks. This necessitates a deeper look into the types of privacy attacks and how to cope with them. There is an extensive literature on privacy preserving computational models in variety of application areas such as multi-party communications or distributed computing settings [2, 3, 4, 5, 6]. In this chapter, we focus on a specific type of attack known as background-based active attack and one measure that reflects the resistance of any given network against such attacks. The organization of the rest of the paper is as follows:

• In Section 2 we briefly discuss the notion of privacy in social networks and review some literature on privacy violating attacks on social networks. We also introduce the $\left(k,\mathrm{\ell }\right)$ -anonymity privacy measure and some corresponding network measurement which are the basis for this measure.

• In Section 3 we review some basic terminologies and notations that will be used in formulation of the three problems introduced in Section 4.

• Section 4 contains three problems that arise from theoretical investigation of the $\left(k,\mathrm{\ell }\right)$ -anonymity.

• Section 5 contains the results of an empirical study on the resistance of real-world social networks.

• Finally, we end this chapter with some concluding remarks in Section 6.

2. Privacy measures in social networks

We begin by discussing the mathematical structure that fit the most to represent social networks. A social network is often portrayed as a graph [7, 8] $G=\left(V,E\right)$ where V is a set of nodes representing the social members, and E is the set of edges portraying the relationship among these members. Both nodes and edges may have extra attributes, such as weights, that provide extra information about the nature of these social bonds (e.g., trust or popularity); however, throughout this survey we will consider the simplest form of graphs, namely undirected and unweighted graphs, to model our social networks.

As we discussed in the previous section, the information that the social networks provide are invaluable. Due to the very nature of many social network applications, the identity of the members or the nature of relationship between members is quite sensitive and valuable. Thus, when releasing a social network we want to remove any attributes that may help identify these kinds of sensitive data. Assuming all members and their relationships are of high sensitivity, preventing identity disclosure or link disclosure becomes an important task. One popular method to prevent such disclosures is anonymization. In an anonymization process, we publish the network without identifying the corresponding nodes or potentially identifiable attributes. Even after anonymizing the network, we will still be releasing many informative attributes encoded by the network structure; for example, attributes such as node degree, connectivity, or other similar graph properties can still help the adversaries in compromising the user privacies of a published network.

Adversaries usually rely on background knowledge to compromise the privacy of published anonymized social networks. For understanding the failure of current privacy preservation methods such as anonymization, we need to have a proper model for the adversary background knowledge. Although it’s challenging to have a comprehensive model of all possible types of adversary background knowledge, it is very useful to model the background knowledge via structural properties of networks such as node degrees, embedded subgraphs, node neighbors, etc. [9]. Backstrom et al. [10] were the first to introduce a category of attacks on anonymized social graphs. The models introduced in [10] are background-based attacks and are widely used in privacy analysis of social networks. The two main types of attacks are as follows.

1. Passive attacks in which the adversary will not modify the network by injecting new nodes, but instead will use the structural knowledge to detect the location of a known node. In this type of attacks, the adversary can benefit from the fact that most nodes in real social networks often belong to a small uniquely identifiable subgraph [10]. An adversary can then build a coalition with members of such subgraphs and attempt to re-identify the subgraphs in the anonymized published network, thus compromising the privacy of neighboring nodes.

2. Active attacks in which the adversary will choose an arbitrary set of target users, create new nodes and insert them into a social network in a way that they are connected to the target set and they form a distinguishable subgraph. After the anonymized version of the social network is published, the adversary can then use the subgraph as a fingerprint to re-identify the targeted users and compromise their privacy.

The authors in [10] also showed that it is possible to compromise the privacy of any social network of n nodes with high probability using only $O\left(\sqrt{logn}\right)$ attacker nodes. In a passive attack, adversary’s structural knowledge will give her/him a global view of the network depending on the global structure of the network. It could pose a high privacy risk if an adversary were to combine this global view with the local structural knowledge obtained using an active attack. As an example, consider the network in Figure 1. If we only have global structural knowledge, it is not possible to differentiate the nodes $v_3$ and $v_4$ (e.g. , same node degrees, etc.). However, controlling just one extra node in the graph, such as the node $v_1$ , provides local structural knowledge such as distances between nodes, and using the knowledge of the distance of $v_1$ from $v_3$ and $v_4$ ( $d_{v_1,v_3}=1$ and $d_{v_1,v_4}=2$ ) one can easily differentiate node $v_3$ from node $v_4$ .

Figure 1.

A simple graph G used in Section 2 to illustrate the high risk posed by combining knowledge gained by active and passive attacks.

There are several well-studied strategies for coping with active attacks on a social network [9, 11, 12] via addressing the anonymization process of the social network. However, in this chapter we will focus on a measure that evaluates how resistant a social network is against this type of privacy attack. Introduced by Trujillo-Rasua et al. [1], $\left(k,\mathrm{\ell }\right)$ -anonymity is a novel and, to the best of our knowledge, the only privacy measure examining the structural resistance of a given graph against active attacks. The $\left(k,\mathrm{\ell }\right)$ -anonymity is a measure based on metric representation of nodes, where k is a privacy threshold and l is the maximum number of attacker nodes that may be inserted in the network. It was shown in [1] that graphs satisfying $\left(k,\mathrm{\ell }\right)$ -anonymity can successfully deter adversaries controlling at most l nodes in the graph from re-identifying nodes with probability higher than $\frac{1}{k}$ .

2.1 $\left(k,\mathrm{\ell }\right)$ -anonymity

The $\left(k,\mathrm{\ell }\right)$ -anonymity measure is based on a concept known as k-metric anti-dimension of graphs. To facilitate further discussions about the measure, we first introduce some notations and terminologies. For a simple connected graph $G=\left(V,E\right)$ , where V is set of nodes and E is set of edges, let ${\mathit{\text{dist}}}_{v_i,v_j}$ denote distance (i.e. , number of edges in a shortest path) between the nodes $v_i$ and $v_j$ . Given and ordered set of nodes $S=\left\{v_1,\dots ,v_t\right\}$ and a node $u$ we define the metric representation of u with respect to S as a vector ${\mathbf{d}}_{u,-S}=\left({\mathit{\text{dist}}}_{u,v_1},\dots ,{\mathit{\text{dist}}}_{u,v_t}\right)$ . Metric representations of nodes are closely related to the concept of a resolving set of a graph. Inspired by the problem of identifying an intruder in a network and introduced separately by Slater [13] and by Harary and Melter [14], a resolving set of graph provides recognition of every pair of nodes in graph.

Definition 1 (resolving set). Given a graph $G=\left(V,E\right)$ , a subset $S\subseteq V$ is called a resolving set for G if, for each pair of nodes $\left(u,v\right)\in G$ , there exist a node $x\in S$ such that ${\mathit{\text{dist}}}_{x,u}\ne {\mathit{\text{dist}}}_{x,v}$ . A smallest-cardinality resolving set is called the metric basis, and its cardinality is referred to as the metric dimension of G.

The concepts of metric representation and resolving set inspired the introduction of another network measure known as k-antiresolving set that will be used as the founding base for $\left(k,\mathrm{\ell }\right)$ -anonymity.

Definition 2 (k-antiresolving set). Given a graph $G=\left(V,E\right)$ , $S\subset V$ is called a k-antiresolving set of G if k is the largest integer such that, for every node $v\in V\backslash S$ , there exist at least $k-1$ nodes $u_1,u_2,\dots ,u_{k-1}\in V\backslash S$ with the same metric representation with respect to S as $v$ .

A k-antiresolving set of minimum cardinality is called a k-antiresolving basis, and its cardinality denotes the k-metric antidimension ${\mathit{\text{adim}}}_k\left(G\right)$ of G. Note that the k-antiresolving set may not exist for every k in a graph.

The (k,l)-anonymity measure is built upon the k-antiresolving set concept. Assume the adversary has gained control of a subset S of nodes in the graph G, where S is a k-antiresolving set for G. Then the adversary cannot uniquely re-identify any node based on the background knowledge (namely, the knowledge of metric representation of a node $v$ with respect to S) with probability higher than $\frac{1}{k}$ . $\left(k,\mathrm{\ell }\right)$ -anonymity is formally defined as [1].

Definition 3 ( $\left(k,\mathrm{\ell }\right)$ -anonymity). A graph G under active attack satisfies $\left(k,\mathrm{\ell }\right)$ -anonymity if k is the smallest positive integer so that the k-metric antidimension of G is less than or equal to l.

In the above definition, k is a parameter depicting the privacy threshold and l represents the maximum number of attacker nodes. It is safe to assume that number of attacker nodes l is significantly smaller than number of nodes present in the network as injecting attacker nodes or gaining control of existing nodes is difficult without being detected [15].

3. Basic terminologies and notations

For the exposition in the remainder of this chapter, we will need some notations and terminologies which we introduce here. Consider the (undirected unweighted) graph G in Figure 2. We will use this graph to illustrate the terminologies and notations that are introduced.

• The metric representation of node $v_i$ is denoted by ${\mathbf{d}}_{v_i}=\left({\mathit{\text{dist}}}_{v_1,v_i},{\mathit{\text{dist}}}_{v_2,v_i},\dots ,{\mathit{\text{dist}}}_{v_n,v_i}\right)$ .

  • For example, in Figure 2, ${\mathbf{d}}_{v_1}=\left(\mathrm{0,1,2,3,3,2}\right)$

• The diameter of $G$ is the length of the longest shortest path and is denoted by $\mathit{\text{diam}}\left(G\right)={max}_{v_i,v_j\in V}\left\{{\mathit{\text{dist}}}_{v_i,v_j}\right\}$ .

  • For example, in Figure 2, $\mathit{\text{diam}}\left(G\right)=3$ .

• The open neighborhood of node $v_i$ is a subset of all nodes directly connected to $v_i$ and denoted by Nbr $\left(v_i\right)=\left\{v_j|\left\{v_i,v_j\right\}\in E\right\}$ .

  • For example, in Figure 2, Nbr $\left(v_2\right)=\left\{v_1,v_3,v_6\right\}$ .

• The metric representation of a node $v_i$ with respect to a subset such as $S\subset V$ is denoted by ${\mathbf{d}}_{v_i,-S}$ .

  • For example, in Figure 2, ${\mathbf{d}}_{v_1,-\left\{v_3,v_4\right\}}=\left(2,3\right)$ .

• We can expand the previous notation to reflect the metric representation of a subset of nodes $V^{\prime }\subset VS$ with respect to $S$ as ${\mathcal{D}}_{V^{\prime },-S}=\left\{{\mathbf{d}}_{v_l,-S}|v_l\in V^{\prime }\right\}$ .

  • For example, in Figure 2, ${\mathcal{D}}_{\left\{v_1,v_2\right\},-\left\{v_3,v_4\right\}}=\left\{\left(2,3\right),\left(1,2\right)\right\}$ . Note that the first pair (2,3) corresponds to $v_1$ and the second pair (1,2) corresponds to $v_2$ .

• We define a partition $\prod =\left\{V_1,V_2,\dots ,V_t\right\}$ of $V^{\prime }\subseteq V$ as one with the following properties:

  • ${\bigcup }_{i=1}^t{V}_i=V^{\prime }$ , and

  • for all $i\ne j$ , $V_i\cap V_j=\mathrm{Ø}$ .

• We define a refinement $\prod \text{'}=\left\{V_1^{\prime },V_2^{\prime },\dots ,V_{\mathrm{\ell }}^{\prime }\right\}$ of a partition $\prod$ , denoted by $\prod \text{'}{\prec }_r\prod$ , as one that can be obtained from $\prod$ using the following rules:

  • For every node $v_j\in \left({\bigcup }_{i=1}^t{V}_i\right)\backslash \left({\bigcup }_{i=1}^{\mathrm{\ell }}{V}_i^{\prime }\right)$ , remove $v_j$ from the set in $\prod$ that contains it.

  • Optionally, for every set $V_{\mathrm{\ell }}$ in $\prod$ , replace $V_{\mathrm{\ell }}$ by a partition of $V_{\mathrm{\ell }}$ .

  • If there exists an empty set, remove it.

  • For example, in Figure 2, $\left\{\left\{v_1,v_2\right\},\left\{v_3\right\},\left\{v_5\right\}\right\}{\prec }_r\left\{\left\{v_1,v_2\right\},\left\{v_3,v_4,v_5\right\}\right\}$ .

• We define an equivalence relation (and related notations) over set of same-length vectors ${\mathcal{D}}_{V\backslash V^{\prime },-V^{\prime }}$ for some $\mathrm{Ø}\subset V^{\prime }\subset V$ as follows:

  • The set _of equivalence classes, which forms a partition of ${\mathcal{D}}_{V\backslash V^{\prime },-V^{\prime }}$ , is denoted by ${\prod }_{V\backslash V^{\prime },-V^{\prime }}^{=}$

  • For example, in Figure 2, ${\prod }_{\left\{v_1,v_2,v_6\right\},-\left\{v_3,v_5\right\}}^{=}=\left\{\left(2,3\right),\left(1,2\right),\left(2,3\right)\right\}$ .

    • We declare two nodes $v_i,v_j\in V\backslash V^{\prime }$ to be in the same equivalence class if ${\mathbf{d}}_{v_i,-V^{\prime }}$ and ${\mathbf{d}}_{v_j,-V^{\prime }}$ belong to the same equivalence class in ${\prod }_{V\backslash V^{\prime },-V^{\prime }}^{=}$ ; thus ${\prod }_{V\backslash V^{\prime },-V^{\prime }}^{=}$ also defines a partition into equivalence classes of $V\backslash V^{\prime }$ .

    • The measure of the equivalence relation is defined as $\mu \left({\mathcal{D}}_{V\backslash V^{\prime },-V^{\prime }}\right)\stackrel{\mathrm{def}}{=}{min}_{y\in {\prod }_{V\backslash V^{\prime },-V^{\prime }}^{=}}\left\{|y|\right\}$ .

    • If a set $S$ is a $k$ -antiresolving set then ${\mathcal{D}}_{V\backslash S,-S}$ defines a partition into equivalence classes of measure $k$ .

  • For example, in Figure 2, $\mu \left({\mathcal{D}}_{\left\{v_1,v_2,v_6\right\},-\left\{v_3,v_5\right\}}\right)=1$ and $\left\{v_3,v_5\right\}$ is a 1-antiresolving set.

Figure 2.

An example used in Section 3 for illustrating various notations.

4. Theoretical results

To understand graph resistance against privacy attacks, one needs to study the $\left(k,\mathrm{\ell }\right)$ -anonymity in greater details. Thus, we look into some computational problems related to this measure that were formalized and investigated in [16]. This section contains three problems from [16] and the respective algorithms to solve each problem efficiently. It is important to note that $\left(k,\mathrm{\ell }\right)$ -anonymity in its basic definition sets no limitation for the adversary, which means that an adversary can take control of as many nodes as she/he can. However, in real world there are many mechanisms designed solely to prevent such attacks and thus the chances of being caught are significantly high. This notion is the motivation behind several problems with respect to measuring the $\left(k,\mathrm{\ell }\right)$ -anonymity in a graph [17].

We now state the three problems for analyzing $\left(k,\mathrm{\ell }\right)$ -anonymity. Problem 1 simply checks to find a k-antiresolving set for the largest possible value of k. Problem 2 sets a restriction for number of nodes the adversary can control and attempts to find the largest possible value of k while minimizing the number of nodes that are compromised. Problem 3 introduces a version of the problem that attempts to address the trade-off between privacy threshold and number of compromised nodes.

Problem 1 (metric antidimension (ADIM)). Find a k-antiresolving subset of nodes S that maximizes k.

Problem 1 assumes there are no limitations on the number of attacker nodes, thus finding an absolute bound for privacy violation. Note that solution to Problem 1, denoted by k_opt , shows that, given no bound on number of the nodes an adversary can control, it is feasible to uniquely re-identify k_opt nodes with probability $\frac{1}{k_{\mathit{opt}}}$ . The assumptions in Problem 1 are rarely plausible in practice; due to mechanisms present to counter such attacks, the more nodes the adversary controls, the higher the risk of being exposed. Thus, a limit on number of attacker nodes is necessary, which leads us to Problem 2.

Problem 2 ( $k_{\ge }$ -metric antidimension ( ${\mathit{\text{ADIM}}}_{\ge k}$ )). Given k, find a $k^{\prime }$ -antiresolving set S such that (i) $k^{\prime }>=k$ and, (ii) S is of minimum cardinality.

Problem 2 is an extension to Problem 1 that attempts to find the largest value of k while minimizing the number of attacker nodes. A solution to this problem asserts few interesting statements. For example, an adversary controlling l attacker nodes where $\mathrm{\ell }<\mid {\mathcal{L}}_{\mathit{opt}}^{\ge k}\mid$ cannot uniquely re-identify any node in the network with a probability better than $\frac{1}{k}$ . However, using enough number of nodes ( $\ge \mid {\mathcal{L}}_{\mathit{opt}}^{\ge k}\mid$ ) one can re-establish such possibilities.

The third problem focuses on a trade-off between number of attacker nodes and the privacy violation probability. Given two measures $\left(k,\mathrm{\ell }\right)$ -anonymity and $\left(k^{\prime },{\mathrm{\ell }}^{\prime }\right)$ -anonymity where $k^{\prime }>k$ and ${\mathrm{\ell }}^{\prime }<\mathrm{\ell }$ , it is easy to observe that $\left(k^{\prime },{\mathrm{\ell }}^{\prime }\right)$ -anonymity measure provides a smaller privacy violation probability but also has lower tolerance for attacker nodes. The trade-off leads us to the third problem.

Problem 3 (k=-metric antidimension ( ${\mathit{\text{ADIM}}}_{=k}$ )) Given a positive integer k, find a k antiresolving subset of nodes S with minimum cardinality if such a subset exists.

Chatterjee et al. [16] investigated Problems 1–3 from a computational complexity perspective. The following theorems summarizes their finding on Problems 1–3. The non-trivial mathematical proofs for these theorems are unfortunately outside of the scope of this chapter; we strongly recommend readers who are interested in the proofs to read the original paper [16].

Theorem 1. [16]

1. Both ADIM and ${\mathit{\text{ADIM}}}_{\ge k}$ can be solved in O $\left(n^4\right)$ time.

2. Both ADIM and ${\mathit{\text{ADIM}}}_{\ge k}$ can also be solved in O $\left(\frac{n^{4}logn}{k}\right)$ time with high probability.

Theorem 2. [16]

1. ${\mathit{\text{ADIM}}}_{=k}$ is NP-Complete for any $k$ in the range $1\le k\le n^{\epsilon }$ where $0\le \epsilon <\frac{1}{2}$ is any arbitrary constant, even if the diameter of the input graph is 2.

2. Assuming NP $⊈$ DTIME $\left(n^{loglogn}\right)$ , there exists a universal constant $\delta >0$ such that ${\mathit{\text{ADIM}}}_{=k}$ does not admit $\left(\frac{1}{\delta }lnn\right)$ approximation for any integer $k$ in the range $1\le k\le n^{\epsilon }$ for any constant $0\le \epsilon <\frac{1}{2}$ , even if the diameter of the input graph is 2.

3. If $k=n-c$ for some constant c then ${\mathit{\text{ADIM}}}_{=k}$ can be solved in polynomial time.

Theorem 3. [16]

1. ${\mathit{\text{ADIM}}}_{=1}$ admits $\left(1+ln\left(n-1\right)\right)$ approximation in $O\left(n^3\right)$ time.

2. If $G$ has at least one node of degree 1 then ${\mathit{\text{ADIM}}}_{=1}$ can be solved in $O\left(n^3\right)$ time.

3. If $G$ does not contain a cycle of 4 edges then ${\mathit{\text{ADIM}}}_{=1}$ can be solved in $O\left(n^3\right)$ time.

4.1 Algorithms

The following algorithms were devised in [16] to address Problems 1–3. It is important to note that $\mathit{\text{ADIM}}$ can be solved in $O\left(n^5\right)$ time by repeatedly solving ${\mathit{\text{ADIM}}}_{\ge k}$ for $k=n-1,n-2,\dots ,1$ to find the largest obtainable value for k such that ${\mathcal{L}}_{\mathit{opt}}^{\ge k}<\infty$ . However, few modifications to Algorithm 1 directly result in $O\left(n^4\right)$ solution, which is shown in Algorithm 2.

5. Empirical results

In [18], DasGupta et al. investigated the resistance of 8 real-world network against active attacks with respect to the $\left(k,\mathrm{\ell }\right)$ -anonymity. All the networks under investigation were unweighted graphs and the direction of edges (if the network was directed) was ignored during the analysis. Table 1 contains the general information regarding these networks. Results for both $\mathit{\text{ADIM}}$ and ${\mathit{\text{ADIM}}}_{\ge k}$ were obtained by running Algorithm 1 on the networks, the return statements from Algorithm 1 being an exact solution to Problem 2. On the other hand, the exact solution for Problem 1 can be achieved by combining Algorithm 1 and binary search on k to find the largest value of k such that $V_{\mathit{opt}}^{\ge k}\ne \mathrm{Ø}$ [18].

Name	Number of nodes	Number of edges	Description
Zachary Karate Club [20]	34	78	Network of friendship between 34 members of a karate club
San Juan Community [21]	75	144	Network for visiting relations between families living in farms in San Juan Sur, Costa Rica, 1948
Jazz Musician Network [22]	198	2842	A social network of jazz musicians
University Rovira i Virgili emails [23]	1133	10903	The network of email interchanges between members of university
Enron Email Data Set [24]	1088	1767	Enron email network
Email Eu Core [25]	986	24989	Emails from a large European research institute
UC Irvine College Message platform [26]	1896	59835	Messages on a Facebook-like platform at UC-Irvine
Hamsterster friendships [27]	1788	12476	Friendships between users of the website

Table 1.

List of 8 social networks studied in [18].

The results for both Problem 1 and Problem 2 for the networks in Table 1 are depicted in Table 2. Results in Table 2 provide the following interesting insights with respect to resistance against privacy attacks in real-world social networks [19].

• All networks, with the exception of ”Enron Email Data” network, will have a significant percentage of their users compromised if an adversary gains control of only one node (varying between 2.6% of users compromised in ”University Rovira i Virgili emails” network to 26.5% of users compromised in ”Zachary Karate Club” network).

• For all networks with the exception of ”Enron Email Data” network, the minimum privacy violation probability is notably higher than 0 (varying between 0.019 for the ”UC Irvine College Message platform” network to 0.25 for the ”Hamsterster friendships” network). The value for minimum privacy violation probability in ”Hamsterster friendships” network is notably higher compare to all other networks.

• In comparison to other networks, the ”Zachary Karate Club” and the ”San Juan Community” have higher percentage of their users compromised if subjected to a privacy attack.

Name	$n$	$k_{\mathit{opt}}$	$p_{\mathit{opt}}=\frac{1}{k_{\mathit{opt}}}$	${\mathcal{L}}_{\mathit{opt}}^{\ge k_{\mathit{opt}}}={\mathcal{L}}_{\mathit{opt}}^{=k_{\mathit{opt}}}$	$\frac{k_{\mathit{opt}}}{n}$
Zachary Karate Club [20]	34	9	0.111	1	26.5%
San Juan Community [21]	75	7	0.143	1	9.3%
Jazz Musician Network [22]	198	12	0.084	1	6.0%
University Rovira i Virgili emails [23]	1133	29	0.035	1	2.6%
Enron Email Data Set [24]	1088	153	0.007	935	14.1%
Email Eu Core [25]	986	39	0.026	1	3.4%
UC Irvine College Message platform [26]	1896	55	0.019	1	2.9%
Hamsterster friendships [27]	1788	4	0.25	1	0.22%

Table 2.

Results for ADIM using Algorithm 1 [18].

^a

n denotes the number of nodes in the social graph.

^b

k_opt is the largest value of k such that $V_{\mathit{opt}}^{\ge k}\ne \mathrm{ø}$ .

$n$ depict the number of nodes, $k_{\mathit{opt}}$ is the largest value of $k$ such that $V_{\mathit{opt}}^{\ge k}\ne \mathrm{ø}$ , and ${\mathcal{L}}_{\mathit{opt}}^{\ge k_{\mathit{opt}}}$ is minimum number of attacker nodes for corresponding k.

The exception network is the “Enron Email Data” network which due to a high value of ${\mathcal{L}}_{\mathit{opt}}^{\ge k}$ is very resilient against an attack. An adversary needs to control at least 86% of the network to achieve a value of $p_{\mathit{opt}}=0.007$ , which is not feasible in practice. This interesting observation in the “Enron Email Data” network motivated further inspections in different values of $k$ . As shown in Table 3, ${\mathcal{L}}_{\mathit{opt}}^{\ge k}$ in the “Enron Email Data” network does not decrease significantly until k is set to a much smaller value compare to $k_{\mathit{opt}}$ , which further emphasizes that violating the privacy of the “Enron Email Data” network is not guaranteed in practice. The authors in [18] also investigated the $\left(k,\mathrm{\ell }\right)$ -anonymity measure in synthetic networks constructed based on both Erdös-Rényi random graphs and Barabási-Albert scale-free networks. We refer the reader to the original paper for more information.

	k	4	5	10	20	40	60	100	120	153
Enron Email Data Set	$p_k=\frac{1}{k}$	0.25	0.2	0.1	0.05	0.025	0.017	0.01	0.009	0.007
	${\mathcal{L}}_{\mathit{opt}}^{\ge k}$	1	334	463	567	683	842	935	935	935

Table 3.

${\mathcal{L}}_{\mathit{opt}}^{\ge k}$ values recorded for $k>1$ for the “Enron Email Data” network [18]. The values shown are subject to ${\mathcal{L}}_{\mathit{opt}}^{\ge k}\ne {\mathcal{L}}_{\mathit{opt}}^{\ge k-1}$ .

6. Conclusions

Since their emergence about a decade ago, social networks have rapidly grown and infiltrated every aspect of our daily lives. With rapidly expanding reliance on their platforms, social networks like Facebook and Twitter are becoming a goldmine of personal information and user behavior data which makes the study of these networks of prime importance. The valuable information stored within these platforms makes them the target of malicious entities which try to compromise the privacy of the users which may further lead to unwanted disclosure of the sensitive attributes of the network.

In this chapter, we have reviewed a novel privacy measure that quantifies the resistance of a large social network against a privacy violating attack. We reviewed some efficient algorithms to compute this measure in social graph and revisited the privacy violation properties in 8 real-world networks. The current theoretical and empirical results for $\left(k,\mathrm{\ell }\right)$ -anonymity pave the way for further investigation of this measure, as well as addressing its shortcomings and limitations.

Acknowledgments

We thank Ismael G. Yero for useful discussions. This research was partially supported by NSF grants IIS-1160995 and IIS-1814931.