社会网络子集 θ, k ?材涿?方法
中图分类号： TP393.08
文献标志码：A
（θ，k）anonymous method in the subsets of social networks
ZHANG Xiaolin， WANG Ping， GUO Yanlei， WANG Jingyu
School of Information Engineering， Inner Mongolia University of Science and Technology， Baotou Nei Mongol 014010， China
Abstract： Focusing on the issue that the current related research about social network do not consider subsets for neighborhoods privacy preserving， and the specific properties of neighborhood subsets also lead individual privacy disclosure， a new （θ， k）anonymous model was proposed. According to the kisomorphism ideology， the model removed labels of neighborhood subsets which needed to be protected in social network， made use of neighborhood component coding technique and the method of node refining to process nodes in candidate set and their neighborhood information， then completed the operation of specific subsets isomorphism with considering the sensitive attribute distribution. Ultimately， the model satisfies that each node in neighborhood subset meets neighborhood isomorphism with at least k-1 nodes， as well the model requires the difference between the attribute distribution of each node in the neighborhood subset and the throughout subsets is not bigger than θ. The experimental results show that， （θ， k）anonymous model can reduce the anonymization cost and maximize the utility of the data.
Key words： social network； subset of neighbourhood； distribution of attribute； kisomorphism； （θ， k）anonymous model
0引言
近年，随着信息技术的飞速发展，在线社区和社会网络的数量与日俱增，如Facebook、Twitter、mySpace、ParentsLikeMe等被人们广泛应用进行社交活动。科学家、在线营销公司和贸易商等能够通过对这些社交网络的分析获得无可估量的目标人口的信息。但是，随着对这些信息的挖掘，用户的隐私也被暴露。
结构和属性是社会网络中个体所具有的性质。个体的结构包括：度、邻域和子图。个体的属性包括敏感属性和非敏感属性。为防止个体结构被识别，文献[1]基于动态规划思想设计了一个算法来处理原始图使之产生了一个k度匿名图。Chester等文献[2]考虑实际社会网络中基于度约束的社会网络子集匿名问题，设计了一个算法产生kdegreesubset匿名图。由于社会网络中每个节点的相邻节点度信息也易造成泄露，文献[3]提出了一种整数规划构想来寻找最优解，设计了kldegree anonymity算法。度的攻击是一种最简单的结构攻击，不足以面对攻击者更复杂的背景知识挑战。基于自同构的AKSecure隐私保护模型[4]有效地解决了攻击者同时拥有节点、边、路径长度等更加复杂的背景知识而造成的隐私泄露问题。文献[5]介绍了一个新的隐私攻击模型，即相同朋友攻击，攻击者可以通过他们所拥有的共同朋友而重识别出这对朋友；而且为了解决该问题，文献中还提出了一个新的匿名模型观念，即kNMF匿名，解决了之前关于自同构模型中在多个朋友之间的边未被保护这一问题。 为防止敏感属性泄露，文献[6-7]在构建k度序列的基础上将l多样性运用进去保护节点属性或连边关系属性。Zhou等文献[8]针对社会网络个体邻域攻击和敏感属性攻击问题，设计了适用于社会网络的k匿名算法和l多样性匿名算法。文献[9]展示了社交网络中个体子集及相应的属性隐私需要被保护的这一迫切现状。文献[10]对不同准标识符属性泛化路径设置不同的权重，满足特定领域内对于匿名数据的分析。Li等文献[11]介绍了tcloseness模型，该模型要求每个k匿名等价类内部属性值的分布应当接近整个表的属性值分布；但是此模型不能被很好地应用到社会网络图中。
由于社会网络子集度的隐私保护不足以应对攻击者拥有更加复杂的背景知识这一情形，并且社会网络中不同群体有不同的隐私保护需求，相应的攻击者有不同的背景知识。本文根据这一现状提出一种（θ， k）匿名模型。该模型根据k匿名要求完成目标节点的k邻域同构操作，在匹配邻域组件的同时考虑目标节点邻域子集的属性分布，使得每个节点在其对应的直接邻域子集的属性分布值接近其在整个子集中的分布，最终得到满足（θ， k）匿名模型的社会网络子集匿名图。
1相关定义及概念
社会网络通常以无向图的形式表示：1）社会网络中的个体都是同一类型的；2）社会网络中个体与个体间的连边关系是同一类型的并且边是无标签无权重的。
定义1节点带有标签的社会网络。节点带有标签的社会网络G由一个5元组表示，其表示形式为G=（V， E， L， lv， T）。其中：
V={（vi， ti）}（i=1，2，…，n； t∈T）表示节点集；
E={（vi， vj）}（i， j=1，2，…，n）表示边集；
L表示标签集，是节点的属性的集合，为便于理解和表示，将节点的属性用字母表中有序的字母元素代替；
lv表示节点标签函数，即节点到其标签的映射；
T={{p11，p12，…，p1n }，{p21，p22，…，p2n }，…，{pn1，pn2，…，pnn }}表示节点标签中属性类型，其中pi1，pi2，…，pin表示第i个节点的属性集；
节点vi表示社会网络中的个体，边（vi， vj）表示vi和vj之间存在关系。
经过简单地移除节点属性标签，形成社会网络简单匿名图，如图1所示。
定义2社会网络子集。给定一个节点带有标签的社会网络，即G=（V， E， L， lv， T），其子集为G′=（V′， E′， L′， lv′， T′）。其中：V′V， E′E， L′L， lv′lv， T′T。
例1如图1所示中，黑色节点为社会网络子集。
定义3一个节点的直接邻域[8]。一个节点vi∈V的直接邻域是vi的邻居的导出子图，通常用NeighborG（vi）=G（Nvi） 表示，其中Nvi={vj|（vj， vi）∈E， i≠j}。
因此，一个节点的邻域子集即一个节点ui∈U的直接邻域NeighborG（ui）=G（Nui），ui直接邻域子集是NeighborSubG（ui）=G（NSui），即NeighborSubG （ui）NeighborG （vi），其中NSui={uj | （uj， ui）∈Es， i≠j， ui∈U， uj∈U， UV， EsE}。
文献[8]按照深度优先搜索树的方式对社会网络中各个节点进行直接邻域组件编码（Neighborhood Component Code， NCC），用NCC（vi）表示，则针对子集中每个节点的邻域信息，邻域子集组件编码（Neighborhood Subset Component Code， NSCC），即NSCCs（ui）也同样适用。
定义4邻域子集组件同构。对于社会网络子集G中的两个节点uj，ui∈U，当其最小邻域子集组件编码NSCCs（uj）和NSCCs（ui）相等时，直接邻域子集NeighborSubG（uj）和NeighborSubG（ui）是同构的。
对于一个特定节点，其属性标签序列是其本身及其朋友的属性标签的集合。
定义5一个节点的邻域子集属性标签序列。一个节点ui∈U的邻域子集属性标签序列用ηs（ui）表示，是一个由ui的邻域子集的属性标签序列组成的节点集合，即ηs（ui）={ui}∪{uj∈U：（uj， ui）∈Es}。
定义6域子集属性标签分布。对于UV，用number（li， U）代表在节点集U中属性标签为li的节点的数目。属性标签在U上的分布用distrs（U）表示，即向量distrs（U）=[number（l1， U），number（l2， U），…，number（lL， U）]/|U|。其中：li表示一个特定属性标签， number（li， U）/|U|表示一个特定属性标签的分布，作为向量中的一个元素。
通过两个分布distrs（Ui）和distrs（Uj）来定义一个距离测量：
定义7两个邻域子集属性标签分布间的距离。两个邻域子集属性标签分布间的距离σ（distrs（Ui），distrs（Uj）），即它们对应元素间差值的和，其中不包括最后元素之间的差。
例2两个邻域子集标签分布分别为〈0.6， 0.2， 0.2〉和〈0.3， 0.4， 0.1〉，则其距离为0.3+0.2=0.5。
定义8属性分布θ接近性（θcloseness）。当一个节点ui∈U的邻域属性标签分布满足σ（distrs（ηs（ui））， distrs（U））≤θ，其中UV，则此节点ui被认为是θ接近性。如果在UV中的每一个节点的邻域子集是θ接近性，则这个带属性标签的社会网络子集GsG是θ接近性的。
2（θ， k）匿名模型 社会网络子集中攻击者通过结构信息背景知识进行隐私攻击。最简单的结构信息如度信息，通常的保护策略是构造原始目标节点的k度序列以防止节点被识别。然而攻击者一旦拥有更复杂的结构背景知识时，例如：节点及其邻域信息，k度匿名方法将不足以解决隐私泄露问题。对于一个给定的敏感属性，其在一个特定的邻域子集中的分布与在整个提取的子集中的分布有极大的不同时，会造成一定的隐私泄露危险，因为攻击者能够得知一个目标节点的邻域子集属性标签分布值。为此根据前面给出的定义和概念提出（θ， k）匿名模型，该模型满足社会网络子集中任意一个节点至少有k-1个与其邻域同构的节点存在，即每个节点及其直接邻域子集节点形成的度序列是相同的。在邻域同构的同时考虑每个节点的属性标签在总的社会网络子集中的分布值接近于其在直接邻域子集中的分布值，即满足θ接近性。
3（θ， k）匿名算法
3.1邻域攻击问题
如图1所示，此简单的匿名社会网络图满足2度子集匿名，但是，若攻击者有更复杂的背景知识，则此网络的某些个体隐私仍面临泄露危险。例如：假设一个属于社会网络中提取的子集中的一成员Lily，她在此子集内部好友的个数为3，并且其中两个好友是另一个好友的共同好友，因此攻击者可通过此描述抽象出一子图，如图2所示为图1中子集U中节点的各个邻域子集组件。E3及其1邻域的子图为其中组件之一。经过查询图1后得知E3满足假设要求，并且唯一存在。因此通过E3的邻域子集识别出E3节点。
本文模型考虑一个节点的直接邻域，即1邻域，ui∈U（UV）的直接邻域子集是NeighborSubG（ui）=G （NSui），即NeighborSubG（ui）NeighborG（ui）。将一个节点的直接邻域用节点及其邻域子集度序列表示。在一个社会网络G中，一个节点ui和其直接邻域子集NeighborSubG（ui）中的各个节点的度构成的序列称为节点及其邻域子集度序列。
如图2所示中，E1及其邻域子集度序列为（4， 3， 2， 2， 1）。
3.2邻域同构
针对上述社会网络子集中邻域攻击问题，基于k同构思想，设计算法使得社会网络子集满足邻域同构要求，对其进行匿名保护。
步骤如下：
1）提取社会网络中需要被保护的子集及其每个节点的直接邻域。在社会网络图G中，节点vi的邻域组件由若干个最大连接子图构成，为了编码整个邻域，首先编码每一个邻域组件，采用最小深度优先搜索树（Depth First Search tree， DFStree）编码节点和边，得到最小深度优先搜索树组件编码各个集合，比较各个子集的邻域组件大小，对节点直接邻域组件编码集合，即NCC（vi）进行排序，合并所有的最小邻域组件的深度优先搜索编码为一个编码。
2）将节点集分组，在同一个小组中匿名节点集的邻域子集。通过以上编码确定了节点集UV及其各个节点的邻域子集组件集合NSCC（ui），分别将NSCC（ui）中的邻域组件量化，将其放在一个哈希映射容器中，其中key值存子集中的目标节点对象，将目标节点及其直接邻域子集节点度值和节点信息封装成一个对象放在value中。
3）利用动态规划思想计算每个节点及其邻域子集度序列之间的差值，为了最小化匿名代价，取差值最小的放入候选集Cw中进行同构操作。
3.3属性泄露
属性泄露指一个攻击者通过识别带属性标签的社会网络子集中一个节点ui∈U的标签序列，获得关于ui的子集的属性标签序列的背景知识。
不仅获取到标签为li的其属性概率为number（li， U）/|U|，而且获知上述概率值接近于邻域子集属性概率number（li， ηs（ui））/|ηs（ui）|。
由此可产生邻域子集属性标签泄露攻击。根据前文定义可知，一个邻域子集属性标签泄露攻击指一个攻击者发现节点ui∈U的在整个子集的属性标签分布值distrs（U）（UV）更为精炼的估计值，即其邻域子集的属性标签分布值distrs（ηs（ui））。因此攻击者的背景知识可为σ（distrs（U）， distrs（ηs（ui）））。
如图3所示，提取出的子集（黑色节点）中各个节点的标签中的属性，根据k匿名思想泛化后的属性用图中小写字母标识，对于属性泛化标识为a在整个子集中的概率分布为05。属性泛化标识为b的3个节点对应的邻域子集属性序列为（b， a， a， a），（b， a， a），（b， a）。如果一个攻击者知道a在这三个节点对应的邻域子集中的概率分布分别是（075， 067， 0.5），由此可见仅有第三个节点的邻域子集的标识a和标识a在整个网络中的分布一样，其他两个节点有可能隐私被泄露。
3.4属性分布值满足θ接近性实现思路
3.2节在进行邻域同构的过程中计算邻域子集中的各个节点属性值分布性，通过增加边集使得其满足属性分布接近性，即θcloseness。如图4所示通过添加边（E2， E4），属性标识为b的节点对应的邻域子集属性序列为（a， a， b， b， b），（a， a， b， b），（a， b），可计算属性标识b的节点对应的邻域子集中的概率分布分别是（0.6， 0.5， 0.5）和原始b的概率分布接近。属性标识为b的3个节点对应的邻域子集属性序列为（b， b， a， a， a），（b， b， a， a），（b， a），可计算属性标识a在这3个节点对应的邻域子集中的概率分布分别是（0.6， 0.5， 0.5），和原始a在整个子集中的概率分布接近。
图4（0.1，2）匿名模型的社会网络子集匿名图
实现θ接近性（θcloseness）的边的添加策略：
1）将在候选集中的各个邻域子集组件依据属性标签值类别进行分类。
2）优先在属性标签相同的节点之间添加边，其次选取属性不同的节点之间进行添加。 为解决以上由于属性分布情况和邻域造成隐私泄露这一问题，最小化匿名代价和图修改，形成了如图4所示的（0.1，2）匿名模型的社会网络子集匿名图。
3.5匿名代价
匿名代价相关的概念和计算方式：
1）一个邻域子集匿名组代价。基于节点精炼方法[12]思想，降序构建每个节点及其邻域子集对应的度序列NSD1u[d1i， d1j]， NSD2u[d2i， d2j]，…，NSDnu[dki， dkj]，里面对应的所有节点i， i+1，…，j是在同一个邻域子集中的度值，CNDA（NSDxu[dxi， dxj]， NSDyu[dyi， dyj]）是此匿名组的代价。
【邻域度匿名（Neighborhood Degree Anonymization）
CNDA（NSDxu[dxi，dxj]，NSDyu[dyi，dyj]）=∑yy=x{NSDxu[dxi，dxj]-NSDyu[dyi，dyj]}
（1）
2）为了实现对社会网络子集原始图邻域同构和θcloseness，通过插入边的数量来度量发布匿名图的匿名代价。匿名代价是指原始图G的候选集中的每个节点的代价之和：
Cost（G）∑|U|nu=1Cost（Cand（unu））
（2）
根据动态规划思想中的动态规划方程式如下：
当nu<2k时：
Cost（Cand（unu））=CNDA（NSD1u[d1i，d1j]，NSDnuu[dnui，dnuj]）
（3）
当nu≥ 2k时：
Cost（Cand（unu））=mink≤t≤nu-k{CNDA（NSD1u[d1i，d1j]，NSDtu[dti，dtj]）+CNDA（NSDt+1u[d（t+1）i，d（t+1）j]，NSDyu[dyi，dyj]）}
（4）
3.6匿名算法
基于以上讨论，对于社会网络子集邻域及其节点属性泛化标识导致的隐私泄露，设计了（θ， k）匿名模型，并设计了相应的算法。
算法描述如下：
输入社会网络原始图G=（V， E， L， Lv， T），UV，整数k，θ；
输出满足k邻域子集_θcloseness社会网络匿名图G*。
程序前
4实验与分析
4.1实验环境
实验的硬件环境为：CPU Intel Core i5 （3.2GHz），内存8GB，操作系统为64位的Windows 7，实验工具为Eclipse 4.3.2，JDK 6.0。实验测试所用数据集分别是：TeleContact稀疏图数据集，该数据集中包含204个节点和401条边；Speed Dating稠密图数据集，该数据集包含552个节点和8388条边。
4.2实验说明
本实验选取两个数据集进行测试，分别从这两个数据集中提取需保护的部分节点子集，设计5组实验。
第一组实验
测试参数θ与边改变率的关系。实验中对TeleContact和Speed Dating数据集分别令θ=0.05， 0.1， 0.15， 0.2， 0.25， 0.3，k=5，子集|U|变化的数量为分别为10， 20， 30， 40， 50，结果如图5、6所示。从图中可以看出，随着θ增大，原始图边的改变率呈现下降趋势。正如前文的定义可知，随着θ的增加需要添加更少的边。当θ取非常小的一些值时，趋势线又突然下降并且此后变化相对较小，说明对于TeleContact和Speed Dating数据集，分别当θ=0.1和θ=015时可以实现较好的匿名。
第二组实验
通过计算满足（θ， k）匿名模型所需添加的边占原始边的比率来衡量（θ， k）匿名模型算法和经典的k邻域同构算法各自的匿名代价，添加边的比率越小，匿名代价越小。实验中对TeleContact数据集分别令k=2， 4， 6， 8， 10，θ=0.1，子集|U|=0.7|V|；对Speed Dating数据集分别令k=5， 10， 15， 20， 25，θ=0.15，子集|U|=0.7|V|，结果如图7、8所示。从图中可以看出，利用（θ， k）匿名算法对原始图添加的边数比k邻域同构算法少，即匿名代价小；且（θ， k）匿名算法对原始图的修改更少，即图的完整性更高。
第三组实验
运用度分布变化率来衡量本文模型对原始图度分布的改变情况，用原始图的度分布和发布图的度分布之间的地球移动距离（Earth Mover Distance， EMD）[13]来代表度分布的变化，以此观察匿名算法对原始图数据的效用。EMD越大，说明度分布改变的越大，数据损失率越大，匿名效果更高；同理，EMD越小，说明度分布改变的越小。实验中对TeleContact数据集分别令k=2， 4， 6， 8， 10， θ=0.1，子集|U|=0.5|V|；对Speed Dating数据集分别令k=5， 10， 15， 20， 25，θ=0.15，子集|U|=0.5|V|，结果如图9、10所示。从图中可以看出，（θ， k）匿名算法与已有k邻域同构算法相比，添加了最少的边，降低了匿名成本且最大化数据效用。
第四组实验
对两个数据集上的算法执行效率进行测试比较。实验中对TeleContact和Speed Dating数据集分别令k=2， 4， 6， 8， 10，子集|U|=05|V|，TeleContact数据集的θ=0.1，Speed Dating数据集的θ=0.15，结果如图11、12所示。从图中可以看出，随着k值的升高，算法执行时间有所增长，但（θ， k）匿名模型算法较经典的k邻域同构算法执行效率高。 第五组实验
通过聚类系数（Clustering Coefficient， CC）来测量（θ， k）匿名算法和k邻域同构算法对原始图数据匿名后数据的有效性。在无向网络中通常把聚类系数定义为表示一个图中节点聚集程度的系数，且CC=n/C2k，其中n表示在节点v的所有k个邻居间边的数量。实验中对TeleContact数据集分别令k=2， 4， 6， 8， 10，θ=0.1，子集|U|=0.5|V|；对Speed Dating数据集分别令k=5， 10， 15， 20， 25，θ=0.15，子集|U|=0.5|V|。如图13所示在匿名的数据中，随着k值的增加聚类系数略微下降；然而，此匿名图的聚类系数仍然相当接近原始数据值，当k=10时，原始图数据和匿名图数据的聚类系数之差仅为0.06。如图14所示，（θ， k）匿名算法较k邻域同构算法聚类系数高，对原始图改变略少。
5结语
本文针对社会网络中目标个体邻域子集结构和属性泄露问题，定义了社会网络子集（θ， k）匿名模型，该模型基于k同构思想可有效抵抗拥有社交网络中节点的直接邻域子集结构攻击；同时定义一个测量标准即属性分布θ接近性来抵抗属性泄露攻击，设计实现了（θ， k）匿名算法。通过在不同真实社会网络数据集上的测试分析，结果表明该算法相比经典k邻域同构算法不仅考虑了攻击者背景知识的复杂性和多样化，而且匿名代价有所降低，减少了信息缺损率，执行效率和数据可用性上得到明显提高。
