# Privacy Preservation of User History Graph

Shinsaku Kiyomoto, Kazuhide Fukushima, Yutaka Miyake

► To cite this version:

Shinsaku Kiyomoto, Kazuhide Fukushima, Yutaka Miyake. Privacy Preservation of User History Graph. 6th International Workshop on Information Security Theory and Practice (WISTP), Jun 2012, Egham, United Kingdom. pp.87-96, 10.1007/978-3-642-30955-7_9. hal-01534302

HAL Id: hal-01534302

https://inria.hal.science/hal-01534302

Submitted on 7 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Privacy Preservation of User History Graph

Shinsaku Kiyomoto¹, Kazuhide Fukushima¹, and Yutaka Miyake¹

KDDI R & D Laboratories Inc.
2-1-15 Ohara, Fujimino, Saitama, 356-8502, Japan
kiyomoto@kddilabs.jp

**Abstract.** In this paper, we propose new ideas to protect user privacy while allowing the use of a user history graph. We define new privacy notions for user history graphs and consider algorithms to generate a privacy-preserving digraph from the original graph.

## 1 Introduction

Graph-structured data are useful for the analysis of relationships and trends of service use [6, 4], and has been considered an analysis tool for a commercial services [10]. Graph-structured data sets are collections of user history data, which are anonymous, but contain sensitive information with implications for user privacy. A privacy concern for leakages of user history data has been reported [11]. Privacy-preserving analysis of such graphs remains a continuing concern as interest in the areas of privacy and data mining increases.

Current research focuses mainly on social network graphs without directed edges. In a social network graph, the anonymity of each node is important for privacy protection. How to obfuscate the relationships between users and nodes is the main issue for existing privacy protection mechanisms for graphs. A method [13] proposed by Yuan et al. constructs a *k*-degree anonymous graph by adding nodes and edges. In the *k*-degree anonymous graph, the probability that an attacker cannot identify a node of the target user is at most $\frac{1}{k}$. Several studies have examined [5, 7, 3] methods that use secret graph data and respond to queries with approximate results. Blaustein et al. formalized the problem of creating a protected account *G'* of a graph *G* and provided an algorithm [2] to create a maximally useful protected account of a sensitive social network graph. In the article [15], *k*-automorphism is proposed: *k*-automorphism requires that each node has at least *k* − 1 other nodes with the same structure in a published graph. Some other techniques for protecting privacy in social networks have been proposed [12, 14]. Privacy preserving data mining methods for link analysis of directed graphs was presented in [8, 1].

In this paper, we propose new privacy notions for user history graphs and consider algorithms to generate a privacy-preserving digraph from the original graph. We assume that the user history graph is published and used for several analyses using non-interactive schemes. The notions are similar in approach to *k*-anonymity [9], and they are configured by two parameters *k* and *v*.
<figure><img src="image_2.png" /><figcaption>Fig. 1. Example of Merged History Graph</figcaption></figure>

The rest of the paper is organized as follows; user history graphs are explained in section 2. Section 3 provides privacy notions for user history graphs and section 4 presents algorithms for privacy-preserving graph data. Evaluation results of the algorithms are shown in section 5. We conclude this paper in section 6.

## 2 User History Graph

A history graph as shown in figure 1 is an efficient method to visualize the history of a user. We define a label for each edge to merge the history graphs of all users. A user history graph showing that users perform action *a* and then *b* is transformed into a labeled digraph (*a* → *b*): the label $L(a \to b)$ denotes the number of users who perform the action from *a* to *b*. For simplicity in the definition, we assume that the user does not repeat his previous actions, even though our discussion in this paper can be applied to that case. First, a history for each user is transformed into a labeled digraph such that the label is $L(a \to b) = 1$. Then, digraphs of all users are merged as follows;

- all nodes that denote the same action are merged into one node.

- The labels are updated to $L(a \to b) = n$, where digraphs of *n* users have the same label $L(a \to b) = 1$.

Note that the digraph ($a \to b$) is different from the digraph ($b \to a$), so the label is defined for each digraph.

Let *start* be a group of nodes that the number of outgoing edges for a node is larger than the number of incoming edges for the node and *end* be a group of nodes the number of incoming edges for a node is larger than the number of outgoing edges for the node. The symbol $start \to x$ denotes the routes from the nodes *start* to *x*, and the symbol $x \to end$ denotes the routes from *x* to the *end* nodes. The symbols $N_{start \to t}$ and $N_{t \to end}$ respectively denote all nodes on all possible routes from $start \to t$ and all nodes on all possible routes from $t \to end$, where the symbol $N_x$ denotes a group of nodes that satisfy the condition *x*. If $start = \emptyset$, $N_{start \to t}$ consists of all nodes that can be reached from node *t* to trace the digraph backwards. For $end = \emptyset$, $N_{t \to end}$ consists of all nodes that can be reached from node *t* to trace the digraph forwards. The symbol $\emptyset$ denotes an empty set. For the merged history graph in figure 1, $N_{start \to d}$ is the set of nodes $\{a, b\}$, and $N_{d \to end}$ is the set of nodes $\{e, f, h\}$.
# 3 Privacy Notion

## 3.1 Adversary Model

Privacy leakage from a merged history graph is the disclosure of the actions of a particular person from the graph. Attacks against user history graphs are intended to obtain private information on a particular user from the graph. We assume that the merge process is executed on a trusted domain and only the merged history graph is published. We summarize an adversary model as follows:

*Adversary against a Merged History Graph.* It is assumed that an adversary knows a victim *A* executed an action *t*. The objective of the adversary is to obtain actions that *A* executed before or after the action *t*. Thus, the adversary searches the merged history graph that includes actions of other people and finds actions of *A* using the knowledge that action *t* was executed.

## 3.2 Notions for Untraceability of Graph

We consider two levels of privacy notions: partial *k*-untraceability, and complete *k*-untraceability. Partial *k*-traceability accepts leakage of some partial actions of a user, but prevents all actions of the user from being revealed. The definition of complete *k*-untraceability involves meeting the requirement that no action of the user is leaked. The symbol $Act_{N_{x \to y}}^A$ for user *A* denotes the sequence of all actions of user *A* from action *x* to action *y*. For example, the sequence of actions from the first action to action *x* and the sequence of actions from action *x* to the final action are denoted $Act_{N_{start \to x}}^A$ and $Act_{N_{x \to end}}^A$, respectively.

Generally, there are many trivial actions, performed by many users. It is not important for privacy purposes where we keep the information about such actions. Thus, we relax the above definitions to produce an anonymized graph that includes a lot of information for analyses of user history. Let *v* be the threshold value for the number of performing users that establishes that an action is trivial, that is, we judge the actions $x \to y$ to be trivial if the label $L(x \to y) \ge v$. Both definitions are denoted as follows:

**Definition 1.** *Partial (k, v)-untraceability.* We assume that an adversary knows an action *t* of a user *A*, and we consider all possible adversaries defined for any *t* in the merged graph. If at least *k* sequences of actions that are potentially associated with the user *A* and *k* − 1 other users exist as candidates respectively for all actions $Act_{N_{start \to t}}^A$ and $Act_{N_{t \to end}}^A$, except trivial actions $x \to y$ that have a label $L(x \to y) \ge v$, it is said that the digraph satisfies partial (k, v)-untraceability for *A*. If the digraph satisfies the above condition for all users, the digraph is said to satisfy partial (k, v)-untraceability.

**Definition 2.** *Complete (k, v)-untraceability.* We assume that an adversary knows an action *t* of a user *A*, and we consider all possible adversaries defined for any *t* in the merged graph. If at least *k* actions that are potentially associated with the user *A* and *k* − 1 other users exist as candidates for each action in $Act_{N_{start \to t}}^A$ and $Act_{N_{t \to end}}^A$, except trivial actions $x \to y$ that have a label
$L(x \to y) \ge v$, it is said that the digraph satisfies complete $(k, v)$-untraceability for $A$. If the digraph satisfies the above condition for all users, the digraph is said to satisfy complete $(k, v)$-untraceability.

In a complete $(k, v)$-untraceable graph, each action $t$ except trivial actions has $k$ outgoing edges and incoming edges; thus, an action of the user $A$ which connects to the action $t$ cannot be identified from $k$ candidates. Thus, the graph satisfies untraceability for the adversary who knows the action $t$ of the user. It is trivial that a complete $(k, v)$-untraceable graph satisfies partial $(k, v)$-untraceability; all actions except trivial actions are connected to $k$ potential actions in a complete $(k, v)$-untraceable graph. A graph that satisfies partial $(k, v)$-untraceability generally produces much information than a complete $(k, v)$-untraceable graph, where the partial $(k, v)$-untraceable graph and the complete $(k, v)$-untraceable graph are generated from a user history graph. However, the $(k, v)$-untraceable graph may reveal partial actions of users due to the relaxed definition of the privacy notion; an attack is successful where an adversary obtains all actions of a user. To trace all actions of the user, the adversary has to select a sequence of actions from $k$ sequences of actions; thus, all actions of the user is untraceable, even though some actions are treaceable for the adversary. The parameter $k$ means that an action (or a sequence of actions) is potentially associated with a user and $k-1$ other users in the untraceable graph, and the parameter $v$ means that $v$ users do the same action in the graph. Generally, we should select the parameter $v=k$ with regards to a privacy requirement for a merged graph. Actions of a user are hidden in actions of a group that consists of $k$ members including the user. A privacy notion for the graph should be selected from the above two notions according to a use case of the graph and its privacy requirements. Tradeoffs between privacy and the amount of information that is provided by the untraceable graph will be evaluated in section 6.

# 4 Algorithm

## 4.1 Algorithm generating partial $(k, v)$-untraceable history graph

Details of the algorithm are denoted as **Algorithm 1**, where $oe_t$ and $ie_t$ are respectively defined as the number of outgoing edges and incoming edges of a node $t$. The algorithm to generate a partial $(k, v)$-untraceable history graph is as follows.

1. This step consists of a part of the detailed algorithm, from line 1 to line 3. For input of a user history graph $G$, the algorithm adds a virtual incoming edge $(s_r \to r)$ to each node $r \in \text{start}$ until the number of the incoming edges is the same as the number of outgoing edges. Then, the algorithm adds a virtual outgoing edge $(q \to u_q)$ to each node $q \in \text{end}$ until the number of the outgoing edges is the same as the number of incoming edges. A label of a virtual incoming edge $L(s_x \to x)$ denotes the number of users who first do the action, and a label of a virtual outgoing edge $L(y \to u_y)$ denotes the number of users who do the action at the end.
2. This step consists of a part of the detailed algorithm, from line 4 to line 12. The algorithm searches for a node *t* that has fewer outgoing edges than *k* and for which all lower nodes $N_{t \to end \setminus t}$ have fewer outgoing edges than *k*. Then, the algorithm removes all outgoing edges (*t* → *) that satisfy $L(t \to *) < v$. Next, the algorithm searches for a node *t'* that receives incoming edges numbering less than *k* and all upper nodes $N_{start \to t' \setminus t'}$ that receive fewer incoming edges than *k*. Then the algorithm removes all incoming edges (* → t') that satisfy $L(* \to t') < v$. The algorithm repeats this step until no node that meets the conditions has found.

3. This step is the same as line 13, line 14 and line 15 in the detailed algorithm. The algorithm removes virtual incoming and outgoing edges, removes nodes that has no edges, and outputs the modified graph.

<caption>**Algorithm 1** Generation of a Partial (*k*, *v*)-Untraceable History Graph</caption>

**Input:** User History Graph G, parameters *k* and *v*
**Output:** Anonymized Graph $G^\alpha(G, k, v)$
1: $G^\alpha(G, k, v) \leftarrow G$
2: Add virtual incoming edges to *start* nodes
3: Add virtual outgoing edges to *end* nodes.
4: $T \leftarrow$ all nodes *t*, where $\text{oe}_{N_{t \to end}} < k$ and its all edges are not $L(t_i \to *) \ge v$
5: $T' \leftarrow$ all nodes $t'$, where $\text{ie}_{N_{start \to t'}} < k$ and its all edges are not $L(* \to t'_j) \ge v$
6: **while** $T \ne \emptyset$ or $T' \ne \emptyset$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;Choose $t_i$ from *T*
8: &nbsp;&nbsp;&nbsp;&nbsp;Remove all outgoing edges of $t_i$, where $L(t_i \to *) < v$ from $G^\alpha(G, k, v)$
9: &nbsp;&nbsp;&nbsp;&nbsp;Choose $t'_j$ from $T'$
10: Remove all incoming edges of $t'_j$, where $L(* \to t'_j) < v$ from $G^\alpha(G, k, v)$
11: Update *T* and $T'$
12: **end while**
13: Remove virtual edges
14: Remove all node $t''$ where $\text{oe}_{t''} = 0$ and $\text{ie}_{t''} = 0$ from $G^\alpha(G, k, v)$
15: **return** $G^\alpha(G, k, v)$

**Example.** We show an example of the execution for the merged history graph in figure 2, where we set $k = v = 2$. The algorithm checks whether each node satisfies the condition for outgoing edges which is described in the step 2, and find that the nodes *h* and *g* satisfy the condition. Because, the nodes {*a*, *d*, *e*, *f*} have two outgoing edges, and the nodes *b* and *c* have edges $L(b \to c) = 2$, $L(c \to d) = 2$, respectively. Then, the outgoing edges (*g* → *h*) and (*h* → *u*<sub>*h*</sub>) are removed. The algorithm has no node that satisfy the condition for incoming edges which is described in the step 2. Note that the incoming edge (*s*<sub>*a*</sub> → *a*) satisfies $L(s<sub>*a*</sub> → *a*) \ge 2$. The algorithm removes virtual edges from the graph, and then the algorithm removes the node *h* that has no connection with other nodes. Thus, the output of the algorithms for the example graph is the graph including seven nodes as described in figure 2.

Any adversary who knows an action of a user cannot find sequences of all actions of the user from the output of **Algorithm 1**. For example, if an adversary knows that a user do the action *g*, there exist at least two possible sequences of the actions, (*a* → *d* → *f* → *g*) and (*a* → *d* → *e* → *f* → *g*).
**Computational Cost.** We estimate the computational cost of the algorithm 1. Let $E$ and $N$ be the total number of edges in the graph and the total number of nodes in the graph. The cost of line 1 is $O(1)$. The computational cost from line 2 to line 5 is $O(N + E)$. Lines 6 to 12 require $O(N^2 + NE)$ computation and lines 13 and 14 require $O(N)$ computation, respectively; thus the total cost from line 1 to line 14 can be estimated as $O(N^2 + NE)$. Where the graph is a dense graph ($E = O(N^2)$), the computational cost is $O(N^3)$.

## 4.2 Algorithm generating complete $(k, v)$-untraceable history graph

Details of the algorithm are denoted as **Algorithm 2**. The algorithm to generate a complete $(k, v)$-untraceable history graph is as follows;

1. The algorithm first executes **Algorithm 1** except line 13 and line 15.

2. This step consists of a part of the detailed algorithm, from line 3 to line 11. The algorithm searches for a node $t$ that has fewer outgoing edges than $k$ and removes all outgoing edges ($t \to $*) that satisfy $L(t \to $*) < $v$, until no node is found. Then, the algorithm searches for a node $t'$ that receives fewer incoming edges than $k$ and removes all edges ($* \to t'$) that satisfy $L(* \to t') < $v. The algorithm repeats this step until no node that meets the conditions has found.

3. This step consists of line 12, line 13, and line 14 in the detailed program. The algorithm removes virtual edges, removes nodes to which no edge is connected, and outputs the modified graph.

**Example.** An example of the output by **Algorithm 2** is shown in figure 2. We set $k = v = 2$. After the step 1, the algorithm checks whether each node satisfies the conditions described in the step 2, and find that the node $g$ satisfies the condition for incoming edges, because the node $g$ has a incoming edge of $L(f \to g) = 1$. Then, the incoming edge ($f \to g$) is removed. Next, the algorithm finds the node $f$ satisfies the condition for outgoing edges, and removes the virtual edge ($f \to u_f$). In the final step, the virtual edges are removed from the graph, and then the node $f$ that has no edge is removed.

Any adversary who knows an action of a user cannot find any action of the user from the output of **Algorithm 2**. For example, if an adversary knows that a user does the action $e$, the adversary knows a trivial action $d$, and possible actions $\{a, b, c\}$ that are potentially associated with other users.

**Computational Cost.** We can calculate the total computational cost of **Algorithm 2** in the same manner. The total computational cost is estimated as $O(N^3)$.

# 5 Evaluation

We implemented a prototype module for **Algorithm 1** and **Algorithm 2**, and evaluated the transaction time for generating an anonymized history graph on a
<caption>**Algorithm 2** Generation of a Complete $(k, v)$-Untraceable History Graph</caption>

**Input:** User History Graph $G$, parameters $k$ and $v$
**Output:** Anonymized Graph $G^\alpha(G, k, v)$
1: $G^\alpha(G, k, v) \leftarrow G$
2: Execute **Algorithm 1** except line 13 and 15
3: $T \leftarrow$ all nodes $t$, where $oe_t < k$ and its all edges are not $L(t_i \to *) \ge v$
4: $T' \leftarrow$ all nodes $t'$, where $ie_{t'} < k$ and its all edges are not $L(* \to t'_j) \ge v$
5: **while** $T \ne \emptyset$, or $T' \ne \emptyset$ **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;Choose $t_i$ from $T$
7: &nbsp;&nbsp;&nbsp;&nbsp;Remove all outgoing edges of $t_i$, where $L(t_i \to *) < v$ from $G^\alpha(G, k, v)$
8: &nbsp;&nbsp;&nbsp;&nbsp;Choose $t'_i$ from $T'$
9: &nbsp;&nbsp;&nbsp;&nbsp;Remove all incoming edges of $t'_j$, where $L(* \to t'_j) < v$ from $G^\alpha(G, k, v)$
10: &nbsp;&nbsp;&nbsp;&nbsp;Update $T$ and $T'$
11: **end while**
12: Remove vertical edges
13: Remove all node $t''$ where $oe_{t''} = 0$ and $ie_{t''} = 0$ from $G^\alpha(G, k, v)$
14: **return** $G^\alpha(G, k, v)$

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Outputs of Algorithms</figcaption></figure>

PC (Core i7 2.93GHz, 4.00GB Memory). We randomly generated merged user history graphs in two steps. In the first step, we generated a merged user history graph of $n$ nodes under the condition that the probability of node connection $L(a, b) = 1$ was $p$; we first obtained an $n$-node merged graph where all labels are $L(a, b) = 1$. Then, we randomly assigned $n^{1/2}$ actions of $10 \times n^{1/2}$ users to digraphs and updated the labels in the graph. The data format described a user history graph $a \xrightarrow{L(a,b)} b$ as a tuple of three data $\{a, b, L(a, b)\}$.

**Performance.** The evaluation results of the average transaction time for 20 graphs are summarized in table 1 and table 2. The tables show the transaction time of **Algorithm 1** and **Algorithm 2**, respectively. We examined two different probabilities of node connections with five patterns of $k$. We set $v = k$ for all experiments. The transaction time depends on the number of processed nodes that are input into $T$ and $T'$, and the number of processed nodes is configured
<table><caption>**Table 1.** Transaction Time of Partial $(k, v)$-Untraceable History Graph Generation</caption><thead><tr><th>(second)</th><th>100 nodes</th><th>150 nodes</th><th>200 nodes</th><th>300 nodes</th><th>400 nodes</th><th>500 nodes</th><th>700 nodes</th><th>1000 nodes</th><th>1500 nodes</th><th>2000 nodes</th></tr></thead><tbody><tr><td>p=0.01, k=2</td><td>0.01</td><td>0.01</td><td>0.03</td><td>0.07</td><td>0.08</td><td>0.14</td><td>0.21</td><td>0.27</td><td>0.67</td><td>1.04</td></tr><tr><td>p=0.01, k=5</td><td>0.01</td><td>0.04</td><td>0.21</td><td>0.52</td><td>1.03</td><td>1.67</td><td>2.98</td><td>4.32</td><td>10.80</td><td>19.22</td></tr><tr><td>p=0.01, k=10</td><td>0.01</td><td>0.07</td><td>0.36</td><td>2.33</td><td>6.51</td><td>17.85</td><td>24.45</td><td>30.99</td><td>62.06</td><td>138.72</td></tr><tr><td>p=0.01, k=20</td><td>0.01</td><td>0.07</td><td>0.38</td><td>2.34</td><td>6.82</td><td>14.27</td><td>42.79</td><td>128.22</td><td>425.58</td><td>834.59</td></tr><tr><td>p=0.01, k=30</td><td>0.01</td><td>0.07</td><td>0.39</td><td>2.39</td><td>6.37</td><td>14.66</td><td>41.41</td><td>127.87</td><td>424.65</td><td>931.05</td></tr><tr><td>p=0.1, k=2</td><td>0.01</td><td>0.01</td><td>0.01</td><td>0.02</td><td>0.03</td><td>0.06</td><td>0.11</td><td>0.23</td><td>0.55</td><td>0.97</td></tr><tr><td>p=0.1, k=5</td><td>0.01</td><td>0.02</td><td>0.03</td><td>0.06</td><td>0.13</td><td>0.21</td><td>0.52</td><td>1.08</td><td>3.31</td><td>7.53</td></tr><tr><td>p=0.1, k=10</td><td>0.06</td><td>0.12</td><td>0.19</td><td>0.52</td><td>1.16</td><td>2.12</td><td>5.42</td><td>14.27</td><td>46.89</td><td>109.14</td></tr><tr><td>p=0.1, k=20</td><td>0.18</td><td>0.55</td><td>1.41</td><td>4.35</td><td>9.41</td><td>18.11</td><td>43.58</td><td>113.71</td><td>305.10</td><td>622.19</td></tr><tr><td>p=0.1, k=30</td><td>0.18</td><td>0.55</td><td>1.32</td><td>4.32</td><td>10.32</td><td>19.46</td><td>51.51</td><td>146.82</td><td>472.82</td><td>1039.43</td></tr></tbody></table>

<table><caption>**Table 2.** Transaction Time of Complete $(k, v)$-Untraceable History Graph Generation</caption><thead><tr><th>(second)</th><th>100 nodes</th><th>150 nodes</th><th>200 nodes</th><th>300 nodes</th><th>400 nodes</th><th>500 nodes</th><th>700 nodes</th><th>1000 nodes</th><th>1500 nodes</th><th>2000 nodes</th></tr></thead><tbody><tr><td>p=0.01, k=2</td><td>0.01</td><td>0.02</td><td>0.04</td><td>0.09</td><td>0.14</td><td>0.18</td><td>0.27</td><td>0.50</td><td>1.14</td><td>1.80</td></tr><tr><td>p=0.01, k=5</td><td>0.01</td><td>0.06</td><td>0.22</td><td>0.61</td><td>1.10</td><td>1.98</td><td>4.19</td><td>6.25</td><td>13.26</td><td>23.81</td></tr><tr><td>p=0.01, k=10</td><td>0.01</td><td>0.07</td><td>0.43</td><td>2.40</td><td>6.35</td><td>17.27</td><td>26.19</td><td>32.87</td><td>68.87</td><td>138.77</td></tr><tr><td>p=0.01, k=20</td><td>0.01</td><td>0.08</td><td>0.43</td><td>2.43</td><td>6.98</td><td>14.75</td><td>42.81</td><td>128.02</td><td>427.77</td><td>885.70</td></tr><tr><td>p=0.01, k=30</td><td>0.01</td><td>0.08</td><td>0.42</td><td>2.38</td><td>6.48</td><td>14.27</td><td>41.89</td><td>128.13</td><td>425.65</td><td>936.94</td></tr><tr><td>p=0.1, k=2</td><td>0.01</td><td>0.01</td><td>0.02</td><td>0.04</td><td>0.07</td><td>0.11</td><td>0.22</td><td>0.41</td><td>0.97</td><td>1.61</td></tr><tr><td>p=0.1, k=5</td><td>0.02</td><td>0.03</td><td>0.05</td><td>0.10</td><td>0.18</td><td>0.32</td><td>0.67</td><td>1.37</td><td>4.17</td><td>8.32</td></tr><tr><td>p=0.1, k=10</td><td>0.07</td><td>0.13</td><td>0.21</td><td>0.57</td><td>1.18</td><td>2.19</td><td>5.54</td><td>14.56</td><td>51.84</td><td>109.92</td></tr><tr><td>p=0.1, k=20</td><td>0.18</td><td>0.56</td><td>1.39</td><td>4.32</td><td>9.42</td><td>18.01</td><td>45.52</td><td>114.35</td><td>305.09</td><td>787.99</td></tr><tr><td>p=0.1, k=30</td><td>0.17</td><td>0.54</td><td>1.31</td><td>4.31</td><td>10.07</td><td>19.49</td><td>51.21</td><td>148.97</td><td>473.55</td><td>1040.19</td></tr></tbody></table>

by values of $k$, $v$ and the number of nodes in the merged user history graph; thus, the transaction time was increased according to increases of $k(= v)$ and the number of nodes of the original graphs. A dominant part of the transaction time of Algorithm 2 is the transaction time of Algorithm 1, where $k$ is large; it is expected that many nodes are removed by Algorithm 1, and edges of almost all nodes are removed at the first iteration of the *do-while-loop* in the Algorithm 2. Example cases of $k = v = 10$ for Algorithm 1 (denoted P) and Algorithm 2 (denoted C) are shown in figure 3. The transaction time is approximately proportional to $N^3$.

**Tradeoff.** We evaluated the number of nodes that were outputs of algorithms, where we changed parameters $k$ and $v$. Evaluation results are shown in figure 4. The evaluation results denote reductions of information that is provided by $(k, v)$-untraceable history graph, where a privacy requirement is tightened. We used random graphs of $n = 1000$ and $p = 0.01$, and evaluated three cases: $k$ was fixed ($k = 10$) and $v$ was changed, $k$ and $v$ were changed ($k = v$), and $k$ was changed and $v$ was fixed ($v = 10$). For both partial $(k, v)$-untraceable history graphs and complete $(k, v)$-untraceable history graphs, a result in the case $v = 10$ was almost same as that in the case $k = v$. Changes of the parameter $v$ did not affect partial $(k, v)$-untraceable history graphs, but strongly affected complete $(k, v)$-untraceable history graphs. In any of the cases, there are threshold values for parameters $k$ and $v$; the number of nodes is dramatically reduced, where $k$ and $v$ is increased over the threshold values. Thus, we should choose appropriate values for parameter sets, $k$ and $v$ in an operation of each history graph, even though there is a tradeoff between privacy and the amount of infor-
<figure><img src="image_4.png" /><figcaption>Fig. 3. Transaction Time of Algorithms ($k = 10$)</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4. Number of Nodes for Each Parameters $k$ and $v$</figcaption></figure>

mation. Especially, the partial $(k, v)$-untraceable history graph is useful since it
holds almost nodes and the graph is close to the original random graph, where
$k$ and $v$ are small.

# 6 Conclusion

In this paper, we have presented concrete algorithms for generating graph data that satisfies the notions. Furthermore, experimental results for performance and tradeoff analyses of the algorithms have been presented.

The extension of the adversary model remains an open issue for our future
work. We will consider an adversary who knows an action for a fraction of users in
the merged history graph and an adversary who knows some continuous actions
of a user in the graph, and effects of the extended adversary models will be
analyzed. We will also evaluate the feasibility of graphs using real data.
**Acknowledgement.** The authors would like to thank anonymous reviewers and program committee members for useful comments on an earlier version of this manuscript.

**References**

1. Hiromi Arai and Jun Sakuma. Privacy preserving semi-supervised learning for labeled graphs. In *Machine Learning and Knowledge Discovery in Databases*, volume 6911 of LNCS, pages 124–139. 2011.

2. B Blaustein, A. Chapman, L. Seligman, M. D. Allen, and A. Rosenthal. Surrogate parenthood: Protected and informative graphs. In *Proc. of the 37th International Conference on Very Large Data Bases*, VLDB '11, pages 518–527, 2011.

3. M. Hay, C. Li, G. Miklau, and D. Jensen. Accurate estimation of the degree distribution of private networks. In *Proc. of the 2009 9th IEEE International Conference on Data Mining*, ICDM '09, pages 169–178, 2009.

4. J. Heer, J. Mackinlay, C. Stolte, and M. Agrawala. Graphical histories for visualization: Supporting analysis, communication, and evaluation. *IEEE Transactions on Visualization and Computer Graphics*, 14(6):1189–1196, 2008.

5. V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev. Private analysis of graph structure. In *Proc. of the 37th International Conference on Very Large Data Bases*, VLDB '11, pages 1146–1157, 2011.

6. T. Kurashima, K. Bessho, H. Toda, T. Uchiyama, and R. Kataoka. Ranking entities using comparative relations. In *Proc. of 19th International Conference on Database and Expert Systems Applications*, DEXA '08, pages 3124–133, 2008.

7. V. Rastogi, M. Hay, G. Miklau, and D. Suciu. Relationship privacy: output perturbation for queries with joins. In *Proc. of the 28th ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems*, PODS '09, pages 107–116, 2009.

8. J. Sakuma and S. Kobayashi. Link analysis for private weighted graphs. In *Proc. of the 32nd international ACM SIGIR conference on Research and development in information retrieval*, pages 235–242. 2009.

9. P. Samarati and L. Sweeney. Generalizing data to provide anonymity when disclosing information. In *Proc. of the 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems (PODS'98)*, page 188, 1998.

10. TWIMPACT UG. TWIMPACT. http://twimpact.com/, 2011.

11. Z. Weinberg, E.Y. Chen, P.R. Jayaraman, and C. Jackson. I still know what you visited last summer: Leaking browsing history via user interaction and side channel attacks. In *2011 IEEE Symposium on Security and Privacy*, pages 147–161, 2011.

12. X. Ying and X. Wu. Randomizing social networks: a spectrum preserving approach. In *Proc. of the 8th SIAM Conference on Data Mining*, SDM'08, pages 739–750, 2008.

13. M. Yuan, L. Chen, and P.S. Yu. Personalized privacy protection in social network. In *Proc. of the 37th International Conference on Very Large Data Bases*, VLDB '11, pages 141–150, 2011.

14. B. Zhou and J. Pei. Preserving privacy in social networks against neighborhood attacks. In *Proc. of the 24th International Conference on Data Engineering*, ICDE'08, pages 506–515, 2008.

15. L. Zou, L. CHen, and M. T. Özsü. k-automorphism: a general framework for privacy preserving network publication. In *Proc. of the 35th International Conference on Very Large Data Bases*, VLDB '09, pages 946–957, 2009.