The growing need to address privacy concerns when social network data is released for mining purposes has recently led to considerable interest in various techniques for graph anonymization. In this paper, we study the following problem: Given a social network modeled as an {em edge-labeled graph} $G$, we aim to make a pre-specified subset of vertices of $G$ $k$-label sequence anonymous with the minimum number of edge additions. Here, the label sequence of a vertex is the sequence of labels of edges incident to it. The contributions of this paper are two fold: We provide a framework to show hardness results for different variants of social network anonymization using a common approach. We start by showing that $k$-label sequence anonymity of arbitrary labeled graphs is hard, and use this result to prove NP-hardness results for many other recently proposed notions of graph anonymization. Secondly, we present interesting algorithms and hardness for bipartite graphs. For unlabeled bipartite graphs, we show $k$-degree anonymity is in P for all $k geq 2$. For labeled bipartite graphs, we show that $k$-label sequence anonymity is in P for $k=2$ but it is NP-hard for $k geq 3$.
展开▼
机译：当社会网络数据被释放以进行采矿目的时，越来越多的需要解决私有网络数据，最近导致了对图形匿名化的各种技术的相当兴趣。在本文中，我们研究了以下问题：给定像{EM Edge标记图} $ G $的社交网络，我们的目标是使预先指定的V $ $ K $ -Label序列匿名具有最小数量的边缘添加。这里，顶点的标签序列是事件的边缘标签序列。本文的贡献是两倍：我们提供了一个框架，以显示使用共同方法的社交网络匿名变种的不同变体的硬度。我们首先显示任意标记图的$ k $ -label序列匿名是很难的，并且使用此结果来证明NP-Hardense结果对图表匿名的许多其他最近提出的概念。其次，我们呈现有趣的算法和二分图的硬度。对于未标记的二角形图形，我们显示$ k $ -degree匿名是在p的所有$ k geq 2 $的p中。对于标记的二分图，我们显示$ k $ -label序列匿名在p for $ k = 2 $，但它是$ k geq 3 $的np-hard。
展开▼
