欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2013102276331
申请人: 广西师范大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-02-23
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

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

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

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

(3)对无向图G(V,E)中的所有度di进行排序,获得度序列dG,其中dG=(d1,d2,……,dn),且d1≥d2≥……≥dn;

(4)用户根据隐私数据的敏感程度自行设定所需达到匿名度k的值,并对度序列dG进行匿名度操作,构建出匿名度序列dG’;即(4.1)从度序列dG中的d1开始,计算度序列dG中两两相邻度的差值,即︱dj-dj+1︱,并记录首次遇到的最大差值对应的j;

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

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

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

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

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

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

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

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

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

2~200之间选择。