(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210782301.9 (22)申请日 2022.06.24 (71)申请人 浙江大学 地址 310058 浙江省杭州市西湖区余杭塘 路866号 (72)发明人 孙铭阳　袁泉　杜林康　程鹏　 (74)专利代理 机构 杭州求是专利事务所有限公 司 33200 专利代理师 刘静 (51)Int.Cl. G06F 21/62(2013.01) G06F 16/901(2019.01) G06F 16/903(2019.01) G06Q 50/00(2012.01) (54)发明名称 一种面向图数据的差分隐私保护发布方法 及系统 (57)摘要 本发明公开了一种面向图数据的差分隐私 保护发布方法及系统， 本发明首先读取原始图数 据， 记录节点和连边情况； 然后采用满足差分隐 私的社区检测方法， 对所有的节点进行社区划 分， 从而避免了直接对表示图的邻接矩阵加噪所 带来的过量噪声； 针对同一社区内和不同社区间 的不同特征， 分别提取不同粒度的信息并加噪， 有效减少了图编码过程的信息损失； 最后针对社 区内和社区间提取的不同信息采用不同的重构 方法， 尽可能的保留图的原始特征； 此外， 在处理 过程中， 对 添加拉普拉斯噪声后的结果采用了后 置处理方法， 将不符合实际的数据转变为符合真 实图特征的结果。 权利要求书3页 说明书7页 附图4页 CN 115114664 A 2022.09.27 CN 115114664 A 1.一种面向图数据的差分隐私保护发布方法， 其特 征在于， 该 方法包括： 步骤一， 获取原 始的真实图数据， 记录初始 节点信息和连边信息； 步骤二， 通过采用指数噪声机制和拉普拉斯噪声机制， 结合社区检测算法对节点进行 社区划分， 此 过程分配的隐私预算 为 ε1， 包括以下子步骤： 2.1通过指数噪声机制对节点进行初始的社区划分， 此 过程分配的隐私预算 为 εc； 2.2通过合并在同一社区的节点形成一个超节点图， 采用拉普拉斯机制对超节点图进 行加噪并进行后向处 理， 得到扰动 后的超节点图， 此 过程分配的隐私预算 为 εw＝ ε1‑εc； 2.3对扰动的超节点图采用社区检测算法进行进一 步的社区划分； 2.4基于超节点和原始节点的对应关系和所有超节点的社区划分情况， 得到原始节点 的最终社区划分情况； 步骤三， 对分组后的节点分别进行社区内和社区间的信息提取， 并采用拉普拉斯噪声 机制对提 取信息进行扰动， 此过程分配的隐私预算为 ε2＝ ε‑ε1， ε是总的隐私预算， 包括以下 子步骤： 3.1提取同一社区内节点的度序列信息， 采用拉普拉斯机制对其进行加噪并进行后向 处理， 此过程分配的隐私预算 为 εd； 3.2提取不同社区间的连边信息， 采用拉普拉斯机制对其进行加噪并进行后向处理， 此 过程分配的隐私预算 为 εv＝ ε2‑εd； 步骤四， 根据扰动得到的信息 重构图数据， 并将结果进行发布， 包括以下子步骤： 4.1对于同一社区内的节点， 通过步骤三得到的度序列信息计算出节点之间的连边概 率， 通过产生随机数的形式确定社区内的最终连边； 4.2对于不同社区间的节点， 通过步骤三得到的连边信 息， 在社区之间随机产生对应数 量的边， 从而确定不同社区之间的最终连边； 4.3将同一社区内和不同社区间的连边情况进行合并， 得到最终的合成图数据。 2.根据权利要求1所述的一种面向图数据的差分隐私保护发布方法， 其特征在于， 所述 步骤2.1中， 采用的社区划分具体步骤为： a)初始化， 将所有节点随机分为 k个社区， k 为预设值； b)以随机的方式遍历图的每个节点， 计算每个节点到所有社区的连边数量并将其作为 指数噪声机制的可用性 函数， 通过指数噪声机制选择被遍历节点的社区； c)对图节点的遍历进行T次， 从而得到节点的初始社区划分情况。 3.根据权利要求1所述的一种面向图数据的差分隐私保护发布方法， 其特征在于， 所述 步骤2.2中， 合并节点 为超节点并对其进行处 理， 具体步骤为： a)将在同一个社区内的节点合并为一个超节点， 同一社区内节点的度 数之和为超节点 的内部权重， 不同社区间的节点连边之和为 不同超节点之间的外 部权重； b)对超节点的内部 权重和外部权重分别采用拉普拉斯机制添加噪声 进行扰动； c)对扰动后的内部权重和外部权重分别进行后向处理， 即 向扰动后的权重同时减去一 个整数并将所有负值置 0， 使得处 理后的权 重之和与初始权 重之和的差值 最小。 4.根据权利要求1所述的一种面向图数据的差分隐私保护发布方法， 其特征在于， 所述 步骤2.3中， 对 超节点图进行 社区检测处 理， 具体步骤为： a)每个超节点初始化 为一个社区；权　利　要　求　书 1/3 页 2 CN 115114664 A 2b)以随机的方式遍历每个超节点， 计算每个超节点移动到邻居超节点的对应社区所带 来的模块度的变化， 模块度的定义 Q： 其中∑in代表社 区C内部的权重之和， ∑tot代表社 区C内所有节点的权重总和， 即内部 权重与外部权重的总和， 2m代 表整个图的权 重总和； 将一个孤立的超节点移动到一个社区的模块度变化 值ΔQ： 其中kn代表与超节点n相连的边的权重之和， kn,in代表超节点n到属于社区C的超节点的 连边的权 重之和； 每次遍历时， 如果模块度增益大于 0， 则选择将超节点移动到模块度增益 最大的社区； c)不断循环b)过程， 直到遍历所有的超节点的过程中没有超节点有所属社区移动的情 况或者上一次遍历得到的模块度与此次遍历得到的模块度的差值小于设定阈值θ1时停止； d)将在同一个社区内部的超节点合并为一个新的超节点， 得到一个新的超节点图， 继 续循环a)、 b)、 c)过程， 直至前后两次合并超节点时的模块度 的差值小于设定阈值θ2时停 止。 5.根据权利要求1所述的一种面向图数据的差分隐私保护发布方法， 其特征在于， 所述 步骤3.1中， 对同一社区内的节点 提取信息并扰动， 具体步骤为： a)获取同一社区内节点在该 社区内部的度 序列信息； b)向度序列信息添加拉普拉斯噪声； c)对扰动后的结果进行后向处理， 即向扰动后的度序列同时减去一个整数并将所有负 值置0， 使得处 理后的度 序列之和与初始度 序列之和的差值 最小。 6.根据权利要求1所述的一种面向图数据的差分隐私保护发布方法， 其特征在于， 所述 步骤3.2中， 对不同社区间的节点 提取信息并扰动， 具体步骤为： a)获取不同社区内节点之间的连边情况， 将两个社区间所有节点之间的连边数相加， 进而得到所有不同社区间的连边数量信息； b)向不同社区间的连边数量添加拉普拉斯噪声； c)对扰动后的结果进行后向处理， 即向扰动后的结果同时减去一个整数并将所有负值 置0， 使得处 理后的结果之和与初始结果之和的差值 最小。 7.根据权利要求1所述的一种面向图数据的差分隐私保护发布方法， 其特征在于， 所述 步骤4.1中， 重构同一社区内部的连边， 具体步骤为： a)根据同一社区内所有节点扰动后的度序列信 息， 计算出任意两个节点u和w之间的连 接概率pu,w： 其中 表示节点u在社区C内的扰动度， 表示节点w在社区C内的扰动度， 表示权　利　要　求　书 2/3 页 3 CN 115114664 A 3