(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210867729.3 (22)申请日 2022.07.22 (71)申请人 福建师范大学 地址 350117 福建省福州市闽侯县上街 镇 学府南路8号福建师 范大学旗山校区 (72)发明人 许力　章红艳　许佳钰　李啸林　 周赵斌　 (74)专利代理 机构 福州元创专利商标代理有限 公司 35100 专利代理师 陈鼎桂　蔡学俊 (51)Int.Cl. H04L 9/40(2022.01) G06K 9/62(2022.01) G06Q 50/00(2012.01) G06F 21/62(2013.01) (54)发明名称 一种社交网络中抵抗邻居攻击的用户身份 隐私保护方法 (57)摘要 本发明涉及一种社交网络中抵抗邻居攻击 的用户身份隐私保护方法， 在社会网络的图数据 遭受1*‑邻居攻击时， 采用图修改技术实现了用 户隐私身份隐私信息的保护； 根据图编辑距离对 同一簇中的1* ‑邻居图进行修改， 使它们达到概 率不可区分； 在实现社交网络中用户身份隐私保 护的同时， 提高图数据的可用性。 权利要求书4页 说明书8页 附图2页 CN 115277156 A 2022.11.01 CN 115277156 A 1.一种社交网络中抵抗邻居攻击的用户身份隐私保护方法， 其特征在于， 包括以下步 骤： 步骤1)建立社交网络模型， 将其表示为图G＝(V,E)， 其中V是图的顶点集， 表示社交网 络中的用户； E是边 集， 表示社交网络中的用户之间的关系； 根据度量d(v),lc(v)将用户节点初划分成T个簇， 其中d(v)表示用户节点v的度， 其含 义为社交网络中与该用户具有联系的用户数量； lc(v)表 示用户节 点v在网络中的局部聚类 系数， 其含义为节点v的邻居之间联系的紧密程度， 在划分结束后， 将这些簇按照每个簇的 最大节点度降序排列； 步骤2)预设一个用户隐私需求阈值k， 若某 个簇Ci中用户数少于阈值k， 则计算该簇的平 均度与相邻的前后两簇Ci‑1,Ci+1的平均度的差值， 将该簇合并到差值小的簇中， 重复该过程 直到所有簇的中用户的数量都大于k； 步骤3)， 在簇合并完成后， 针对用户节点个数大于2k的簇， 对其进行簇分裂操作使得每 一个簇中用户的数量 为[k,2k)的某个取值； 具体为： S3‑1， 对于每 个簇中的用户节点， 按度数降序排序， 构建用户节点的1* ‑邻居图； S3‑2， 构造用户节点的1* ‑邻居结构特征矩阵 其中 分别表示用户的节点v在社交网络中的度分布、 内度分布、 外度分布及 间隙度分布； S3‑3， 根据公式 计算同一簇中任意两个节点 之间的结构相似度， 其中 分别表示用户节点度分布、 内度分布、 外度分 布及间隙度分布的不相关程度,k1、 k2、 k3、 k4分别表示各个相似度所占比重， 且满足k1+k2+k3 +k4＝1； S3‑4， 利用K‑means聚类算法将节点划分为T个簇； 步骤4)， 根据每个簇中用户节点的1* ‑邻居图计算用户每对节点间的相似度， 并据此构 造出一个带权二部图， 在二部图上计算出图编辑距离， 据此找到目标图编辑路径P； 步骤5)， 根据步骤4)找到的图编辑路径P， 修改簇中节点的1* ‑邻居图， 使得他们同构。 2.根据权利要求1所述的一种抵抗邻居攻击的用户身份隐私保护方法， 其特征在于： 所 述1*‑邻居图为原 始图G的一个子图， 定义 为： G(v)＝(V(v),E(v),D(v) ) 其中V(v)是包括用户节点v本身及其邻居节点的集合， E(v)是V(v)中节点的边即邻居 之间的关系， D(v)是节点v的邻居在社交网络中邻居的数量构成的集合即V(v)中所有节点 的度构成的集 合。 3.根据权利要求1所述的一种抵抗邻居攻击的用户身份隐私保护方法， 所述步骤2)具 体为： S2‑1， 对于节点数小于k的簇， 将其记为 其中上标1表示该簇是第 一次划分后得到的 结果， 其簇内节点的平均度记为 计算 其前后相邻的两个簇 的节点平均 度， 分别记为 权　利　要　求　书 1/4 页 2 CN 115277156 A 2S2‑2， 若 满足公式 则将 添加到 中， 否则将 添加到 中； S2‑3， 重复执 行上述步骤， 直到所有的簇中的节点数都超过k。 4.根据权利要求1所述的一种抵抗邻居攻击的用户身份隐私保护方法， 其特征在于： 所 述步骤4)具体为： S4‑1， 如果两个用户节点的l* ‑邻居图中邻居节点数不相等， 则在用户邻居节点数少的 图中添加用户节点使得两个图中节点数相等； S4‑2， 构造用户节点的匹配代价矩阵， 并以用户节点的匹配代价作为边权值构造一个 带权二部图； S4‑3， 利用二部图计算用户节点间的图编辑距离以得到匹配的节点以及图编辑路径。 5.根据权利要求1所述的一种抵抗邻居攻击的用户身份隐私保护方法， 其特征在于： 所 述步骤5)具体为： S5‑1， 构造图G的邻接矩阵记为A＝(aij)n×n， 其中当节点vi和vj间存在边时， aij＝1， 否 则， aij＝0； S5‑2， 计算A2及A3， 及 若 则令 若 则令 计算 S5‑3， 对于社交网络中每个用户节点v， 根据S4 ‑3计算得到 的匹配节点u， 计算出节点v 需要修改的度并记为 将社交网络中每个用户节点需修改的度按照降 序排列， 得到的度修改序列记为 其中， dv表示用户节点v的邻居个数； S5‑4， 按照DM修改图结构。 6.根据权利要求1所述的一种抵抗邻居攻击的用户身份隐私保护方法， 其特征在于： 所 述S3‑2具体为： S3‑2‑1， 计算用户节点v的1* ‑邻居图G(v )中邻居节点的度分布 是 用 户节 点 vi的 度 ， 表 示 vi在 原 始图 G 中 邻 居 的 个 数 ， N(vi)为用户节点v所有邻居的集 合； S3‑2‑2 ， 计算用户节点v的1* ‑邻居图G (v)中邻居节点的内度分布 是用户节点的内度， 表示用户节点vi在1*‑邻居图 G(v)中邻居的个数， 步骤3‑2‑3， 计算用户节点v的1* ‑邻居图G(v)中邻居节点的出度分布 是vi的出度， 表示用户节点vi在1*‑邻居图G(v)之 外邻居的个数， 步骤3‑2‑4， 计算用户节点v的1* ‑邻居图G(v)中邻居节点的间隙度分布 其中 权　利　要　求　书 2/4 页 3 CN 115277156 A 3