专利摘要

本发明公开一种优化的社交网络图数据发布隐私保护方法，其首先将社交网络的数据抽象为无向图，并将该无向图生成度序列；然后对度序列进行分组，构建出匿名度序列；最后再对匿名度序列进行增加边和增加顶点的处理，使社交网络数据中每个个人或团体数据都具有至少k和他属性相同的其他个人或团体，攻击者根据背景信息只能定位到至少k个体，能够很好的保护社交网络参与者的个人或团体隐私信息；本方法由于其高效性，能够适用于大规模的社交网络数据隐私保护处理。此外，本方法对于数据重构处理的信息损失量也较小。

权利要求

1.一种优化的社交网络图数据发布隐私保护方法，其特征是包括如下步骤：

(1)将社交网络的数据抽象为无向图G(V，E)，其中V是顶点的有限集合、表示社交网络中的个人或团体，E是V上的二元关系、表示社交网络中的关系；

(2)计算无向图G(V，E)中每个顶点的度d_i，其中度d_i表示与第i个顶点相关的二元关系的个数，其中i＝1，2，……，n，其中n为顶点的个数；

(3)对无向图G(V，E)中的所有度d_i进行排序，获得度序列d_G，其中d_G＝(d₁，d₂，……，d_n)，且d₁≥d₂≥……≥d_n；

(4)用户根据隐私数据的敏感程度自行设定所需达到匿名度k的值，并对度序列d_G进行匿名度操作，构建出匿名度序列d_G’；即

(4.1)从度序列d_G中的d₁开始，计算度序列d_G中两两相邻度的差值，即︱d_j-d_j+1︱，并记录首次遇到的最大差值对应的j；

(4.2)调整j的值，以确保每个分组至少有k个元素,即将j与k进行比较，若j≥K，则将第j个元素作为分组的结束点，若j＜K，则将第k个元素作为分组的结束点；

(4.3)以第j+1位度作为新分组的起点；

(4.4)重复步骤(4.1)-(4.3)，即重复寻找新分组的起点和计算差值的过程，直至将度序列d_G中的所有新分组的起点都找出，由此将度序列d_G中的度d_i划分为多组，此时带有分组信息的度序列d_G即为构建出的匿名度序列d_G’；

(5)针对匿名度序列d_G’的每组分组中的度d_i’，计算其与同分组中第一个度值间的差值x_i，其中x_i代表这个顶点要达到匿名所需的边数，并把所有x_i不为0的点放在集合V_d中；

(6)在集合V_d中搜索添加匿名所需的边，其条件为在无向图G(V，E)中两个顶点之间不能够有边，每添加一条边，对应的两个顶点的匿名所需的边数x_i都减少1，当某个顶点的x_i为0时，表示此顶点满足匿名需求，将该顶点移出集合V_d；

(7)重复步骤(6)添加边的步骤；如果能够使集合V_d为空，则认为该组匿名度序列d_G’已经完成匿名无向图G’(V’，E’)的构建，此时输出匿名度序列d_G’所对应的匿名无向图G’(V’，E’)；如果集合V_d不为空，则需要对V_d集合中剩余的未匿名顶点进行步骤(8)的添加新顶点的步骤；

(8)计算剩余集合V_d中所有顶点到达匿名度k所需的最大边数t，并添加t个新顶点，选择集合V_d’中的第一个顶点，根据前面计算出的这个顶点匿名所需边数x_i，建立这个点同x_i个新增加点间的边，这个顶点匿名完成，将该顶点移出集合V_d；

(9)重复步骤(8)添加边的步骤，直至集合V_d为空，完成构建匿名无向图G’(V’，E’)的工作；此时输出匿名度序列d_G’所对应的匿名无向图G’(V’，E’)。

2.根据权利要求1所述的一种优化的社交网络图数据发布隐私保护方法，其特征是，步骤(4)中所述匿名度k的值在小于需匿名图数据即无向图G(V，E)的顶点数的条件下，在2～200之间选择。

说明书

技术领域

本发明涉及社交网络信息发布安全领域，具体涉及一种优化的社交网络图数据发布隐私保护方法。

背景技术

近年来伴随着互联网的高速发展，社交网络产品，如Facebook、Twitter、微信、微博、开心网等，同个人生活联系越来越密切。有关个人的信息在网络上更加丰富和完整，虚拟世界同现实世界逐渐出现了交叉。用户在使用社交网络服务时会产生大量的有关个人隐私的数据，这些数据由于政府监管、商业目的或是研究的需要将会提供给第三方使用。但如果直接对这些数据进行发布，会造成大量的个人隐私泄露。因此在发布前需要对这些数据进行隐私保护处理。

名词解释

定义1，在一个无向图中，某一顶点i的度d_i表示与该顶点i相关的二元关系的个数。

定义2，如果度序列d_G中的任意分量d_i出现至少k次，则d_G是k-匿名的；如，序列d_G=（9，9，7，7，7，6，6）是2-匿名的。

定义3，如图G对应的度序列d_G是k-匿名的，则图G是k-匿名的。

发明内容

本发明所要解决的技术问题是提供一种优化的社交网络图数据发布隐私保护方法，其能够对社交网络发布的数据进行隐私保护处理。

为解决上述问题，本发明所设计的一种优化的社交网络图数据发布隐私保护方法，包括如下步骤：

（1）将社交网络的数据抽象为无向图G（V，E），其中V是顶点的有限集合、表示社交网络中的个人或团体，E是V上的二元关系、表示社交网络中的关系；

（2）计算无向图G（V，E）中每个顶点的度d_i，其中度d_i表示与第i个顶点相关的二元关系的个数，其中i=1，2，……，n；

（3）对无向图G（V，E）中的所有度d_i进行排序，获得度序列d_G，其中d_G=（d₁，d₂，……，d_n），且d₁≥d₂≥……≥d_n；

（4）用户根据隐私数据的敏感程度自行设定所需达到匿名度k的值，并对度序列d_G进行匿名度操作，构建出匿名度序列d_G’；即

（4.1）从度序列d_G中的d₁开始，计算度序列d_G中两两相邻度的差值，即︱d_i-d_i+1︱，并记录首次遇到的最大差值对应的i；

（4.2）调整i的值，以确保每个分组至少有k个元素；

（4.3）以第i+1位度作为新分组的起点；

（4.4）重复寻找新分组的起点和计算差值的过程，直至将度序列d_G中的所有新分组的起点都找出，由此将度序列d_G中的度d_i划分为多组，此时带有分组信息的度序列d_G即为构建出的匿名度序列d_G’；

（5）针对匿名度序列d_G’的每组分组中的度d_i’，计算其与同分组中第一个度值间的差值x_i，其中x_i代表这个顶点要达到匿名所需的边数，并把所有x_i不为0的点放在集合V_d中；

（6）在集合V_d中搜索添加匿名所需的边，其条件为在无向图G（V，E）中两个顶点之间不能够有边，每添加一条边，对应的两个顶点的匿名所需的边数x_i都减少1，当某个顶点的x_i为0时，表示此顶点满足匿名需求，将该顶点移出集合V_d；

（7）重复步骤（6）添加边的步骤；如果能够使集合V_d为空，则认为该组匿名度序列d_G’已经完成匿名无向图G’（V’，E’）的构建，此时输出匿名度序列d_G’所对应的匿名无向图G’（V’，E’）；如果集合V_d不为空，则需要对V_d集合中剩余的未匿名顶点进行步骤（8）的添加新顶点的步骤；

（8）计算剩余集合V_d中所有顶点到达匿名度k所需的最大边数t，并添加t个新顶点，选择集合V_d’中的第一个顶点，根据前面计算出的这个顶点匿名所需边数x_i，建立这个点同x_i个新增加点间的边，这个顶点匿名完成，将该顶点移出集合V_d；

（9）重复步骤（8）添加边的步骤，直至集合V_d为空，完成构建匿名无向图G’（V’，E’）的工作；此时输出匿名度序列d_G’所对应的匿名无向图G’（V’，E’）。

上述步骤（4）中所述设定的匿名度k的值在小于需匿名图数据即无向图G（V，E）的顶点数的条件下，建议在2～200之间选择。

与现有技术相比，本发明提供了一种k-匿名的社交网络数据隐私保护构建方法，即首先将社交网络的数据抽象为无向图，并由该无向图生成度序列；然后对度序列进行分组，构建出匿名度序列；最后再根据匿名度序列对原始图数据进行增加边和增加顶点的操作，使无向图中的所有顶点的度均为k,。经过本方法处理后，社交网络数据中每个个人或团体数据都具有至少k和他属性相同的其他个人或团体，攻击者根据背景信息只能定位到至少k个体，能够很好的保护社交网络参与者的隐私信息；本方法由于其高效性，能够适用于大规模的社交网络数据隐私保护处理。此外，本方法对于数据重构处理的信息损失量也较小。

附图说明

图1为构建匿名度序列d_G’的流程图；

图2为从匿名度序列d_G’及原始数据无向图G通过添加边构建匿名图G’的流程图；

图3为通过添加顶点构建匿名无向图G’的流程图。

具体实施方式

一种优化的社交网络图数据发布隐私保护方法，其特征是包括如下步骤：

（1）社交网络数据，由于其关系复杂性，一般用图数据结表示，本算法针对社交网络图数据的度属性进行保护。首先采用无向图G（V，E）抽象社交网络，其中V是顶点的有限集合、表示社交网络中的个人或团体，E是V上的二元关系、表示社交网络中的关系，如朋友、同学、亲戚等关系。

（2）计算无向图G（V，E）中每个顶点的度d_i，其中度d_i表示与第i个顶点相关的二元关系的个数，其中i=1，2，……，n。对于有n个点的图G，每个顶点都有一个度，度的序列d_G为n维向量。

（3）对无向图G（V，E）中的所有度d_i进行排序，获得度序列d_G，其中d_G=（d₁，d₂，……，d_n），且d₁≥d₂≥……≥d_n。

本发明的主要任务是在任给图G（V，E）和匿名度k的基础上，在对图G做最小改变的条件下，找到一个图具有k-匿名的图G’（V’，E’）。在此通过对原始图G（V，E）使用增加边和增加结点的方式进行匿名操作。

由图G（V，E）到图G’（V’，E’）匿名过程带来的信息量的损失为匿名代价cost，本发明的匿名代价由以下两部分组成：

①对于度序列d_G到d_G’的匿名过程，代价为增加的边个数

diffE(dG′-dG)=12Σi|di′-di|]]>

②对于图构建过程的代价diffN，为增加的点个数和与增加点相连接的边个数。

总的代价：Cost=diffE(d_G’-d_G)+diffN。

本发明分为三个主要步骤，即：

Ⅰ、由度序列d_G在diifE最小情况下构建匿名度序列d_G’。

Ⅱ、由d_G’及原始图数据通过添加边构建图G’。

Ⅲ、由d_G’及上一步的中间信息通过添加顶点构建图G’。

度为n（n≥2*k）的度序列d_G的最小diffE代价k匿名分组，其第二组的起点x满足不等式

k+1≤x≤2*k-1

由于要满足k匿名，所以第一组至少需要k个结点，第二组的起点最小为k+1；如果第二组的起点x≥2k，可以把第一组分为满足k匿名的两组，其diffE代价小于只分为一组的代价。

由此可得出，寻找最小diffE代价的算法可通过递归的方式在k+1≤x≤2*k-1序列中搜索。

本发明通过“贪心”的方式，由局部最优近似得出全局最优的序列分组。

（4）用户根据隐私数据的敏感程度自行设定所需达到匿名度k的值，并对度序列d_G进行匿名度操作，构建出匿名度序列d_G’；即

（4.1）从度序列d_G中的d₁开始，计算度序列d_G中两两相邻度的差值，即︱d_i-d_i+1︱，并记录首次遇到的最大差值对应的i；

（4.2）调整i的值，以确保每个分组至少有k个元素；

（4.3）以第i+1位度作为新分组的起点；

（4.4）重复寻找新分组的起点和计算差值的过程，直至将度序列d_G中的所有新分组的起点都找出，由此将度序列d_G中的度d_i划分为多组，此时带有分组信息的度序列d_G即为构建出的匿名度序列d_G’。

构建匿名度序列d_G’的具体过程如图1所示：

输入：n维度序列d_G，匿名度k；

输出：具有k-匿名的度序列d_G’。

fPoinr=0

for(n-starPoint)>2*k

fori<2*k-1

选择最大的d_i-d_i+1，记录首先遇到的最大值对应的i。

ifi<k

i=k

第k+1位为新分组的起点。

startPiont=fPoinr+i

最坏情况下，计算2k范围内的差最大值需要2k次减法和2k次判断，完成后问题的规模减少k，所以算法的最坏复杂度为O(n/k*4k)=O(4n)，是一个线性时间的复杂度。

匿名度k值由用户自行设定，k=1时，表示用户无需本方法保护其隐私，k=2时表示用户要求自己匿名于至少2个人或2个团体中。k值越大，隐私保护效果越好，但带了的原始数据扰动会越大。因此，在本发明中，一般建议用户设定的匿名度k值在小于需匿名图数据即无向图G（V，E）的顶点数的条件下，在2～100之间选择。

（5）针对匿名度序列d_G’的每组分组中的度d_i’，计算其与同分组中第一个度值间的差值x_i，其中x_i代表这个顶点要达到匿名所需的边数，并把所有x_i不为0的点放在集合V_d中；

（6）在集合V_d中搜索添加匿名所需的边，其条件为在无向图G（V，E）中两个顶点之间不能够有边，每添加一条边，对应的两个顶点的匿名所需的边数x_i都减少1，当某个顶点的x_i为0时，表示此顶点满足匿名需求，将该顶点移出集合V_d；

（7）重复步骤（6）添加边的步骤；如果能够使集合V_d为空，则认为该组匿名度序列d_G’已经完成匿名无向图G’（V’，E’）的构建，此时输出匿名度序列d_G’所对应的匿名无向图G’（V’，E’）；如果集合V_d不为空，则需要对V_d集合中剩余的未匿名顶点进行步骤（8）的添加新顶点的步骤；

（8）计算剩余集合V_d中所有顶点到达匿名度k所需的最大边数t，并添加t个新顶点，选择集合V_d’中的第一个顶点，根据前面计算出的这个顶点匿名所需边数x_i，建立这个点同x_i个新增加点间的边，这个顶点匿名完成，将该顶点移出集合V_d；

（9）重复步骤（8）添加边的步骤，直至集合V_d为空，完成构建匿名无向图G’（V’，E’）的工作；此时输出匿名度序列d_G’所对应的匿名无向图G’（V’，E’）。

①添加边的具体过程如图2所示：

输入：n维度序列d_G,匿名度序列d_G’，无向图G（V，E）；

输出：Ture：匿名完成，存在度序列为d_G’的图G’（V’,E’），使得V=V’，E∩E’=E；False:匿名没有完成，集合V_d包含没有匿名的结点和匿名所需的边数。

让V_d={v_d1，v_d2，……，v_di}存储d_G度序列与d_G’度序列的差值不为0的结点。

i=0；

fori<|V_d|do

If从V_d[i+1]到V_d.end()中存在结点Vd[j]和Vd[i]间没有边

增加一条V_d[j]到V_d[i]的边

V_d[j]，V_d[i+1]的差值都减1

ifV_d[i].diff为0，

从Vd中除去V_d[i]

ifV_d[j].diff为0，

从V_d中除去V_d[j]

i++;\\到下一个元素

ifV_d为空

retunTure，

else

returnFalse

②添加顶点的具体过程如图3所示，

输入：V_d没有匿名成功的结点集合，每个结点匿名所需的边数；

输出：度序列为d_G’的图G’（V’，E’），使得E∩E’=E,V∩V’=V。

选择V_d中结点匿名所需边的最大数t

增加t个结点

j=0

forV_d中的每个结点V_d[i]do

m=0

whilem小于Vd[i]结点匿名所需边数xdo

建立V_d[i]到t[j]的边，

m=m+1;

j=(j+1)%t

一种优化的社交网络图数据发布隐私保护方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。