(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 20221071279 2.X (22)申请日 2022.06.22 (71)申请人 广州大学 地址 510006 广东省广州市大 学城外环西 路230号 (72)发明人 殷丽华　孙哲　陶富强　方滨兴　 韩伟红　张美范　李然　 (74)专利代理 机构 广州高炬知识产权代理有限 公司 44376 专利代理师 孙明科 (51)Int.Cl. G06F 16/28(2019.01) G06F 21/62(2013.01) (54)发明名称 一种面向本地化差分隐私的图统计分析方 法 (57)摘要 本发明属于差分隐私和子图统计技术领域， 公开了一种面向本地化差分隐私的图统计分析 方法， 包括如下步骤： S1、 针对现有图统计分析算 法存在隐私泄露的问题， 设置的框架让每个用户 对他的邻接列表数据进行扰动； S2、 再将噪声数 据发送到服务器， 服务器接收到扰动的数据后再 计算出子图计数的无偏估计； S3、 通过三角形和 k‑stars的实用计数算法， 在不接触用户的原始 数据的条件下计算出图中的聚类系数； S4、 服务 器根据聚类系数， 可以向聚类系数高的子图中的 用户推送相关的服务。 该面向本地化差分隐私的 图统计分析方法， 可以降低子图统计的估计误 差， 确保算法的实用性， 并且其客户端无需了解 额外信息， 提高子图统计分析的隐私性。 权利要求书2页 说明书5页 附图2页 CN 115114381 A 2022.09.27 CN 115114381 A 1.一种面向本地 化差分隐私的图统计分析 方法， 其特 征在于， 包括以下步骤： S1、 针对现有图统计分析算法存在隐私泄露的问题， 设置的框架让每个用户对他的邻 接列表数据进行扰动； S2、 再将噪声数据发送到服务器， 服务器接收到扰动的数据后再计算出子图计数的无 偏估计； S3、 通过三角形和k ‑stars的实用计数算法， 在不接触用户的原始数据的条件下计算出 图中的聚类系数； S4、 服务器根据聚类系数， 可以向聚类系数高的子图中的用户推送相关的服 务。 2.根据权利要求1所述的面向本地化差分隐私的图统计分析方法， 其特征在于： 所述步 骤S3中， 针对子图k ‑stars的计数设计一种实用性的响应算法， 针对子图三角形的计数设计 一种基于 两轮客户端 ‑服务器的交 互算法。 3.根据权利要求2所述的面向本地化差分隐私的图统计分析方法， 其特征在于， 针对子 图k‑stars的计数设计一种基于 本地化差分隐私的统计算法， 其 步骤如下： 第一步， 通过一个邻接矩阵A来表示图(1： 有边， 0： 没有边)， 用户vi知道所有与自身相连 接的节点， 记为邻接列表ai(A的第i行)； 第二步， 在客户端中， 用户的邻接列表ai分为两部分Xs＝{x1,…,xk}和Xn＝{xk+1,…, xn}， 用户可以调节k的位置， 如果用户觉得数据是敏感的， 可以将k的位置往后移。 如果用户 觉得数据是不敏感的， 可以将k的位置往前移； 第三步， 客户端对用户的邻接列表数据进行扰动， 对于Xs＝{x1,…,xk}采用随机响应RR 机制进行扰动， 对0和1都以概率P1进行翻转； 对于Xn＝{xk+1,…,xn}部分仅对1以概率P2进行 翻转； 第四步， 客户端将k的值和扰动后的邻 接列表的值上传到服务器， 服务器对扰动后的数 据进行统计分析， 对统计结果进行校正， 构建似然函数， 得到真实结果的极大似然估计， 再 分析其数 学期望， 得到真实结果的无偏估计。 4.根据权利要求2所述的面向本地化差分隐私的图统计分析方法， 其特征在于， 针对子 图三角形的计数设计一种基于 本地化差分隐私的统计算法， 其 步骤如下： 第一步， 通过一个邻接矩阵A来表示图(1： 有边， 0： 没有边)， 用户vi知道所有与自身相连 接的节点， 记为邻接列表ai(A的第i行)； 第二步， 在客户端中， 用户的邻接列表ai分为两部分Xs＝{x1,…,xk}和Xn＝{xk+1,…, xn}， 用户可以调节k的位置， 如果用户觉得数据是敏感的， 可以将k的位置往后移。 如果用户 觉得数据是不敏感的， 可以将k的位置往前移； 第三步， 客户端对用户的邻接列表数据进行扰动， 对于Xs＝{x1,…,xk}采用随机响应RR 机制进行扰动， 对0和1都以概率P1进行翻转； 对于Xn＝{xk+1,…,xn}部分仅对1以概率P2进行 翻转， 客户端将噪声数据上传到服 务器； 第四步， 服 务器端统计 每个用户提交的噪声边， 服 务器发布噪声图G ′； 第五步， 客户端接收到噪声图G ′， 用户可以使用噪声图G ′来计算含一条噪声边的三角 形计数； 第六步， 用户根据邻接列表和噪声图G ′值， 统计他的三角形计数再加上拉普拉斯噪声， 上传到服 务器中；权　利　要　求　书 1/2 页 2 CN 115114381 A 2第七步， 服 务器计算出三角形计数的无偏估计。权　利　要　求　书 2/2 页 3 CN 115114381 A 3