社交网络数据发布的混合随机化隐私保护方法

摘要

社交网络数据发布的混合随机化隐私保护方法，是把表示社交网络数据的无向图G（V,E）的顶点V，以k-匿名为条件，按照度的数量分为两个集合Vk和Vr，Vk中包含度的数量满足k-匿名条件的点；Vr中包含不满足k-匿名条件的点；对Vk集合中的点不做处理；对Vr集合中的点进行随机化保护处理。该方法将现有的k-匿名法和随机化的方法结合，不改变社交网络用户数目，对提供给第三方的数据的性质和质量影响较小，处理过程简单，速度快。经过处理后，社交网络数据中每个个人数据会处于两种保护状态之一：度属性没有改变，处于至少k个和他的度属性相同的其他个人之中；或度属性改变。这种保护能够阻止采用结构背景知识的重定位攻击，满足社交网络用户对隐私安全的需求。

说明书

技术领域

本发明涉及数据安全领域，具体是网络数据中隐私的保护技术，更具体是社交网络数据发布的混合随机化隐私保护方法。

背景技术

随着网络信息技术的发展，互联网已经渗入到我们生活的各个方面。社会网络服务如：新浪微博、QQ空间、人人网、淘宝网、LinkedIn和Google+等大量出现。社会网络的出现，改变了我们同朋友的联系方式，拓展了我们的交际范围，提供了更加直接快速的信息交流和传播方式。随着智能手机、平板及可穿戴智能设备的普及，人们在线的时间越来越多，提供给网络的数据越来越详细，互联网将逐步和现实世界产生融合。使用这些社会网络服务给我们生活带来极大的便利，同时也产生了大量的有关我们个人信息的数据如年龄、性别、爱好、照片、位置等，其中有些是我们不想让他人知道的个人隐私的信息。但是这些数据是存放在社会网络服务提供商处的，由于科研、商业，或是政府的要求，服务商会把他们所收集的数据发布给第三方使用。如果发布数据不当，将会泄露用户的个人隐私信息。如果个人隐私被泄露，将会带来不可估量的损失。因此迫切需要一种安全的社会网络数据发布方法，在保护个人隐私数据安全的情况下，尽可能大的保持原始数据的可用性，满足第三方对社会网络数据的分析研究和其他方面的需求。

社交网络数据，由于其关系复杂性，一般用图数据结构表示。对这些数据发布前需进行隐私保护处理，目前主要使用k-匿名的隐私保护方法、以k-匿名为基础的l-不同、t-接近等方法。这些方法其核心思想都是把个体隐藏在群体中，以不可区分性来保护个体的隐私。这些已有方法为了隐藏个体标识信息，通过添加虚拟用户，虚拟关系等方式对原始数据进行更改，对原始数据改变较大，对数据的可用性有较大影响。

发明内容

本发明的目的是提供一种社交网络数据发布的混合随机化隐私保护方法。

本发明是针对社交网络图数据的结构属性进行保护的。社交网络数据发布前，首先进行初步匿名工作，去掉姓名，身份证等显式的标识符并分离一般属性和结构属性，一般属性如年龄、爱好、地区等采用二维表表示，结构属性采用无向图G（V,E）表示，他们之间的联系用重新编号的标识符表示，其中V是顶点的有限集合，表示社交网络中的个人或其他实体；E是V上的二元关系，即用户或实体间的关系，如朋友、同学、共同爱好等关系，也叫做一条边，每个顶点的度表示与该顶点相关的二元关系的个数，即边的数量。经过上述处理的数据，能够有效防止攻击者使用背景知识，如某个用户朋友列表，对这个用户在发布的数据中重新定位。

本发明的方法的具体步骤如下：

1）把无向图G（V,E）的顶点V，以是否满足k-匿名为条件分为两个集合V_k和V_r，V_k中存放满足k-匿名条件的点；V_r中存放不满足k-匿名条件的点；

2）对V_k，由于满足k-匿名不需要继续处理；对Vr集合中的点进行下述处理：

3）随机选择重复次数n； 

4）对于Vr中点，随机的（等概率的）在原来没有边的两点间添加m条边，然后再随机在原来有边的顶点间去掉m条边。

5）依次检测Vr中点的度，删除Vr中度有变化的点； 

6）n=n-1

7）如果重复次数n大于零且Vr非空，转到步骤4）；否则转到步骤8）。

8）判读Vr中的点是否为奇数，如果为奇数转步骤9），否则转步骤10）。

9）在Vr中随机选择两点，如果他们间有边就去掉这条边，否则在他们之间增加一条边。在Vr中移除这两点中的一点。

10）对于Vr中的点，随机选择两两组合，如果他们间原本有边就去掉边；原本没有边添加一条边；

11）结束；

在步骤1），k-匿名条件的k值范围为2~20，,由用户根据需求选择，优选为10。

在步骤3），随机数n范围为：1~10。

在步骤4），m为：10~100%Vr中包含的点，优选为：20~40%Vr中包含的点。

本发明的方法是将已有技术中的k-匿名法和改变度属性的方法进行结合，并对原有的改变度属性的方法进行改进，不会影响提供给第三方的数据的性质和质量，也不改变数量，处理过程简单，速度快。

经过上述处理后，将数据进行发布或提供给第三方使用，这样，社交网络数据中每个个人数据就会处于两种保护状态之一：1.度属性没有改变，处于至少k个和他的度属性相同的其他个人之中；2.度属性改变。

处于状态1的个人数据，攻击者根据背景信息只能定位到至少k个体；

处于状态2的个人数据，攻击者根据背景信息不能够确定攻击目标。

本方法能够很好的保护社交网络参与者的个人隐私信息，这种保护能够阻止采用结构背景知识的重定位攻击。本发明结合已有技术的方法思想，在个体标识信息隐藏过程中结合随机换的概率思想，规避掉个体标识信息必须成组的复杂问题，巧妙而有效的的解决了社交网络数据发布的隐私保护问题。

    附图说明

图1是本发明方法的具体流程图。

具体实施方式

测试数据集采用Facebook的朋友圈数据集，下载地址：http://snap.stanford.edu/data/ 。数据集经过处理，包含534位有朋友的用户和3466条朋友关系。

参照图1，按照本发明的方法，首先进行初步匿名工作，去掉显式的标识符如姓名，身份证等，并分离一般属性和结构属性，一般属性如年龄、爱好、地区等采用二维表表示，结构属性采用无向图G（V,E）表示，他们之间的联系用重新编号的标识符表示，其中V是顶点的有限集合，表示社交网络中的个人或其他实体；E是V上的二元关系，即用户或实体间的关系，如朋友、同学、共同爱好等关系，也叫做一条边，每个顶点的度表示与该顶点相关的二元关系的个数，即边的数量。

然后，选择k=5，完成步骤1）后Vk中包含480个点，Vr中包含54个点。

然后，对V_k中的点不作处理；对Vr中的点进行下述处理：

在步骤3）随机选择重复次数n如n=1，

步骤4）中取m为50% Vr中包含的点，则m为27， 

完成步骤5）有45个点的度发生改变，9个点的度没有变，删除这45个度有变化的点；

步骤6）n的值减少1，变为0，由于n不大于0（等于0），按照步骤7）转到步骤8），

由于Vr中的点是9，为奇数，所以转到步骤9），在这9个点中，随机选择两点，如果它们间有边就去掉这条边，否则在他们之间增加一条边，之后在移除这两点中的一点；Vr中顶点数又减少了一个，变成8个，为偶数。

之后按照步骤10）随机选择两两组合，如果它们间原本有边就去掉边，原本没有边添加一条边，完成整个处理过程。