(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 20221040793 6.0 (22)申请日 2022.04.19 (71)申请人 辽宁工业大学 地址 121001 辽宁省锦州市古塔区士英街 169号 (72)发明人 史伟　李刚　褚治广　张兴　 (74)专利代理 机构 北京远大卓悦知识产权代理 有限公司 1 1369 专利代理师 王雪娇 (51)Int.Cl. G06F 21/62(2013.01) G06F 16/9536(2019.01) G06F 16/906(2019.01) G06K 9/62(2022.01) (54)发明名称 一种面向加权社交网络隐私保护的图匿名 方法 (57)摘要 本发明公开了一种面向加权社交网络隐私 保护的图匿名方法， 结合k成员模糊聚类和模拟 退火算法对节点度序列创建最优聚类得到新的 度序列， 对原图进行增 删边操作使重构图满足新 的度序列； 对于度相同的节点， 为抵御背景知识 攻击， 对部分节点边权重进行泛化， 使得相同度 节点权重值满足l多样性模型， 实验结果表明， 相 比较其他方法， 本发明所提供的k成员模糊聚类 和模拟退火算法结合不仅能抵御加权社交网络 中节点度和加权边的背景知识攻击， 同时能有效 减少匿名后数据的损失量， 提高数据的实际效 用。 权利要求书2页 说明书13页 附图12页 CN 114692205 A 2022.07.01 CN 114692205 A 1.一种面向加权社交网络隐私保护的图匿名方法， 其特 征在于， 包括如下步骤： 步骤一、 对图数据G＝(V,E,W)进行k成员模糊聚类和模拟退火获得最优度划分序列； 其中， G为无向加权图， V为节点的集合， E为边的集合， W为边权重的集合， k为节点数， 且 k为整数； 步骤二、 通过 所述最优度划分序列构造k ‑度匿名图； 步骤三、 对所述 k‑度匿名图加权边泛化获得(k,l)匿名图； 其中， l为节点边权重相同个数， 且l 为整数。 2.如权利要求1所述的面向加权社交网络隐私保护的图匿名方法， 其特征在于， 所述k 成员模糊聚类包括： 对图数据的数据点集合vi＝{v1,v2,...,vn}进行划分后获得t个模糊聚类的集合， 并使 得目标函数值 最小， 获得簇 c{c1,c2…,ct}。 3.如权利要求2所述的面向加权社交网络隐私保护的图匿名方法， 其特征在于， 所述目 标函数值满足： 式中， f(v)为目标函数值， m为模糊参数， m∈R且m＞1， 为集合vi与第j个聚类中心的 隶属度， 表示节点度的数值与聚类中心点的度数值cj的误差绝对 值， 为图数据的节点度。 4.如权利要求3所述的面向加权社交网络隐私保护的图匿名方法， 其特征在于， 所述隶 属度矩阵满足： 式中， Uij为数据点的隶属度矩阵， Uij∈[0,1]， i ＝1,…,n， j＝1, …,c。 5.如权利要求4所述的面向加权社交网络隐私保护的图匿名方法， 其特征在于， 所述模 拟退火包括： 将簇c{c1,c2...,ct}作为模拟退火的初始解， 在迭代过程中， 随机产生一个领域解， 使 用所述目标函数值进 行评估， 以1的概率接受比原始 解更好的领域解， 以接受概率接受较差 的解决方案， 并用得到的新解代替最优解， 直至满足自定义的迭代次数输出最优解做最优 度划分序列。 6.如权利要求5所述的面向加权社交网络隐私保护的图匿名方法， 其特征在于， 所述接 受概率满足： 式中， P为接受概 率， f0为最优解的目标函数值， f1为新解的目标函数值， Ct为迭代参数。 7.如权利要求6所述的面向加权社交网络隐私保护的图匿名方法， 其特征在于， 所述迭 代参数满足： Ct＝1/αtT0；权　利　要　求　书 1/2 页 2 CN 114692205 A 2初始温度T0＝100， 降温系数α ＝0.95， 最大迭代次数maxgen＝200， 同一温度下的迭代次 数lk＝100。 8.如权利要求7所述的面向加权社交网络隐私保护的图匿名方法， 其特征在于， 所述k ‑ 度匿名图的删边方式包括： 若节点vu需要删边， 其邻居节点vv需要增边， 选取一个不与节点vv连接的vu的邻居节点 vw， 删除边eu,w， 增加边ev,w， 节点vu的度减少1， 节点vv的度增加1， 其他节点的度并没有发生 变化； 若节点vu需要删边， 其邻居节点vv同样需要删边， 则直接删除边ev,u； 若节点vu需要删边， 其邻居节点vv不需要改变， 则找到节点vv的邻居节点vw， 并且vw需要 加边， 如果存在边eu,w， 则删除边eu,w。 9.如权利要求8所述的面向加权社交网络隐私保护的图匿名方法， 其特征在于， 所述k ‑ 度匿名图的增边方式包括： 若节点vu需要增边， 其邻居节点vv不需要改变， 则找到节点vv的邻居节点vw， 并且vw需要 加边， 如果 不存在边eu,w， 则增加边eu,w； 若节点vu需要增边， 其邻居节点vv需要删边， 则找到节点vv的邻居节点vw， 并且vw不需要 改变， 如果 不存在边eu,w， 则增加边eu,w， 删除边ev,w； 若节点vu需要增边， 其邻居节点vv同样需要增边， 则直接添加边ev,u。 10.如权利要求9所述的面向加权社交网络隐私保护的图匿名方法， 其特征在于， 所述 步骤三具体包括： 对每一个簇cj， 获得簇中节点的权重矩阵， 对每个节点的权重序列进行递减排序， 并根 据度序列间的互信息划分为 个组， 使每个组至少拥有L个成员， 对每一项进行 比 较， 若Wi,j＞η×Wp,q， 则用户vi和vj之间的权重比用户vp和vq之间的权重大的节点， 将边权重 Wi,j和Wp,q全部投影到一个区域 值当中， 即泛化 为： Wi,j＝Wp,q＝[min{Wi,j,Wp,q},max{Wi,j,Wp,q}]； 式中， η为比例系数。权　利　要　求　书 2/2 页 3 CN 114692205 A 3