近年来，物联网、大数据及云计算等^[1-2]新兴技术的快速发展使得海量数据采集、存储和处理变得便捷，促使社交网络、商业推荐、智慧交通等以数据为驱动的信息服务快速普及，深刻影响人们的生活与工作. 特别是生物医药研发、社交物联网^[3-4]、社交网络、金融保险等领域，产生了海量数据并兴起了AI for Science、联邦学习^[5]、图神经网络^[6]等新兴研究方向.

然而，各类以数据为驱动的信息服务系统均以不同形式采集和保留用户的个人数据. 这些数据包含用户的身份、职业及爱好等隐私信息，还可能包含不同用户间的交互信息. 如果在采集和共享过程中，不能对这些数据进行有效隐私保护，将引发信息泄露及财产损失等隐患^[4]. 因此，将隐私数据共享应用于信息服务之前，有必要落实合规的隐私保护措施，以实现隐私数据的安全采集和共享. 在不同类型的数据采集和共享中，社交网络、社交物联网等产生的图结构数据可以表示不同实体间的复杂关系，较关系、文本和图像等类型的数据在分析主体间复杂关联关系方面更具优势. 然而，图结构数据的节点和边表示的身份隐私、关系隐私和属性隐私相互关联，尤其在采集或共享分布式用户持有的图结构数据子集时，具有更大的隐私泄露风险和保护难度. 因此，迫切需要有效的隐私保护手段，在图结构数据采集和共享过程实现高效的隐私保护效果^[7].

在分布式图结构数据应用场景中（如社交物联网、社交网络），往往由单个节点（用户或设备）持有其自身节点信息及其与邻居的关联信息，即一阶邻居子图^[7-8]. 为了更好地分析数据或提供服务，数据采集者（服务提供商）会从分布式用户端采集整个图结构数据，以供应用服务商分析和应用，进而提高服务便捷性或精准营销. 具体的数据分析过程会采用统计学、图论等技术对整个图结构数据的统计指标（如度分布、三角计数序列和聚类系数等）进行处理，从而有效地挖掘其中的潜在高价值信息^[7-9]. 但这些统计指标与各用户拥有的子图结构数据高度关联，且包含大量用户轨迹、关联关系等隐私信息，在采集、共享或发布时极易泄露隐私信息. 因此，对高度关联的分布式图结构数据的各种统计指标进行隐私保护采集共享，且不泄露用户身份隐私以及用户间的关系隐私，成为以图结构数据为驱动的信息服务领域中尤为迫切的挑战之一.

为了有效保护分布式场景下的图结构数据隐私，本地差分隐私（local differential privacy，LDP）^[10-11]从关系型数据集、Key-Value型数据应用场景中被扩展到了图结构数据应用场景. LDP具有可证明强度的隐私保护能力，且无需可信第三方，故而广受学术界和产业界的关注^[8-9,12-17]. 面向图结构数据的LDP方案，其基本假设是各用户持有包含自身节点信息的一阶邻居子图，即各用户仅知道其自身信息以及与其相邻的关系信息. 在数据采集者采集数据时，首先，各用户对自身一阶邻居子图的邻接向量进行随机响应（randomized response，RR）^[18]扰动加噪；然后，数据收集方根据各用户发送的噪声邻接向量进行聚合统计，获取分布式图结构数据整体统计指标的估计数据. 根据保护强度不同，LDP可应用于对图结构数据的节点或边进行加噪，产生了节点LDP（Node-LDP）和边LDP（Edge-LDP）^[8]两种变型. 其中，Node-LDP能同时保护多条边的隐私，保证敌手无法获取图结构数据上任意节点的邻居数量^[8,14,17]，从而提供更强的隐私保护效果，但会大幅度降低图结构数据采集结果的数据效用^[8,14]. 因此，为了保持更好的数据效用，现有基于LDP的图结构数据隐私保护方案^[8-9,12-14]通常采用Edge-LDP模式对隐私保护效果进行折中以提高数据效用. 如Zhan等人^[8]提出一种Edge-LDP下基于度序列进行聚类的图生成算法. Ye等人^[12]引入Edge-LDP提出一种可同时采集聚类系数和模块化信息的框架. 随着图结构数据规模的增长以及图结构数据应用的扩展，获取一些图结构数据信息时所面临的隐私需求将更加严格，特别是图结构数据多条边的隐私需要同时保护的需求愈发迫切^[17]. 具体而言，需要在实施隐私保护的过程中进一步加强图结构数据的节点隐私（如度值隐私）和关系隐私保护，或者实现节点的个性化隐私保护. 然而，Edge-LDP无法同时保护多条边的隐私，且无法实现对节点度值隐私的保护^[8,14,17]. 为进一步强化图结构数据的隐私保护效果，Fu等人^[17]和Liu等人^[19]分别基于Node-LDP设计了分布式图结构数据的隐私保护聚类及度分布采集算法. 真实图结构应用中，往往需要同时采集多种图结构数据统计指标，且各用户的隐私偏好不一^[14,17]，需要平衡分布式图结构数据上各节点的隐私需求以及数据效用间的冲突，同时优化隐私保护机制，尽可能降低扰动加噪对数据效用的影响. 此外，直接应用现有的算法来组合完成多统计指标的隐私保护采集，一方面会增加分布式用户与数据采集者间的通信开销，另一方面会增加存储和计算开销，再一方面各个算法的隐私保护强度不一，难以实现统一的隐私保护效果，且无法满足各节点的个性化隐私保护偏好需求. 同时，真实世界中的图结构数据多数为稀疏的，使得无论Edge-LDP或Node-LDP都会在随机化过程中产生大量的虚假边^[14,17]，进而严重降低最终采集的图结构数据的精度和效用. 如图1所示，当采用2-Edge-LDP和2-Node-LDP（$\varepsilon = 2$）对图结构数据加噪时，图结构数据的隐私效用会受到不同程度的影响（边密度大幅度提高）.

图  1  Edge-LDP和Node-LDP下扰动图结构数据对边密度效用的影响

Figure  1.  Impact of perturbing graph-structure data on edge density utility under Edge-LDP and Node-LDP

下载: 全尺寸图片 幻灯片

为了满足分布式图结构数据应用中的多样化统计指标采集需求，实现高强度和个性化的隐私保护，降低扰动加噪对数据效用的影响，本文通过引入Node-LDP和Edge-LDP提出基于本地差分隐私的图统计指标采集算法（graph statistics collecting algorithms via local differential privacy，GS-LDP），将度值采集作为基础统计指标来采集，在采集过程中通过限制加噪的扰动域来降低噪声输入，并在加噪过程中对用户子图进行剪枝来大幅度降低无效噪声量来提升数据效用，通过自适应隐私设置来调节满足Node-LDP或Edge-LDP以适应用户的个性化隐私偏好. 具体地：首先，引入分组机制和对称一元编码（symmetric unary encoding，SUE）^[11]，提出一种满足Node-LDP的图结构数据度分布采集算法，通过限制SUE扰动域上限的方式降低采集过程中的噪声输入，实现Node-LDP保护的同时实施高效用的分布式图结构数据度分布采集；其次，基于所提出的度分布采集算法，利用剪枝（Prune）算法对用户持有的子图进行剪枝，通过设置度值阈值来对一阶邻居子图的邻居位向量进行剪切投影，从而限制随机过程中所产生的噪声边的量，通过大幅度降低无效噪声提高数据效用；再次，引入拉普拉斯机制、随机响应机制和2轮交互模型，提出满足Node-LDP和Edge-LDP的三角计数序列采集算法及满足Node-LDP和Edge-LDP的聚类系数采集算法，通过自适应隐私设置来调节满足Node-LDP或Edge-LDP以适应用户的个性化隐私偏好，实现不同隐私保护强度和数据效用需求的分布式图结构数据多统计指标采集. 本文的主要贡献有4个方面：

1）基于分组机制及对称一元编码机制，提出一种满足Node-LDP的分布式图结构数据度分布采集算法，提高度分布采集的隐私保护强度和数据效用；

2）采用剪枝算法控制随机加噪过程中虚假边的上限，降低无效噪声输入，并进一步利用2轮交互模型分别提出满足Node-LDP和Edge-LDP的三角计数序列采集算法；

3）在2）中三角计数序列采集算法的基础上，引入拉普拉斯机制分别提出满足Node-LDP和Edge-LDP的聚类系数采集算法；

4）进行理论分析和多个数据集实验对比，结果表明，所提出的算法能在不同约束下实现多个统计指标的有效采集，与现有的统计指标采集算法相比有显著的效用优势.

1.   相关工作

差分隐私（differential privacy，DP）^[20-24]由Dwork^[20]提出，主要应用于关系型数据库的统计信息隐私保护，后来被逐步应用于图结构数据的隐私保护^[21-24]. DP在应用过程中，通常需要一个可信第三方对数据进行统筹处理，其仅适用于中心化的数据共享采集场景. 然而，在诸如位置服务网络、社交物联网等真实图结构数据应用场景中，往往不存在可信第三方^[12]，且数据被分布式持有在不同的用户或设备上. 在此类场景中，各用户相互不信任，均不愿把自己的子图数据直接共享给彼此或数据采集者.

为了适应分布式场景的隐私保护，LDP^[10-11]被提出并应用于均值估计^[10]及频繁模式挖掘^[10]等. 直至2017年，Zhan等人^[8]提出将LDP应用于图结构数据隐私保护，通过在分布式端迭代收集用户节点度值并采用k-means算法聚合获取生成图，但由于该方案仅通过度值进行聚类，所得到的生成图缺少大量原始图中的结构特性. 为了提高数据效用，Ye等人^[12]通过引入RR机制^[18]扰动用户的子图邻接向量，并采用拉普拉斯机制采集用户度值，提出一种基于LDP的图聚类系数和模块化采集框架. 而后，Imola等人^[9]引入2轮交互模型，将加噪后的子图邻接向量合成噪声图后发送给用户，由各用户分别估计三角计数后将整体三角计数结果发布，并最终由数据采集者统一采集全局计数信息. 然而，Ye等人^[12]和Imola等人^[9]的方法都会产生大量噪声边，从而影响最终采集结果的精度. 为了解决该问题，Hou等人^[14]通过设计一种基于最优长度的度向量编码模型对图结构数据进行分散聚类，但该方法仅适用于图结构数据聚类. 为了获得更好的数据效用，Sun等人^[25]和Liu等人^[26]通过减弱分布式图结构数据的隐私保护假设，允许各用户和邻居交换各自的邻居信息（即各用户持有的二阶子图信息），分别设计了隐私保护的分布式图结构数据子图计数算法. 此外，针对二元属性图结构数据的隐私保护，Wei等人^[16]提出一种随机跳转（random jump，RJ）的分布式属性图结构数据度分布采集算法，并将RR机制应用于采集用户的二元属性，在此基础上，通过抽样方法构建整体的二元属性图结构数据用以数据分析.

前述图结构数据的LDP模型均基于Edge-LDP. 然而，随着数据规模的增长及隐私保护需求的增强，Edge-LDP的隐私保护强度难以满足同时保护多条边的隐私需求^[14,17]. 因此，为了提高对图结构数据的隐私保护水平，Fu等人^[17]提出基于Node-LDP的2阶段图结构数据聚类框架，通过剪影系数测量模型进行节点聚合，并利用自适应加噪来提高聚类结果的效用. Liu等人^[19]结合Node-LDP和密码投影方法提出一种最优图投影参数选择方法，并基于此提出Node-LDP下的度分布采集算法，但度值的敏感度过大，使得度分布采集结果效用不高.

由此可见，现有的分布式图结构数据隐私保护方案大多基于Edge-LDP设计，其通过放宽对边的数量保护的隐私约束，实现高效用的数据采集^[14,17]. 也正因如此，此类方法无法实现同时保护多条边的隐私信息^[14,17]. 而Node- LDP的方案能够保证无法从算法输出中获取任何用户的朋友数（边数）^[14]，可有效避免此类缺陷. 因而，Node-LDP较Edge-LDP的方案具有更强的隐私保护效果，但严格的隐私约束及敏感度会大幅度削弱其实际效用^[8,14]. 同时，2种类型的隐私保护方法在作用于分布式图结构数据时，均直接采用随机响应扰动各用户的子图邻接向量，从而会产生大量噪声边（如图1所示），尚未发现有效的机制来识别无效噪声并降低这些噪声的添加量，这使得无论Edge-LDP还是Node-LDP采集的图结构数据效用均无法达到理想状态. 此外，常规LDP模型^[9,12,25-26]多数仅针对单个统计指标的采集需求，无法同时适应图结构数据不同统计指标的采集. 若通过简单组合此类算法来实现多统计指标采集，会造成通信复杂度、存储复杂度、计算复杂度提高等问题，且难以使不同算法的隐私保护水平一致.

为此，本文结合Node-LDP和Edge-LDP面向分布式图统计采集隐私保护需求，引入分组SUE、RR及拉普拉斯机制，并提出一种优化图结构噪声量的剪枝算法，进而设计具备强隐私保护能力和高数据效用的多样化图统计指标采集算法. 首先，针对性质单一的度分布指标，通过分组报告的方式限制SUE扰动域上限，降低采集过程的噪声输入，从而实现满足Node-LDP的高效度分布采集；其次，针对三角计数序列，提出剪枝算法，用于优化随机化过程中边缘的噪声量；再次，引入2轮交互模型、RR及拉普拉斯机制，通过设置不同隐私参数提出满足Node-LDP和Edge-LDP的三角计数序列和聚类系数采集算法.

2.   基本定义及预备知识

2.1   符号定义

本文所述算法均基于简单无向图$G = \left( {V,E} \right)$，其中顶点集由$V$表示，边集由$E$表示，顶点集中的顶点数$n = \left| V \right|$代表当前图$G$中的总用户数量. 本文假设图$G$是分布式的，各用户在本地持有以自身为中心的星图，可称为一跳邻居子图. 用户可将其抽象为一个$n$维的邻接向量${{\boldsymbol{B}}_i} = \left( {{b_1},{b_2},…,{b_n}} \right)$，其中任意${b_j} \in \left\{ {0,1} \right\}$为${{\boldsymbol{B}}_i}$中的第$j$位，代表用户$i$与用户$j$之间的关联关系，${b_j} = 1$表示用户$i$与用户$j$之间存在边，$b_j=0$表示用户i与用户j之间不存在边. $\boldsymbol{M}=\left(\boldsymbol{B}_1,\boldsymbol{B}_2,\dots,\boldsymbol{B}_n\right)=(B_{ij})_{^{n\times n}}$为图$G$的邻接矩阵，由$G$中所有用户的邻接向量组成，代表全局用户的邻居信息. ${d_i} = \sum\limits_{j = 1}^n {{B_i}_j}$（或${d_i} = \sum\limits_{j = 1}^n {{b_j}}$）为用户$i$的度值，代表用户$i$的邻居数量. ${T_i}$代表用户$i$所关联的三角计数，即用户$i$的局部三角计数. $C{C_i}$代表用户$i$的局部聚类系数，可通过用户局部三角计数和度值进行计算，即

其中$T = \left( {{T_1},{T_2},…,{T_n}} \right)$和$CC = \left( {C{C_1},C{C_2},…,C{C_n}} \right)$分别代表图$G$的三角计数序列及全局聚类系数. $\varepsilon$为差分隐私的隐私预算，用于控制噪声输入及保护强度. $\varepsilon$越小，保护强度越高，噪声量越大.

为了便于阅读，表1中列出本文常用符号及其描述.

表  1  符号及其描述

Table  1.  Symbols and Its Discription

符号	描述
$\varepsilon$	隐私预算
$G$	简单无向图
$d_i$	用户度值
${{\boldsymbol{B}}_i}$	用户一阶邻接向量
$T_i$	用户局部三角计数
$C{C_i}$	用户局部聚类系数
$n = \left| V \right|$	图$G$中总用户数量
$T$	图$G$中的三角计数序列
$CC$	图$G$的全局聚类系数
${\boldsymbol{M}}$	图$G$的邻接矩阵

下载: 导出CSV 

| 显示表格

2.2   本地差分隐私及加噪机制

定义1. $\varepsilon$-LDP^[10]. 给定$n$个用户和随机算法$\mathcal{A}$，若算法$\mathcal{A}$作用在任意2条记录$t$和$t'$上得到相同的输出结果${t^*}$，有

则算法$\mathcal{A}$满足$\varepsilon$-LDP. 其中，${t^*} \in range\left( \mathcal{A} \right)$为算法$\mathcal{A}$的输出.

定义2. $\varepsilon$-Edge-LDP^[8]. 当随机算法$\mathcal{A}$作用在任意2个仅在1位上不同的邻接向量${{\boldsymbol{B}}_i} = {\left( {0,1} \right)^n}\,$和${{\boldsymbol{B}}'_i} = {\left( {0,1} \right)^n}\,$上时，若算法$\mathcal{A}$满足$\varepsilon$-Edge-LDP，则有

其中${\boldsymbol{S}} = {\left( {0,1} \right)^n}\, \in range\left( \mathcal{A} \right)$，即算法$\mathcal{A}$的输出.

定义3. $\varepsilon$-Node-LDP^[8]. 当随机算法$\mathcal{A}$作用在任意2个邻接向量${{\boldsymbol{B}}_i} = {\left( {0,1} \right)^n}\,$和${{\boldsymbol{B}}'_i} = {\left( {0,1} \right)^n}\,$上时，若算法$\mathcal{A}$满足$\varepsilon$-Node-LDP，则有

其中${\boldsymbol{S}} = {\left( {0,1} \right)^n}\, \in range\left( \mathcal{A} \right)$，即算法$\mathcal{A}$的输出.

在分布式图结构数据应用场景下，$\varepsilon$-LDP仅满足采集数据的隐私性，并不考虑数据间的关联性，如顶点之间关联的边. 在此基础之上，$\varepsilon$-Edge-LDP和$\varepsilon$-Node-LDP进一步考虑数据间的关联性，需要在采集过程中保护用户间的边信息（关联信息）；不同的是，$\varepsilon$-Edge-LDP是$\varepsilon$-Node-LDP的松弛，它将任意2个邻接向量的邻接定义限制在1位（即1条边）^[12]. 在此背景下，设${Q_1},{Q_2},{Q_3}$和${U_1},{U_2},{U_3}$分别代表满足$\varepsilon$-Node-LDP,$\varepsilon$-Edge-LDP和$\varepsilon$-LDP时的隐私保护强度和效用精度. 根据上述描述可得出结论，在分布式图结构数据应用场景下，隐私约束性（即隐私保护强度）上

反之，在最终效用精度上

定义4. $\varepsilon$-RR^[18]. 设算法$\mathcal{R}\mathcal{R}$为$\varepsilon$-RR，用户通过算法$\mathcal{R}\mathcal{R}$扰动数据的过程为：对任意二进制数据$x \in \left\{ {0,1} \right\}$，用户以$p$的概率发送真实值$x$，以$q$的概率发送真实值$1 - x$，即

满足以上条件，则$\varepsilon$-RR满足$\varepsilon$-LDP，其中$x,y \in \left\{ {0,1} \right\}$分别为输入数据和输出数据.

定义5. $\varepsilon$-SUE^[11]. 用户通过$\varepsilon$-SUE扰动数据的过程为：对任意$o$维的实值数据$x \in \left\{ {1,2,…,o} \right\}$. 首先，用户将其编码为一个$o$维的二元向量，即$Encode\left( x \right) = \left( {0,…,0,1,0,…,0} \right)$，其中除第$x$位为1外，其余位全为0. 随后，用户对编码数据进行逐位扰动（${\varepsilon \mathord{\left/ {\vphantom {\varepsilon 2}} \right. } 2}$-RR），即

该过程满足$\varepsilon$-LDP. 其中，$p = \dfrac{{{{\mathrm{e}}^{{\varepsilon \mathord{\left/ {\vphantom {\varepsilon 2}} \right. } 2}}}}}{{{{\mathrm{e}}^{{\varepsilon \mathord{\left/ {\vphantom {\varepsilon 2}} \right. } 2}}} + 1}}$，$q = 1 - p$.

定义6. 全局敏感度（global sensitivity，GS）^[27]. 对于任意一个实际值的查询函数$f{\text{:}}D \to \mathbb{R}$，其全局敏感度定义为

其中$D$和$D'$表示为相邻数据集.

定义7. Laplace机制^[24]. 对于给定的数据集$D$和实值查询函数$f$，$G{S_f}$是$f$在数据集$D$上的全局敏感度，则随机算法$\mathcal{M}$：$\mathcal{M}\left( D \right) = f\left( D \right) + X$满足$\varepsilon$-DP. 其中$X \sim Lap\left( {{{G{S_f}} \mathord{\left/ {\vphantom {{G{S_f}} \varepsilon }} \right. } \varepsilon }} \right)$是服从尺度参数为${{G{S_f}} \mathord{\left/ {\vphantom {{G{S_f}} \varepsilon }} \right. } \varepsilon }$的Laplace分布噪声.

值得注意的是，在LDP视角上，相邻数据集$D$和$D'$被转换成了相邻的邻接向量${{\boldsymbol{B}}_i}$和${{\boldsymbol{B}}'_i}$. 例如，在Edge-LDP场景下采集度值${d_i}$，删除任意一条边仅影响${{\boldsymbol{B}}_i}$中的1个比特位，因此敏感度为1，即向${d_i}$中添加$Lap\left( {{1 \mathord{\left/ {\vphantom {1 \varepsilon }} \right. } \varepsilon }} \right)$的噪声便可满足$\varepsilon$-Edge-LDP.

定理1. 若通过$\varepsilon$-RR扰动一个$n$维的邻接向量${{\boldsymbol{B}}_i} = {\left( {0,1} \right)^n}\,$，其满足$\varepsilon$-Edge-LDP^[8].

证明. 设随机算法$\mathcal{A}$为$\varepsilon$-RR，$Pr\left[ {\mathcal{A}\left( x \right) = y} \right]$表示$x \in \left\{ {0,1} \right\}$随机翻转为$y \in \left\{ {0,1} \right\}$的概率. 其中，${{\boldsymbol{B}}_i} = \left( {b_1}, {b_2},…,{b_n} \right)$和${{\boldsymbol{B}}'_i} = \left( {{b'_1},{b'_2},…,{b'_n}} \right)$ （${b_i},{b'_i} \in \left\{ {0,1} \right\}$）为仅相差1位的邻接向量. 不失一般性，假设${b_1} \ne {b'_1}$，给定算法$\mathcal{A}$的任意输出${\boldsymbol{S}} = \left( {{s_1},{s_2},…,{s_n}} \right),{s_i} \in \left\{ {0,1} \right\}$，有

因此，算法$\mathcal{A}$（$\varepsilon$-RR）满足$\varepsilon$-Edge-LDP. 证毕.

定理2. 若通过$\varepsilon$-RR扰动一个$n$维的邻接向量${{\boldsymbol{B}}_i} = {\left( {0,1} \right)^n}\,$，其满足$n\varepsilon$-Node-LDP.

证明. 设随机算法$\mathcal{A}$为$\varepsilon$-RR，$Pr\left[ {\mathcal{A}\left( x \right) = y} \right]$表示$x \in \left\{ {0,1} \right\}$随机翻转为$y \in \left\{ {0,1} \right\}$的概率. 其中，${{\boldsymbol{B}}_i} = \left( {b_1}, {b_2},…,{b_n} \right)$和${{\boldsymbol{B}}'_i} = \left( {{b'_1},{b'_2},…,{b'_n}} \right)$ （${b_i},{b'_i} \in \left\{ {0,1} \right\}$）为2个相邻的邻接向量. 不失一般性，假设${{\boldsymbol{B}}_i},{{\boldsymbol{B}}'_i}$中每一位对应值都不一样，因此给定算法$\mathcal{A}$的任意输出${\boldsymbol{S}} = \left( {s_1}, {s_2},…,{s_n} \right),{s_i} \in \left\{ {0,1} \right\}$，则有

因此，算法$\mathcal{A}$（$\varepsilon$-RR）满足$n\varepsilon$-Node-LDP. 证毕.

根据定理1和定理2可知，在相同$\varepsilon$情况下对$n$维的邻接向量进行扰动时，满足$\varepsilon$-Node-LDP和$\varepsilon$-Edge-LDP分别需要通过${\varepsilon \mathord{\left/ {\vphantom {\varepsilon n}} \right. } n}$-RR和$\varepsilon$-RR进行扰动. 显然，相同隐私预算的情况下，满足Node-LDP时所需注入的噪声量要远高于Edge-LDP. 同理，安全级别上Node-LDP也要远优于Edge-LDP.

2.3   DP的组合性质

LDP与DP的区别在于LDP将隐私保护处理过程从数据采集者端移至用户端，二者的核心仍旧是通过噪声机制将数据扰动加噪，从而达到隐私保护效果. 同时，LDP的后处理过程并不会影响最终的隐私保证，因此LDP也满足DP的组合性质^[28].

引理1. 序列组合性^[29]. 给定任意$n$个随机算法${\left\{ {{\mathcal{A}_i}} \right\}_{1 \leqslant i \leqslant n}}$. 其中，任意算法${\mathcal{A}_i}$满足${\varepsilon _i}$-DP，则按指定顺序组合后的算法${\left\{ {{\mathcal{A}_i}} \right\}_{1 \leqslant i \leqslant n}}$满足$\sum\limits_{i = 1}^n {{\varepsilon _i}}$-DP.

引理2. 并行组合性^[29]. 给定任意$n$个随机算法${\left\{ {{\mathcal{A}_i}} \right\}_{1 \leqslant i \leqslant n}}$. 其中，任意算法${\mathcal{A}_i}$满足${\varepsilon _i}$-DP，同时$n$个算法所作用的数据集不相交，则由上述算法所构成的算法$\left( {{\mathcal{A}_1}\left( {{D_1}} \right),{\mathcal{A}_2}\left( {{D_2}} \right),…,{\mathcal{A}_n}\left( {{D_n}} \right)} \right)$满足$\mathop {\max }\limits_{1 \leqslant i \leqslant n} \left\{ {{\varepsilon _i}} \right\}$-DP.

3.   基于LDP的图统计采集框架

本节阐述基于LDP的图结构数据统计采集（GS-LDP）框架. 分布式图结构数据应用场景下，所有用户仅持有包含自身节点的一阶邻居子图，而非拥有整个图结构数据集，数据采集者（服务提供者）希望能采集到整个图结构数据的度分布、三角计数序列和聚类系数等多个统计指标；为了避免自身的身份隐私和与他人间的关系隐私遭受泄露，用户不愿将自身和他人的原始数据直接共享发布给数据采集者. 故而在数据采集的过程中需要考虑用户的不同隐私需求和数据采集者采集不同统计指标时的数据效用需求.

为了同时实现分布式图结构数据的多个统计指标隐私保护采集，结合Node-LDP和Edge-LDP设计GS-LDP算法，具体构建框架如图2所示.

图  2  基于LDP的图结构数据统计指标采集框架

Figure  2.  The framework of statistical indicators collecting of graph-structure data via LDP

下载: 全尺寸图片 幻灯片

图2中，所提GS-LDP算法主要实现3个统计指标的隐私保护采集，即度分布、三角计数序列和聚类系数. 这3个统计指标差异性较大，其中度分布相对单一，三角计数序列和聚类系数具有复杂结构性. 因此，针对不同的统计指标采集需求，分别设计了基于Node-LDP的度分布、基于Node-LDP的三角计数序列和聚类系数采集，以及基于Edge-LDP的三角计数序列和聚类系数采集算法. 在GS-LDP算法中，三角计数序列和聚类系数2个统计指标的采集依赖于度分布设置阈值，同时聚类系数需要基于三角计数结果进行估计.

1）基于Node-LDP的度分布采集算法. 由于各用户持有子图定点的度值属于各用户可直接计算的数值类数据，采用Edge-LDP采集此类数据将无法有效保护关系隐私. 因此，引入分组机制和SUE机制设计基于Node-LDP的度分布采集算法. 具体如图2中指标Ⅰ所示，以单个用户与数据采集者的交互为例，过程为：首先，数据采集者将初始隐私预算$\varepsilon$和组距$L$发布给用户；其次，用户$i$收到$\varepsilon$和$L$后，根据自身度值${d_i}$和$L$计算组号${g_i}$（${g_i} = \left\lfloor {{{{d_i}} \mathord{\left/ {\vphantom {{{d_i}} L}} \right. } L}} \right\rfloor$）；再次，用户$i$根据${g_i}$将${d_i}$归一化（${d_i} - {g_i}L$），并通过一元编码将归一化的${d_i}$编码成一个维度为$L$的二元度向量；然后，用户$i$通过对称一元编码扰动机制对度向量进行逐位扰动，并将扰动结果发送给数据采集者；最后，数据采集者分组聚合估计各度值的频率，得到满足Node-LDP的度分布结果. 具体算法和证明过程见第4节.

2）基于Node-LDP和Edge-LDP的三角计数序列采集算法. 该算法过程如图2的统计指标Ⅱ所示，具体包含一个参数设置阶段和一个2轮交互过程. 在参数设置阶段，首先，数据采集者将初始隐私预算$\varepsilon$拆分为${\varepsilon _1}$，${\varepsilon _2}$，${\varepsilon _3}$，并将${\varepsilon _1}$、${\varepsilon _2}$、${\varepsilon _3}$、组距$L$和频率上限$Level$发布给每位用户；其次，用户和数据采集者以${\varepsilon _1}$和$L$为参数按照基于Node-LDP的度分布采集算法过程获得图结构数据的度分布估计，并将度频率和达到$Level$时的度值设为度阈值$\theta$（即$\sum\limits_{j = 0}^\theta {{f'_j} \geqslant Level}$，其中${f'_j}$表示度值为$j$的频率估计）. 在第1轮交互中，首先，用户通过$\theta$和Prune算法将自身一阶邻居子图的邻接向量${{\boldsymbol{B}}_i}$进行裁剪；其次，用户通过${\varepsilon _2}$-RR机制对裁剪后的邻接向量${{\boldsymbol{B}}'_i}$进行扰动，将扰动结果${\tilde {\boldsymbol{B}}_i}$发送给数据采集者；然后，数据采集者基于所有用户发送的扰动邻接向量${\tilde {\boldsymbol{B}}_i}$构建噪声图$G'$，并将$G'$发送给各用户. 在第2轮交互中，首先，用户根据${{\boldsymbol{B}}'_i}$和$G'$对自身局部三角计数${T_i}$进行估计；其次，用户通过${\varepsilon _3}$-拉普拉斯机制将估计值扰动后发送给数据采集者；然后，数据采集者对所有用户的估计值进行后处理，获取每个用户的局部三角计数估计${T'_i}$，进而采集满足Node-LDP或Edge-LDP的三角计数序列估计$T' = \left( {{T'_1},{T'_2},…,{T'_n}} \right)$.

在实际中，根据采集三角计数序列的隐私或效用需求，设置不同的${\varepsilon _2}$应用于RR及不同的敏感度应用于拉普拉斯机制，可使得算法满足Node-LDP或Edge-LDP. 具体算法和证明见第5节.

3）基于Node-LDP和Edge-LDP的聚类系数采集算法. 算法过程如图2的统计指标Ⅲ所示，包含3个步骤. 首先，数据采集者将初始隐私预算$\varepsilon$拆分为${\varepsilon _1}$，${\varepsilon _2}$，${\varepsilon _3}$，${\varepsilon _4}$，并将${\varepsilon _1}$、${\varepsilon _2}$、${\varepsilon _3}$、${\varepsilon _4}$、组距$L$和频率上限$Level$发布给每位用户；其次，用户以${\varepsilon _1}$，${\varepsilon _2}$，${\varepsilon _3}$为隐私参数向数据采集者报告三角计数序列估计$T' = \left( {{T'_1},{T'_2},…,{T'_n}} \right)$，并以${\varepsilon _4}$为参数通过拉普拉斯机制向数据采集者报告度值序列$\tilde D = \left( {{d'_1},{d'_2},…,{d'_n}} \right)$；最后，数据采集者根据所获得的$T' = \left( {{T'_1},{T'_2},…,{T'_n}} \right)$和$\tilde D = \left( {{d'_1},{d'_2},…,{d'_n}} \right)$计算全局聚类系数估计$CC' = \left( {C{C'_1},C{C'_2},…,C{C'_n}} \right)$.

类似地，在实际中，可以根据采集分布式图结构数据聚类系数时的隐私或效用需求，设置不同的加噪参数，使算法满足Node-LDP或Edge-LDP. 具体算法和证明见第6节.

需要注意的是，当算法满足Node-LDP时，各分布式用户度值的敏感度为整体图结构数据的最大度值${d_{\max}}$. 在真实分布式场景下：一方面，用户无法在分布式端直接获取全局图结构数据的最大度值${d_{\max}}$；另一方面，真实场景图结构数据往往是稀疏的，敏感度为${d_{\max}}$的拉普拉斯加噪将使噪声过大. 因此，在所设计的算法中，仍采用$\theta$为图结构数据的度阈值，并通过投影技术采集各分布式用户的度值，降低敏感度.

4.   基于Node-LDP的度分布采集算法

面向分布式图结构数据的统计指标采集过程中，现有基于LDP或Edge-LDP的度分布采集算法隐私保护效果不佳；同时，现有的Node-LDP度分布采集算法往往采用拉普拉斯机制加噪^[19]，其加噪敏感度大且投影阈值获取困难. 本节设计基于Node-LDP的分布式图结构数据度分布采集算法来提高隐私保护强度，同时引入分组扰动机制和对称一元编码来提高数据效用. 首先，详细介绍所提算法；其次，给出算法的分析与证明.

4.1   分布式图结构数据的度采集算法

本节给出具体的基于Node-LDP的分布式图结构数据度分布采集算法，即图2中的指标Ⅰ，具体过程如算法1所示.

在算法1中，具体分为5个步骤. 首先，数据采集者向用户发送度频率分布查询请求，并设置用户隐私预算$\varepsilon$和组距$L$. 其次，用户依次计算自身组号${g_i}$，归一化度值（${d_i} - {g_i}L$），并将归一化后的度值编码为一个$L$维的二元度向量${{\boldsymbol{D}}_i}$（行②③）. 再次，用户通过${\varepsilon \mathord{\left/ {\vphantom {\varepsilon 2}} \right. } 2}$-RR逐位扰动${{\boldsymbol{D}}_i}$，并将扰动后的度向量${{\boldsymbol{D}}'_i}$和${g_i}$发送给数据采集者（行④⑤）. 然后，数据采集者获取所有用户数据后，计算总的分组数量和各组用户数量，并按分组依次校正各度值频率（行⑦~⑫）. 例如，以度值$i$为例，设$v = \left\lfloor {{i \mathord{\left/ {\vphantom {i L}} \right. } L}} \right\rfloor$和${n_v}$分别为其所处组号及当前组用户数量，$j = i - \left\lfloor {{i \mathord{\left/ {\vphantom {i L}} \right. } L}} \right\rfloor$为归一化后的度值. 数据采集者计算第$v$组中所有噪声度向量中第$j$位为1的个数，并估计频率：

其中$\displaystyle\sum\limits_{c = 0}^{{n_v}} {{D'_c}\left[ j \right]}$为第$v$组中所有噪声度向量中第$j$位为1的个数. 最后，数据采集者可聚合采集所有度值的频率估计$F' = \left( {{f'_0},{f'_1},…,{f'_{\max L - 1}}} \right)$（行⑬）.

算法1. 基于Node-LDP的度分布算法NLDP-DD.

输入：隐私预算$\varepsilon$，组距$L$；

输出：度频率分布估计$F'$.

/*用户*/

① for $i$ in $\left\{ {1,2,…,n} \right\}$ do

② ${g_i} = \left\lfloor {{{{d_i}} \mathord{\left/ {\vphantom {{{d_i}} L}} \right. } L}} \right\rfloor$；/*用户$i$的组号*/

③　${{\boldsymbol{D}}_i} = Unary - Encoding\left( {{d_i} - {g_i}L} \right)$；/*对用户$i$ 的度 值进行归一化，并将其编码为$L$维二元向量 */

④ 通过${\varepsilon \mathord{\left/ {\vphantom {\varepsilon 2}} \right. } 2}$-RR扰动${{\boldsymbol{D}}_i}$中的每一位

⑤ 将${{\boldsymbol{D}}'_i}$和${{{g}}_i}$发送给数据采集者；

⑥ end for

/*数据采集者*/

⑦ for $v$ in $\left\{ {0,1,…,\max \left\{ {{g_1},{g_2},…,{g_n}} \right\}} \right\}$ do

⑧ ${n_v} = \displaystyle\sum\limits_{i = 0}^n {\left( {{g_i} = v} \right)}$；/*组号为$v$的用户数量*/

⑨ for $j$ in $\left\{ {0,1,…,L - 1} \right\}$ do

⑩　　 ${f'_{j + vL}} = \dfrac{{\displaystyle\sum\limits_{c = 0}^{{n_v}} {{D'_c}\left[ j \right]} - {n_v}q}}{{n\left( {p - q} \right)}}$；/*度值为$j + vL$ 的 频率估计*/

⑪ end for

⑫ end for

⑬ $F' = \left( {{f'_0},{f'_1},…,{f'_{\max L - 1}}} \right)$；

⑭ return $F'$.

在算法1中，采用分组编码扰动的方式控制每个用户度值的报告域值大小，使得算法1在满足Node-LDP的同时采集精度得到提升. 此外，算法1还能进一步避免随机化过程中扰动阈值过大的问题.

4.2   度分布采集算法的隐私效用分析

本节对所提基于Node-LDP的分布式图结构数据度分布采集算法的隐私及效用进行分析. 证明了算法1满足$\varepsilon$-Node-LDP，采集的度值频率估计${f'_i}$具有无偏性，以及${f'_i}$所满足的方差.

定理3. 算法1满足$\varepsilon$-Node-LDP.

证明. 设${{\boldsymbol{D}}_i}$和${{\boldsymbol{D}}_j}$为任意组中的2个$L$维二元度向量，同时设算法$\mathcal{R}$为算法1中各用户扰动度向量时的随机算法. 易知，${{\boldsymbol{D}}_i}$和${{\boldsymbol{D}}_j}$中元素最多有2位不同，其余位上的元素均为0. 设${\boldsymbol{S}} \subseteq range\left( \mathcal{R} \right)$（$\boldsymbol{S}=\left(s_1,s_2,\cdots,s_L\right)$，${s_i} \in \left\{ {0,1} \right\}$）为算法$\mathcal{R}$的随机输出. 不失一般性，设${{\boldsymbol{D}}_i}$和${{\boldsymbol{D}}_j}$仅前2位不同，则有

其中$p = \dfrac{{{{\mathrm{e}}^{{\varepsilon \mathord{\left/ {\vphantom {\varepsilon 2}} \right. } 2}}}}}{{{{\mathrm{e}}^{{\varepsilon \mathord{\left/ {\vphantom {\varepsilon 2}} \right. } 2}}} + 1}}$，$q = 1 - p$. 因此，任意分布式用户报告度向量的随机化过程均满足$\varepsilon$-Node-LDP.

进一步，根据引理2，算法1整体满足$\varepsilon$-Node-LDP. 证毕.

定理4. 算法1所估计的度值频率${f'_i}$是真实频率${f_i}$的无偏估计.

证明. 设$z = \sum\limits_{c = 0}^{{n_v}} {{D'_c}\left[ j \right]}$，即第$v$组中各用户度向量第$j$位为1的数量，则${f'_i} = \dfrac{{z - q{n_v}}}{{n\left( {p - q} \right)}}$，有

设${f_i}$为真实度值为$i$的频率，$w = n{f_i}$为对应的频数，则有

因此，度值频率${f'_i}$是真实频率${f_i}$的无偏估计. 证毕.

定理5. 算法1中估计的任意度值频率${f'_i}$的方差满足

其中${n_v}$为度值$i$所处组$v$的用户数量，$p = \dfrac{{{{\mathrm{e}}^{{\varepsilon \mathord{\left/ {\vphantom {\varepsilon 2}} \right. } 2}}}}}{{{{\mathrm{e}}^{{\varepsilon \mathord{\left/ {\vphantom {\varepsilon 2}} \right. } 2}}} + 1}}$，$q = 1 - p$.

证明. 设$w = n{f_i}$为对应度值$i$的频数，即度值为$i$的用户数量，同时$z = \sum\limits_{c = 0}^{{n_v}} {{D'_c}\left[ j \right]}$，则有

由于$w = n{f_i}$，则

同时，$p + q = 1$. 因此，${f'_i}$的方差为

证毕.

在算法1中，每个用户需要先计算自身组号${g_i}$以及将度值${d_i}$编码为$L$维的二元向量，并对其二元度向量中的每一位进行RR扰动，因此用户的时间复杂度和空间复杂度分别为$O\left( {2L + 1} \right)$和$O\left( {L + 1} \right)$. 对采集者而言，他们需要将每个用户的噪声度向量和组号收集，计算各组用户数量，并依次校正各度值的频率分布，采集者的时间复杂度和空间复杂度均为$O\left( {n\left( {L + 1} \right)} \right)$.

5.   三角计数序列采集算法

在真实分布式图结构数据应用场景下，隐私保护和数据效用需求多样化，分布式用户无法直接获取分布式图结构数据的三角计数序列等与图结构特征密切相关的统计指标，故此类信息采集过程中的用户隐私保护非常具有挑战性. 现有的算法在本地扰动加噪时，还存在添加大量噪声边导致数据效用不高的问题. 本节针对上述问题，首先提出一种Prune算法，用于控制噪声边添加的上限，进而降低实际噪声图中的密集程度；其次，针对隐私及效用需求，基于Prune算法和2轮交互模型分别提出基于Node-LDP的三角计数序列采集算法及基于Edge-LDP的三角序列采集算法；最后，给出三角计数序列采集算法的分析与证明.

5.1   基于Node-LDP的三角计数序列采集算法

诸如社交网络、物联网等真实场景中产生的图结构数据通常是稀疏图，即$n \gg {d_{\max}} \gg {d_{\rm{ave}}}$. 其中，${d_{\max}}$和${d_{\rm{ave}}}$分别为最大度和平均度. 为了应对LDP随机加噪过程中产生过多虚假边，降低采集统计指标的效用问题，本节提出Prune算法，通过将用户邻接向量缩减成一个$\theta$维的二元向量，从而减少随机过程中产生的噪声边，具体过程如算法2所示.

算法2中包含2个步骤：1）在用户持有度值上限$\theta$后，用户可依据$\theta$和邻居真实情况裁剪自己的邻接向量. 以用户$i$为例，若${d_i} > \theta$，则用户$i$随机抽取$\theta$个邻居组成裁剪后的邻接向量${{\boldsymbol{B}}'_i}$，每一位邻居均为1（行①②）. 相反，若${d_i} \leqslant \theta$，则用户将${d_i}$个邻居组成裁剪后邻接向量的前${d_i}$位，并随机抽取$\theta - {d_i}$个非邻居充当邻接向量的后几位，从而组成一个$\theta$维的二元向量（行③④）. 其中，真实邻居对应的位为1，其余为0. 2）在填充${{\boldsymbol{B}}'_i}$完毕之后，用户对${{\boldsymbol{B}}'_i}$进行洗牌，从而避免数据采集者按顺序推导用户的邻居信息（行⑥）. 在此基础之上，用户便可将一个$n$维的邻接向量缩减为$\theta$维. 依据真实图的稀疏性，许多非邻居位将会被移除，从而可一定程度上减少随机化过程产生的噪声边.

算法2. 剪枝算法Prune.

输入：邻接向量${{\boldsymbol{B}}_i} = \left( {{b_1},{b_2},…,{b_n}} \right)$，${b_j} \in \left\{ {0,1} \right\}$，阈值$\theta$；

输出：剪枝后的邻接向量${{\boldsymbol{B}}'_i} = \left( {{b'_1},{b'_2},…,{b'_\theta }} \right)$.

① if $\displaystyle\sum\limits_{j = 1}^n {{b_j} > \theta }$ do /*$\displaystyle\sum\limits_{j = 1}^n {{b_j}}$为用户$i$的度值${d_i}$*/

② ${{\boldsymbol{B}}'_i} = Cut\left( {{{\boldsymbol{B}}_i}} \right) = \left( {{b'_1},{b'_2},…,{b'_\theta }} \right)$；

/*随机选择${{\boldsymbol{B}}_i}$中$\theta$个邻居，并均填充为1， 即　　　 ${b'_j} \in \left\{ 1 \right\}$*/

③ else if $\sum\limits_{j = 1}^n {{b_j} \leqslant \theta }$ do

④ ${{\boldsymbol{B}}'_i} = \left( {{b'_1},{b'_2},…{b'_{\sum\limits_{j = 1}^n {{b_j}} }},…,{b'_\theta }} \right)$；

/*$b'_{j\in \big\{1,{\sum\limits_{j=1}^{n}{b}_{j}}\big\}}\in \left\{1\right\}$，选取$\sum\limits_{j = 1}^n {{b_j}}$个邻居填充为前　　　 $\sum\limits_{j = 1}^n {{b_j}}$位，计为1；${b'_{j \in \big\{ {\sum\limits_{j = 1}^n {{b_j}} ,\theta } \big\}}} \in \left\{ 0 \right\}$，即随机抽取　　　$\theta - {d_i}$个非邻居充当邻接向量的后几位， 计为0*/

⑤ end if

⑥ $Shuf fle\left( {\boldsymbol{B}}_i' \right)$；/*对${{\boldsymbol{B}}'_i}$进行洗牌*/

⑦ return ${{\boldsymbol{B}}'_i}$.

为了能在强隐私保护下采集三角计数序列，我们在算法2的基础之上提出基于Node-LDP的三角计数序列采集算法，具体如算法3所示. 在算法3中，引入2轮交互模型来进一步提升采集结果的数据效用. 其中：第1轮交互用于获取分布式用户的噪声边信息，从而聚合获得噪声图结构数据；随后，数据采集者将噪声图结构数据发送给各分布式用户. 第2轮交互过程中，各分布式用户利用自身一阶邻居子图的邻居信息和噪声图结构数据，计算各自的局部三角计数，并通过拉普拉斯机制对三角计数加噪，加噪后的三角计数发送给数据采集者.

算法3. 基于Node-LDP的三角计数序列采集算法NLDP-TS.

输入：邻接矩阵${\boldsymbol{M}} = \left( {{{\boldsymbol{B}}_1},{{\boldsymbol{B}}_2},…,{{\boldsymbol{B}}_n}} \right)$，${{\boldsymbol{B}}_i} = ( {b_1},{b_2},…, {b_n} )$，${b_j} \in \left\{ {0,1} \right\}$，频率上限$Level$，隐私预算$\varepsilon = {\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3}$，组距$L$；

输出：具备Node-LDP保护的三角计数序列$T' = \left( {{T'_1},{T'_2},…,{T'_n}} \right)$.

/*第1轮交互*/

① $\theta = NLDP {\text{-}} DD\left( {Level,{\varepsilon _1},L} \right)$；

/*调用算法1获取度分布估计，并结合$Level$计　　　算度阈值$\theta$*/

/*用户*/

② for $i$ in $\left\{ {1,2,…,n} \right\}$ do

③ ${{\boldsymbol{B}}'_i} = Prune\left( {{{\boldsymbol{B}}_i},\theta } \right)$； /*裁剪邻接向量*/

④ 通过${{{\varepsilon _2}} \mathord{\left/ {\vphantom {{{\varepsilon _2}} \theta }} \right. } \theta }$-RR扰动${{\boldsymbol{B}}'_i}$中的每一位

/*${B'_i}\left[ j \right]$表示${{\boldsymbol{B}}'_i}$中的第$j$位，${\tilde B_i}\left[ j \right]$（${\tilde {\boldsymbol{B}}_i}$中 的第$j$ 位）　　　表示扰动后的${B'_i}\left[ j \right]$，${\tilde {\boldsymbol{B}}_i}$为经过扰动的${{\boldsymbol{B}}'_i}$*/

⑤ 将${\tilde {\boldsymbol{B}}_i}$发送给数据采集者；

⑥ end for

/*数据采集者*/

⑦ $G' = construct\left( {{{\tilde {\boldsymbol{B}}}_1},{{\tilde {\boldsymbol{B}}}_2},…,{{\tilde {\boldsymbol{B}}}_n}} \right)$；/*构建噪声图*/

⑧ 将噪声图$G'$发送给每个用户；

/*第2轮交互*/

/*用户*/

⑨ for $i$ in $\left\{ {1,2,…,n} \right\}$ do

⑩ /*计算噪声2-star计数*/

${t}_{i}\leftarrow\frac{1}{2}{\left[{\displaystyle \sum _{j=1}^{\theta }B'_{i}{}_{j}\left({\displaystyle \sum _{j=1}^{\theta }B'_{i}{}_{j}-1}\right)}\right]}$；

⑪ /*计算噪声局部三角计数*/

${s}_{i}=|\left({v}_{i},{v}_{j},{v}_{k}\right):j < k,{a}_{i,j}={a}_{i,k}=1{\text{，}}$　　　　$\left({v}_{j},{v}_{k}\right)\text{ }{\mathrm{in}}\text{ }{G}'|$；

/*${a_{i,j}}$表示用户$i$本地端的边缘$(i,j)$是否存在，　　　 若存在记为1，否则记为0*/

⑫ ${w_i} \leftarrow {s_i} - q{t_i}$；

⑬ ${w'_i} \leftarrow {w_i} + Lap\left( {\dfrac{{\theta \left( {\theta - 1} \right)}}{{2{\varepsilon _3}}}} \right)$；

⑭ 将${w'_i}$发送给数据采集者；

⑮ end for

/*数据采集者*/

⑯ for $i$ in $\left\{ {1,2,…,n} \right\}$ do

⑰ ${T'_i} = \dfrac{{{w_i'}}}{{2p - 1}}$；

⑱ end for

⑲ $T' = \left( {{T'_1},{T'_2},…,{T'_n}} \right)$；

⑳ return ${T}^{\prime }.$

算法3中，行①~⑧为第1轮交互，行⑨~⑲为第2轮交互，各分为4个步骤. 第1轮交互中，首先，数据采集者将隐私预算$\varepsilon$拆分为${\varepsilon _1}$，${\varepsilon _2}$，${\varepsilon _3}$，并将${\varepsilon _1}$、${\varepsilon _2}$、${\varepsilon _3}$、组距$L$和频率上限$Level$发布给每位用户. 其次，用户和数据采集者以${\varepsilon _1}$和$L$为参数，通过算法1获取度频率分布估计. 数据采集者根据$Level$计算频率和达到$Level$时的最大度值$\theta$，将其设为度阈值（行①）. 再次，用户根据$\theta$和自身真实邻接向量${{\boldsymbol{B}}_i}$，调用算法2对邻接向量${{\boldsymbol{B}}_i}$进行裁剪，并通过${{{\varepsilon _2}} \mathord{\left/ {\vphantom {{{\varepsilon _2}} \theta }} \right. } \theta }$-RR扰动裁剪后的邻接向量中的每一位，将加噪后的邻接向量${\tilde {\boldsymbol{B}}_i}$发送给数据采集者（行③~⑤）. 最后，数据采集者根据采集到的噪声邻接向量${\tilde {\boldsymbol{B}}_i}$构建噪声图结构数据$G'$，并将其发送给用户（行⑦⑧）. 值得注意的是，$\theta$无需用户或数据采集者自行设置，其由$Level$和度分布估计计算而得，与$Level$成正比，即$Level$越大，$\theta$越大.

第2轮交互中，首先，各分布式用户结合噪声图结构数据$G'$和自身裁剪后的邻接向量${{\boldsymbol{B}}'_i}$计算其局部三角计数. 以用户$i$为例，用户$i$根据裁剪后的${{\boldsymbol{B}}'_i}$计算其真实的2-star计数（行⑩）. 其中，用户$i$的2-star可表示为以其自身为中心节点来连接2条边的子图. 因此，用户$i$的2-star计数可表示为

同时，用户$i$可通过${{\boldsymbol{B}}'_i}$上的真实边缘信息和$G'$中的噪声边信息计算他的噪声局部三角计数（行⑪），即

其中${a_{i,j}}$表示用户$i$本地端的边缘$(i,j)$是否存在，若存在则a_i,j=1，否则$a_{ij}=0$. 其次，用户$i$将${s_i} - q{t_i}$发送给数据采集者. 由数据采集者根据用户发送${t_i}$和${s_i}$，并结合RR校正公式估计其三角计数，即

为了避免直接发送${s_i} -q {t_i}$引发的边缘信息泄露问题，用户向该值添加拉普拉斯噪声，使算法满足Node-LDP. 同时，为了降低满足Node-LDP时添加的噪声量，算法不采用${{{d_{\max}}\left( {{d_{\max}} - 1} \right)} \mathord{\left/ {\vphantom {{{d_{\max}}\left( {{d_{\max}} - 1} \right)} 2}} \right. } 2}$作为敏感度. 用户$i$向${s_i} - q{t_i}$添加敏感度为${{\theta \left( {\theta - 1} \right)} \mathord{\left/ {\vphantom {{\theta \left( {\theta - 1} \right)} 2}} \right. } 2}$的拉普拉斯噪声，使算法满足Node-LDP（行⑫⑬）. 再次，数据采集者估计该用户的三角计数（行⑰），即

最后，数据采集者根据获取的所有分布式用户的局部三角计数，聚合得到满足Node-LDP的三角计数序列$T' = \left( {{T'_1},{T'_2},…,{T'_n}} \right)$（行⑲）.

5.2   基于Edge-LDP的三角计数序列采集算法

为了满足各类场景下不同隐私保护和数据效用需求，进一步提升数据效用并放松隐私保护强度，本节在算法2的基础上提出基于Edge-LDP的三角计数序列采集算法，如算法4所示.

算法4包含2轮交互，行①~⑧为第1轮交互，行⑨~⑲为第2轮交互，各分为4个步骤. 第1轮交互中，首先，数据采集者将隐私预算$\varepsilon$拆分为${\varepsilon _1}$，${\varepsilon _2}$，${\varepsilon _3}$，并将${\varepsilon _1}$、${\varepsilon _2}$、${\varepsilon _3}$、组距$L$和频率上限$Level$发布给每位用户. 其次，用户和数据采集者以${\varepsilon _1}$和$L$为参数，通过算法1获取度频率分布估计. 在算法4中，数据采集者根据$Level$计算频率和达到$Level$时的最大度值$\theta$，并将其设为度阈值（行①）；再次，用户通过$\theta$将其邻接向量${{\boldsymbol{B}}_i}$进行剪枝，获取到剪枝后的邻接向量${{\boldsymbol{B}}'_i}$，并通过${\varepsilon _2}$-RR扰动${{\boldsymbol{B}}'_i}$中的每一位并将其发送给数据采集者（行③④）；最后，数据采集者通过所有用户的噪声向量${\tilde {\boldsymbol{B}}_i}$聚合获得噪声图结构数据$G'$，并将$G'$发给所有分布式用户（行⑦⑧）. 值得注意的是，由于Edge-LDP和Node-LDP下的隐私约束有所不同，因此在满足Edge-LDP时，算法4中用户在第1轮交互中仅需使用${\varepsilon _2}$-RR（行④）即可.

第2轮交互中，首先，所有分布式用户各自依据$G'$和${{\boldsymbol{B}}'_i}$计算其真实2-star计数${t_i}$和噪声三角计数${s_i}$（行⑩⑪）. 其次，用户通过拉普拉斯机制将${s_i} - q{t_i}$加噪扰动后报告给数据采集者. 此处与算法3不同的是，用户仅需向${s_i} - q{t_i}$中添加$Lap\left( {{\theta \mathord{\left/ {\vphantom {\theta {{\varepsilon _3}}}} \right. } {{\varepsilon _3}}}} \right)$的噪声即可满足Edge-LDP. 即用户分别向数据采集者报告${s_i} - q{t_i} + Lap\left( {{\theta \mathord{\left/ {\vphantom {\theta {{\varepsilon _3}}}} \right. } {{\varepsilon _3}}}} \right)$（行⑫⑬）. 再次，数据采集者根据用户发送的数据，结合RR校正公式估计其局部三角计数（行⑰），即

最后，数据采集者可获得每个用户的局部三角计数估计${T'_i}$，进一步得到满足Edge-LDP的三角计数序列估计$T' = \left( {{T'_1},{T'_2},…,{T'_n}} \right)$（行⑲）. 与前述同理，在满足Edge-LDP时，算法4中用户在第2轮交互的报告过程中（行⑬）所使用的参数与算法3不同. （与算法3的不同之处为算法4中行④⑬. ）

算法4. 基于Edge-LDP的三角计数序列采集算法ELDP-TS.

输入：邻接矩阵${\boldsymbol{M}} = \left( {{{\boldsymbol{B}}_1},{{\boldsymbol{B}}_2},…,{{\boldsymbol{B}}_n}} \right)$，${{\boldsymbol{B}}_i} =( {b_1},{b_2},…, {b_n} )$，${b_j} \in \left\{ {0,1} \right\}$，频率上限$Level$，隐私预算$\varepsilon = {\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3}$；

输出：具备Edge-LDP保护的三角计数序列$T' = \left( {{T'_1},{T'_2},…,{T'_n}} \right)$.

/*第1轮交互*/

① $\theta = NLDP {\text{-}} DD\left( {Level,{\varepsilon _1},L} \right)$；

/*用户*/

② for $i$ in $\left\{ {1,2,…,n} \right\}$ do

③ ${{\boldsymbol{B}}'_i} = Prune\left( {{{\boldsymbol{B}}_i},\theta } \right)$；

④ 通过${\varepsilon _2}$-RR扰动${{\boldsymbol{B}}'_i}$中的每一位

⑤ 将${\tilde {\boldsymbol{B}}_i}$发送给数据采集者；

⑥ end for

/*数据采集者*/

⑦ $G' = construct\left( {{{\tilde {\boldsymbol{B}}}_1},{{\tilde {\boldsymbol{B}}}_2},…,{{\tilde {\boldsymbol{B}}}_n}} \right)$；

⑧ 将噪声图$G'$发送给每个用户；

/*第2轮交互*/

/*用户*/

⑨ for $i$ in $\left\{ {1,2,…,n} \right\}$ do

⑩ /*计算噪声2-star计数*/

${t}_{i}\leftarrow\dfrac{1}{2} {\left[{\displaystyle \sum _{j=1}^{\theta }B'_{i}{}_{j}\left({\displaystyle \sum _{j=1}^{\theta }B'_{i}{}_{j}-1}\right)}\right]}$；

⑪ /*计算噪声局部三角计数*/

${s}_{i}=|\left({v}_{i},{v}_{j},{v}_{k}\right):j < k,{a}_{i,j}={a}_{i,k}=1,$　　　　　$\text{ }\left({v}_{j},{v}_{k}\right)\text{ }{\mathrm{in}}\text{ }{G}^{\prime }|$；

⑫ ${w_i} \leftarrow {s_i} - q{t_i}$；

⑬ ${w'_i} \leftarrow {w_i} + Lap\left( {{\theta \mathord{\left/ {\vphantom {\theta {{\varepsilon _3}}}} \right. } {{\varepsilon _3}}}} \right)$；

⑭ 将${w'_i}$发送给数据采集者；

⑮ end for

/*数据采集者*/

⑯ for $i$ in $\left\{ {1,2,…,n} \right\}$ do

⑰ ${T'_i} = \dfrac{{w_i'}}{{2p - 1}}$；

⑱ end for

⑲ $T' = \left( {{T'_1},{T'_2},…,{T'_n}} \right)$；

⑳ return ${T}^{\prime }.$

5.3   三角计数序列采集算法隐私效用分析

本节对所提基于Node-LDP和基于Edge-LDP的三角计数序列采集算法（算法3和算法4）所具备的隐私保证、结果无偏性及估计结果满足的方差上限进行理论分析.

定理6. 算法3满足$\varepsilon$-Node-LDP.

证明. 算法3中存在3个过程提供隐私保障，即通过算法1获取度值上限$\theta$（行①）、通过RR扰动邻接向量（行④）以及向估计值中添加拉普拉斯噪声（行⑬）.

首先，依据定理3可知，通过算法1获取度值上限$\theta$满足${\varepsilon _1}$-Node-LDP.

其次，在通过RR扰动位向量过程中，易知剪枝后的邻接向量${{\boldsymbol{B}}'_i}$是$\theta$维的. 不失一般性，我们假设任意2个${{\boldsymbol{B}}'_i}$和${{\boldsymbol{B}}'_j}$为任意位都不一致的相邻位向量，则通过${{{\varepsilon _2}} \mathord{\left/ {\vphantom {{{\varepsilon _2}} \theta }} \right. } \theta }$-RR扰动时，有

其中$p = \dfrac{{{{\mathrm{e}}^{{{{\varepsilon _2}} \mathord{\left/ {\vphantom {{{\varepsilon _2}} \theta }} \right. } \theta }}}}}{{{{\mathrm{e}}^{{{{\varepsilon _2}} \mathord{\left/ {\vphantom {{{\varepsilon _2}} \theta }} \right. } \theta }}} + 1}}$，$q = 1 - p$，${\boldsymbol{S}}$为${{{\varepsilon _2}} \mathord{\left/ {\vphantom {{{\varepsilon _2}} \theta }} \right. } \theta }$-RR的任意输出值. 因此，该过程满足${\varepsilon _2}$-Node-LDP.

再次，在Node-LDP约束下，删除任意顶点对三角计数的敏感度为${{\theta \left( {\theta - 1} \right)} \mathord{\left/ {\vphantom {{\theta \left( {\theta - 1} \right)} 2}} \right. } 2}$，因此，在报告三角计数过程中添加$Lap\left( {\dfrac{{\theta \left( {\theta - 1} \right)}}{{2{\varepsilon _3}}}} \right)$满足${\varepsilon _3}$-Node-LDP.

根据引理1，算法3提供${\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3}$-Node-LDP. 其中，${\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3} = \varepsilon$，因此算法3满足$\varepsilon$-Node-LDP. 证毕.

定理7. 算法3收集的任意用户局部三角计数${T'_i}$都是真实计数${T_i}$的无偏估计.

证明.

设$t_i^*$为用户$i$的2-star中不包括三角形的计数，即${a_{i,j}} = {a_{i,k}} = 1$，且${a_{k,j}} = 0$（$j < k$）. ${T_i}$为用户$i$的真实局部三角计数，即${a_{i,j}} = {a_{i,k}} = {a_{k,j}} = 1$（$j < k$）. ${s_i}$为用户结合$G'$和${{\boldsymbol{B}}'_i}$计数的噪声三角计数，即${s_i} = \left| \left( {{v_i},{v_j},{v_k}} \right): j < k,{a_{i,j}} = {a_{i,k}} = 1,\left( {{v_j},{v_k}} \right){\text{ }}{\mathrm{in}}{\text{ }}G' \right|$. 同时，设${t_i}$为用户$i$的真实2-star计数，则有${t_i} = t_i^* + {T_i}$. 根据RR的性质，有

则

因此，${T'_i}$是真实计数${T_i}$的无偏估计. 证毕.

定理8. 算法3收集的任意用户局部三角计数${T'_i}$的方差满足

其中$p = \dfrac{{{{\mathrm{e}}^{{{{\varepsilon _2}} \mathord{\left/ {\vphantom {{{\varepsilon _2}} \theta }} \right. } \theta }}}}}{{{{\mathrm{e}}^{{{{\varepsilon _2}} \mathord{\left/ {\vphantom {{{\varepsilon _2}} \theta }} \right. } \theta }}} + 1}}$，$q = \dfrac{1}{{{{\mathrm{e}}^{{{{\varepsilon _2}} \mathord{\left/ {\vphantom {{{\varepsilon _2}} \theta }} \right. } \theta }}} + 1}}$.

证明. 设${t_i}$为用户$i$的2-star计数，$t_i^*$为用户$i$的2-star中不包括三角形的计数，即${a_{i,j}} = {a_{i,k}} = 1$，且${a_{k,j}} = 0$（$j < k$）. ${T_i}$为用户$i$的局部三角计数，即${a_{i,j}} = {a_{i,k}} = {a_{k,j}} = 1$（$j < k$）. 有

证毕.

定理9. 算法4满足${\varepsilon _1}$-Node-LDP＋${\varepsilon _2} + {\varepsilon _3}$-Edge-LDP.

证明. 与算法3一致，算法4也存在3个过程提供隐私保障，即通过算法1获取度值上限$\theta$（行①）. 通过RR扰动位向量（行④）以及通过向估计值中添加拉普拉斯噪声（行⑬）.

首先，依据定理3可知，通过算法1获取度值上限$\theta$满足${\varepsilon _1}$-Node-LDP.

其次，在通过RR扰动位向量过程中，易知剪枝后的位向量${{\boldsymbol{B}}'_i}$是$\theta$维的. 不失一般性，我们假设任意2个${{\boldsymbol{B}}'_i}$和${{\boldsymbol{B}}'_j}$为仅第1位不一致的相邻位向量，则通过${\varepsilon _2}$-RR扰动时，有

其中$p{\text{ = }}\dfrac{{{{\mathrm{e}}^{{\varepsilon _2}}}}}{{{{\mathrm{e}}^{{\varepsilon _2}}} + 1}}$，$q = 1 - p$，${\boldsymbol{S}}$为${\varepsilon _2}$-RR的任意输出值. 因此，该过程满足${\varepsilon _2}$-Edge-LDP.

再次，在Edge -LDP约束下，删除任意顶点对三角计数的影响为$\theta$，即敏感度为$\theta$，因此，在报告三角计数过程中添加$Lap\left( {{\theta \mathord{\left/ {\vphantom {\theta {{\varepsilon _3}}}} \right. } {{\varepsilon _3}}}} \right)$满足${\varepsilon _3}$-Edge-LDP.

综上，根据引理1，算法4满足${\varepsilon _1}$-Node-LDP＋${\varepsilon _2} + {\varepsilon _3}$-Edge-LDP. 证毕.

定理10. 算法4收集的任意用户局部三角计数${T'_i}$都是真实计数${T_i}$的无偏估计.

证明.

与定理7同理，$E\left( {{s_i} - q{t_i}} \right) = \left( {p - q} \right){T_i}$，因此

综上，${T'_i}$是真实计数${T_i}$的无偏估计.证毕.

定理11. 算法4收集的任意用户局部三角计数${T'_i}$的方差满足

其中$p = \dfrac{{{{\mathrm{e}}^{{\varepsilon _2}}}}}{{{{\mathrm{e}}^{{\varepsilon _2}}} + 1}}$，$q = \dfrac{1}{{{{\mathrm{e}}^{{\varepsilon _2}}} + 1}}$.

证明. 设${t_i}$和$t_i^*$分别为用户$i$的2-star计数和2-star中不包括三角形的计数，${T_i}$为用户$i$的局部三角计数，有

证毕.

在算法3和算法4中，首先需要调用算法1，因此该过程中用户的时间复杂度和空间复杂度分别为$O\left( {2L + 1} \right)$和$O\left( {L + 1} \right)$，数据采集者的时间复杂度和空间复杂度均为$O\left( {n\left( {L + 1} \right)} \right)$. 其次，用户需先对邻接向量进行剪枝并扰动剪枝后的位向量，该过程时间复杂度和空间复杂度均为$O\left( {2\theta } \right)$，数据采集者收集所有用户的噪声位向量并聚合噪声图，时间复杂度和空间复杂度均为$O\left( {n\theta } \right)$. 再次，用户需结合噪声图计算三角计数并加噪，时间复杂度和空间复杂度分别为$O\left( {\dfrac{{{d_i}\left( {{d_i} - 1} \right)}}{2} + 1} \right)$和$O\left( {n\theta } \right)$. 最后，数据采集者采集各用户的三角计数，时间复杂度和空间复杂度均为$O\left( n \right)$.

综上，算法3和算法4中用户所需的时间复杂度和空间复杂度分别为$O\left( {2L + 2\theta + \dfrac{{{d_i}\left( {{d_i} - 1} \right)}}{2} + 2} \right)$和$O( L + 1 + ( {n + 2} )\theta )$，数据采集者所需的时间复杂度和空间复杂度均为$O\left( {n\left( {L + 2 + \theta } \right)} \right)$.

6.   聚类系数采集算法

本节在第5节所提算法的基础之上，进一步引入拉普拉斯机制采集分布式用户的度值，设计满足Node-LDP和Edge-LDP的聚类系数采集算法.

6.1   基于Node-LDP的聚类系数采集算法

算法5为所提的基于Node-LDP的聚类系数采集算法，具体分为4个步骤. 首先，数据采集者将隐私预算$\varepsilon$拆分为${\varepsilon _1}$，${\varepsilon _2}$，${\varepsilon _3}$，${\varepsilon _4}$，并将${\varepsilon _1}$、${\varepsilon _2}$、${\varepsilon _3}$、${\varepsilon _4}$、组距$L$和频率上限$Level$发布给每位用户. 其次，用户和数据采集者以${\varepsilon _1}$，${\varepsilon _2}$，${\varepsilon _3}$，$L$，$Level$为参数调用算法3获取度阈值$\theta$以及三角计数序列$T' = \left( {{T'_1},{T'_2},…,{T'_n}} \right)$（行①）. 再次，每个用户通过${\varepsilon _4}$-拉普拉斯机制向数据采集者报告其度值${d_i}$. 值得注意的是，在满足Node-LDP时，度值的敏感度为${d_{{\mathrm{max}}}}$. 显然，向常规图结构数据度值中添加${d_{{\mathrm{max}}}}$的拉普拉斯噪声将使得噪声量过大. 因此我们仍然采用算法3中取得的阈值$\theta$作为度值上限，通过投影方式采集度值. 具体而言，以用户$i$为例，当度值${d_i}$>$\theta$时，用户$i$报告$\theta + Lap\left( {{\theta \mathord{\left/ {\vphantom {\theta {{\varepsilon _4}}}} \right. } {{\varepsilon _4}}}} \right)$，否则直接向真实度值上添加$Lap\left( {{\theta \mathord{\left/ {\vphantom {\theta {{\varepsilon _4}}}} \right. } {{\varepsilon _4}}}} \right)$的噪声并报告（行③~⑦）. 最后，数据采集者便可获取每个用户的局部三角计数估计${T'_i}$和度值估计${d'_i}$，并依据${T'_i}$和${d'_i}$计算每个用户的局部聚类系数估计$C{C'_i}$（行⑫），即

并最终聚合采集满足Node-LDP保护的聚类系数估计$CC' = \left( {C{C'_1},C{C'_2},…,C{C'_n}} \right)$（行⑭）.

算法5. 基于Node-LDP的聚类系数采集算法NLDP-CC.

输入：邻接矩阵${\boldsymbol{M}} = \left( {{{\boldsymbol{B}}_1},{{\boldsymbol{B}}_2},…,{{\boldsymbol{B}}_n}} \right)$，${{\boldsymbol{B}}_i} = \left({b_1},{b_2},…, {b_n} \right)$，${b_j} \in \left\{ {0,1} \right\}$，频率上限$Level$，隐私预算$\varepsilon = {\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3} + {\varepsilon _4}$；

输出：具备Node-LDP保护的聚类系数$CC' = \left( C{C'_1}, C{C'_2},…,C{C'_n} \right)$.

① $T',\theta = NLDP {\text{-}} TS\left( {{\boldsymbol{M}},{\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3},Level} \right)$；

/*调用算法3获取满足Node-LDP的三角计数　　　序列$T'$及度阈值$\theta$*/

/*用户*/

② for $i$ in $\left\{ {1,2,…,n} \right\}$ do

/*对度值进行投影*/

③ if ${d_i} > \theta$ do /*度值大于阈值$\theta$*/

④ 　　　　${d'_i} = \theta + Lap\left( {{\theta \mathord{\left/ {\vphantom {\theta {{\varepsilon _4}}}} \right. } {{\varepsilon _4}}}} \right)$；

⑤ else if ${d_i} \leqslant \theta$ do/*度值小于阈值$\theta$*/

⑥ 　　　　${d'_i} = {d_i} + Lap\left( {{\theta \mathord{\left/ {\vphantom {\theta {{\varepsilon _4}}}} \right. } {{\varepsilon _4}}}} \right)$；

⑦ end if

⑧ 将噪声度值${d'_i}$发送给数据采集者；

⑨ end for

⑩ $\tilde D = \left\{ {{d'_1},{d'_2},…,{d'_n}} \right\}$；

/*数据采集者*/

⑪ for $i$ in $\left\{ {1,2,…,n} \right\}$ do

⑫ $C{C'_i} = \dfrac{{2{T'_i}}}{{{d'_i}\left( {{d'_i} - 1} \right)}}$；

⑬ end for

⑭ $CC' = \left( {C{C'_1},C{C'_2},…,C{C'_n}} \right)$；

⑮ return $CC'$.

6.2   基于Edge-LDP的聚类系数采集算法

本节在算法4和算法5的基础之上，提出基于Edge-LDP的聚类系数采集算法，如算法6所示.

类似地，算法6也可分为4个步骤. 首先，数据采集者将隐私预算$\varepsilon$拆分为${\varepsilon _1}$，${\varepsilon _2}$，${\varepsilon _3}$，${\varepsilon _4}$，并将${\varepsilon _1}$、${\varepsilon _2}$、${\varepsilon _3}$、${\varepsilon _4}$、组距$L$和频率上限$Level$发布给每位用户. 其次，用户和数据采集者以${\varepsilon _1}$，${\varepsilon _2}$，${\varepsilon _3}$，$L$，$Level$为参数调用算法4，获取满足Edge-LDP的三角计数序列$T' = \left( {T'_1}, {T'_2},…,{T'_n} \right)$（行①）. 再次，用户通过${\varepsilon _4}$-拉普拉斯机制报告其度值${d_i}$（行③④）. 与算法5所不同，在满足Edge-LDP时，删除任意一条边敏感度仅为1，敏感度相对较小，因此算法6无需删边投影. 用户在报告度值前仅需向度值中添加敏感度为1的拉普拉斯噪声，即$Lap\left( {{1 \mathord{\left/ {\vphantom {1 {{\varepsilon _4}}}} \right. } {{\varepsilon _4}}}} \right)$. 最后，数据采集者利用每个用户的局部三角计数估计${T'_i}$和度值估计${d'_i}$计算其局部聚类系数估计$C{C'_i}$（行⑦~⑨），并聚合采集满足Edge-LDP的全局聚类系数$CC' = \left( {C{C'_1},C{C'_2},…,C{C'_n}} \right)$（行⑩）.

与算法5不同的是，在采集满足Edge-LDP的聚类系数时，首先算法6需调用算法4采集满足Edge-LDP的三角计数序列（行①）；其次，在Edge-LDP约束下采集度值的敏感度仅为1，因此无需通过投影限制采集过程中的敏感度. 进而，在算法6的度值报告过程中（行③）仅需添加$Lap\left( {{1 \mathord{\left/ {\vphantom {1 {{\varepsilon _4}}}} \right. } {{\varepsilon _4}}}} \right)$即可. （与算法5的不同之处为算法6中的行①③. ）

算法6. 基于Edge-LDP的聚类系数采集算法ELDP-CC.

输入：邻接矩阵${\boldsymbol{M}} = \left( {{{\boldsymbol{B}}_1},{{\boldsymbol{B}}_2},…,{{\boldsymbol{B}}_n}} \right)$，${{\boldsymbol{B}}_i} = \left( {b_1},{b_2},…, {b_n} \right)$，${b_j} \in \left\{ {0,1} \right\}$，频率上限$Level$，隐私预算$\varepsilon = {\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3} + {\varepsilon _4}$；

输出：具备Edge-LDP保护的聚类系数$CC' = ( C{C'_1}, C{C'_2},…,C{C'_n} )$.

① $T' = ELDP {\text{-}} TS\left( {{\boldsymbol{M}},{\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3},Level} \right)$；

/*调用算法5获取满足Edge-LDP的三角计数　　　序列$T'$*/

/*用户*/

② for $i$ in $\left\{ {1,2,…,n} \right\}$ do

③ ${d'_i} = {d_i} + Lap\left( {{1 \mathord{\left/ {\vphantom {1 {{\varepsilon _4}}}} \right. } {{\varepsilon _4}}}} \right)$；

④ 将噪声度值${d'_i}$发送给数据采集者；

⑤ end for

⑥ $\tilde D = \left\{ {{d'_1},{d'_2},…,{d'_n}} \right\}$；

/*数据采集者*/

⑦ for $i$ in $\left\{ {1,2,…,n} \right\}$ do

⑧ $C{C_i} = \dfrac{{2{T'_i}}}{{{d'_i}\left( {{d'_i} - 1} \right)}}$；

⑨ end for

⑩ $CC' = \left( {C{C'_1},C{C'_2},…,C{C'_n}} \right)$；

⑪ return $CC'$.

6.3   聚类系数采集算法隐私效用分析

本节对基于Node-LDP和基于Edge-LDP的聚类系数采集算法（算法5和算法6）具备的隐私保证、结果无偏向及估计结果满足的方差上限进行理论分析.

定理12. 算法5满足$\varepsilon$-Node-LDP.

证明. 算法5中，需调用算法3获取用户三角计数序列估计（行①），并由用户通过拉普拉斯机制报告自身度值（行③~⑦）.

首先，根据定理6可知，算法3满足${\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3}$-Node-LDP.

其次，在Node-LDP约束下，删除任意顶点敏感度为$\theta$，因此在报告度值时添加$Lap\left( {{\theta \mathord{\left/ {\vphantom {\theta {{\varepsilon _4}}}} \right. } {{\varepsilon _4}}}} \right)$的噪声满足${\varepsilon _4}$-Node-LDP.

综上，依据引理1可知，算法5满足${\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3} + {\varepsilon _4}$-Node-LDP（${\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3} + {\varepsilon _4} = \varepsilon$），因此算法5满足$\varepsilon$-Node-LDP. 证毕.

定理13. 算法5收集的任意用户局部聚类系数$CC'_i$都是真实局部聚类系数$C{C_i}$的无偏估计.

证明.

依据定理7可知，$E\left( {{T'_i}} \right) = {T_i}$，因此有

因此，任意用户局部聚类系数$C{C'_i}$都是真实局部聚类系数$C{C_i}$的无偏估计. 证毕.

定理14. 算法5收集的任意用户局部聚类系数$C{C'_i}$的方差满足

其中$p = \dfrac{{{{\mathrm{e}}^{{{{\varepsilon _2}} \mathord{\left/ {\vphantom {{{\varepsilon _2}} \theta }} \right. } \theta }}}}}{{{{\mathrm{e}}^{{{{\varepsilon _2}} \mathord{\left/ {\vphantom {{{\varepsilon _2}} \theta }} \right. } \theta }}} + 1}}$，$q = 1 - p$.

证明.

依据定理8可知

同时，

根据文献[12]可知

进一步地，

因此，有

综上，

证毕.

定理15. 算法6满足${\varepsilon _1}$-Node-LDP＋${\varepsilon _2} + {\varepsilon _3} + {\varepsilon _4}$-Edge-LDP.

证明. 算法6中，需调用算法4获取用户三角计数序列估计（行①），并由用户通过拉普拉斯机制报告自身度值（行③）.

首先，根据定理9可知，算法4满足${\varepsilon _1}$-Node-LDP+${\varepsilon _2} + {\varepsilon _3}$-Edge-LDP.

其次，在Edge-LDP约束下，删除任意顶点敏感度为1，因此在报告度值时添加$Lap\left( {{1 \mathord{\left/ {\vphantom {1 {{\varepsilon _4}}}} \right. } {{\varepsilon _4}}}} \right)$满足${\varepsilon _4}$-Edge-LDP.

综上，依据引理1可知，算法6满足${\varepsilon _1}$-Node-LDP+${\varepsilon _2} + {\varepsilon _3} + {\varepsilon _4}$-Edge-LDP. 证毕.

定理16. 算法6收集的任意用户局部聚类系数$C{C'_i}$都是真实局部聚类系数$C{C_i}$的无偏估计.

证明.

依据定理10可知，$E\left( {{T'_i}} \right) = {T_i}$，因此有

因此，任意用户局部聚类系数$C{C'_i}$都是真实局部聚类系数$C{C_i}$的无偏估计. 证毕.

定理17. 算法6收集的任意用户局部聚类系数$C{C'_i}$方差满足

其中$p = \dfrac{{{{\mathrm{e}}^{{\varepsilon _2}}}}}{{{{\mathrm{e}}^{{\varepsilon _2}}} + 1}}$，$q = 1 - p$.

证明.

依据定理11可知

同时，依据文献[12]，

综上，

证毕.

在算法5和算法6中，需要调用算法3和算法4. 由5.3节可知，该过程中用户所需的时间复杂度和空间复杂度分别为$O\left( {2\left( {L + \theta + 1} \right) + \dfrac{{{d_i}\left( {{d_i} - 1} \right)}}{2}} \right)$和$O\left( L + 1 + \right. \left. \left( {n + 2} \right)\theta \right)$，数据采集者所需的时间复杂度和空间复杂度均为$O( n( L + 2 + \theta ) )$. 此外，每个用户需报告自身度值，时间复杂度和空间复杂度均为$O\left( 1 \right)$. 数据采集者需根据用户的度值序列和三角计数序列依次计算每个用户的局部聚类系数，其时间复杂度和空间复杂度分别为$O\left( n \right)$和$O\left( {2n} \right)$.

综上所述，在算法5和算法6中，用户所需的时间复杂度和空间复杂度分别为$O\left( {2\left( {L + \theta } \right) + \dfrac{{{d_i}\left( {{d_i} - 1} \right)}}{2} + 3} \right)$和$O\left( {L + 2 + \left( {n + 2} \right)\theta } \right)$，数据采集者的时间复杂度和空间复杂度分别为$O\left( {n\left( {L + 3 + \theta } \right)} \right)$和$O\left( {n\left( {L + 4 + \theta } \right)} \right)$.

7.   实验分析

为评估所提出的GS-LDP算法在采集分布式图结构数据的不同统计指标（度分布、三角计数序列及聚类系数）时的效果，本节选取多个公开真实数据集及生成数据集进行实验分析，并与其他同类图结构数据统计指标采集算法进行对比分析. 本节所有实验均在Windows 10上运行，采用Inter Core i5-6200U CPU，A4000-16G-ARM和Python3.8实现.

7.1   实验设置

本文实验数据集选取了Stanford Large Network Dataset Collection网站上3个具有代表性的真实图结构数据集，这些数据集也被广泛应用于图结构数据隐私保护研究中^{[12,14,16-17]}. 由于公开数据集都是非分布式的图结构数据，为了有效评估不同算法在分布式图机构数据采集中的隐私保护效果，本文采用与文献[9, 12, 14, 16-17]相同的数据处理方法，对实验图结构数据集进行了分布式处理，使得每个分布式用户仅持有单个顶点的一阶邻居子图.

实验选取的图结构数据集分别为Facebook，AstroPh，Email-Enron，表2简要分析了数据集包含的节点数、边数，以及最大度和平均度等特征信息.

表  2  真实图结构数据集的主要特征

Table  2.  Main Characteristics of the Real Graph-Structure Datasets

数据集	节点数	边数	最大度	平均度
Facebook	4039	88234	1045	43.7
AstroPh	18772	198110	504	21.1
Email-Enron	36692	367662	1383	10

下载: 导出CSV 

| 显示表格

为对比分析图结构数据的不同统计指标的采集结果效用，在实验中采用均方误差（mean squared error, MSE）和平均绝对误差（mean absolute error, MAE）两个指标进行量化对比. 以度分布为例，设$F = \left( {{f_1},{f_2},…,{f_l}} \right)$和$F' = \left( {{f'_1},{f'_2},…,{f'_l}} \right)$分别为原始图结构数据的度频率分布和隐私保护采集的度频率分布，$MSE = \dfrac{1}{l}{\displaystyle\sum\limits_{i = 1}^l {\left( {{f_i} - {f'_i}} \right)} ^2}$和$MAE = \dfrac{1}{l}\displaystyle\sum\limits_{i = 1}^l {\left| {{f_i} - {f'_i}} \right|}$. 其中，MSE和MAE值越小，则表明度分布采集结果$F'$的效用越优.

7.2   算法对比与分析

本文所提GS-LDP算法可满足不同隐私保护强度和数据效用需求的分布式图结构数据多统计指标采集. 在此方面，与现有的基于DP的分布式图结构数据统计指标采集算法具有明显差异. 为了更好地表现这些算法间的不同，凸显GS-LDP的优势，本节进行了理论对比与分析，如表3所示.

表  3  不同分布式图结构数据统计指标采集算法对比

Table  3.  Comparison of Different Statistics Collecting Algorithms of Distributed Graph Structural Data

统计指标	采集不同指标时具备的 特征及时间复杂度	算法
		GS-LDP（本文）	RJ[16]	NodeProj[19]	EdgeProj[19]	RNL[8]	Local2Round△[9]	LF-GDPR[12]
度分布	是否支持采集	√	√	√	√	×	×	×
	满足的隐私约束	Node-LDP	LDP	Node-LDP	Node-LDP
	用户时间复杂度	$O\left( {2L + 1} \right)$	$O\left( 1 \right)$	$O\left( {3K + 1} \right)$	$O\left( {3K + \theta } \right)$
	数据采集者时间复杂度	$O\left( {n\left( {L + 1} \right)} \right)$	$O\left( n \right)$	$O\left( \begin{gathered} K\left( {n + 1} \right) + n \\ \end{gathered} \right)$	$O\left( {\left( {K + n} \right)\left( {n + 1} \right)} \right)$
三角计数序列	是否支持采集	√	×	×	×	√	√	×
	满足的隐私约束	Node-LDP Edge-LDP				Edge-LDP	Edge-LDP Node-LDP
	用户时间复杂度	$O\left( \begin{gathered} 2\left( {L + \theta + 1} \right) + \\ \frac{{{d_i}\left( {{d_i} - 1} \right)}}{2} \\ \end{gathered} \right)$				$O\left( n \right)$	$O\left( \begin{gathered} 2 + \frac{n}{2} + \\ \frac{{{d_i}\left( {{d_i} - 1} \right)}}{2} \\ \end{gathered} \right)$
	数据采集者时间复杂度	$O\left( {n\left( {L + 2 + \theta } \right)} \right)$				$O\left( \begin{gathered} 2n+ \\ {n^2} \\ \end{gathered} \right)$	$O\left( {\dfrac{{2n + {n^2}}}{2}} \right)$
聚类系数	是否支持采集	√	×	×	×	√	√	√
	满足的隐私约束	Node-LDP Edge-LDP				Edge-LDP	Edge-LDP Node-LDP	Edge-LDP
	用户时间复杂度	$O\left( \begin{gathered} 2\left( {L + \theta } \right) + \\ \frac{{{d_i}\left( {{d_i} - 1} \right)}}{2} + 3 \\ \end{gathered} \right)$				$O\left( n \right)$	$O\left( \begin{gathered} 2 + \frac{n}{2} + \\ \frac{{{d_i}\left( {{d_i} - 1} \right)}}{2} \\ \end{gathered} \right)$	$O\left( {n + 1} \right)$
	数据采集者时间复杂度	$O\left( {n\left( {L + 3 + \theta } \right)} \right)$				$O\left( \begin{gathered} 4n + \\ {n^2} \\ \end{gathered} \right)$	$O\left( {\dfrac{{4n + {n^2}}}{2}} \right)$	$O\left( {3n + \dfrac{{{n^2}}}{2}} \right)$
注：采集满足的隐私约束，若未标记下划线，则原始文献所提的算法满足该隐私约束；若标记下划线，则原始文献所提的算法不满足该隐私约束，在本文实验中将其扩展为满足该隐私约束（具有一定实用性）以便进行实验对比.

下载: 导出CSV 

| 显示表格

由表3知，GS-LDP可采集满足Node-LDP的度分布，还可采集满足Node-LDP和Edge-LDP约束的三角计数序列及聚类系数. 算法RJ、NodeProj^[19]和EdgeProj^[19]仅能采集度分布这一单一图结构数据统计指标. 其中，RJ直接对分布式节点的度值进行本地差分加噪，其仅满足LDP，无法有效保护图结构数据节点间的结构隐私；NodeProj和EdgeProj均可采集满足Node-LDP的度分布估计，但二者需要花费更多的隐私预算以获取度阈值，进而依据度阈值对度值进行加噪扰动，因此其整体数据效用会受到影响；GS-LDP在采集度分布时满足Node-LDP，采用分组机制和一元编码机制降低差分加噪量，提高度分布的数据效用，相较于NodeProj和EdgeProj具有更优的效用优势.

算法RNL^[8]和Local2Round_△^[9]都仅满足Edge-LDP，且能同时应用于采集三角计数序列和聚类系数，但是不能有效采集度分布. 其中，RNL通过RR机制扰动子图的邻接向量并进一步聚合得到噪声图结构数据，以此对三角技术序列和聚类系数进行估计；Local2Round_△在RNL基础上引入2轮交互模型降低估计中的噪声量；GS-LDP在采集三角计数序列和聚类系数时，通过引入Prune算法和2轮交互算法减少随机化过程及报告过程中的噪声量，相较于RNL和Local2Round_△具有更优的效用优势. 此外，在采集三角计数序列和聚类系数时，GS-LDP可根据不同的参数设置，进而满足Node-LDP和Edge-LDP这2种隐私约束. 考虑到Local2Round_△在Node-LDP设定下仍具备一定实用性，在7.4节和7.5节的对比实验中，将Local2Round_△扩展使得其满足Node-LDP，以便与GS-LDP在满足Node-LDP情况下的三角计数序列和聚类系数采集效用进行对比.

算法IF-GDPR^[12]仅适用于采集聚类系数的算法，且仅满足Edge-LDP，其在算法RNL的基础上引入拉普拉斯机制和优化机制采集度值，从而结合噪声图信息提升采集聚类系数的精度. 而GS-LDP除了能采集聚类系数，还能同时采集度分布和三角计数序列，且能根据数据效用和隐私需求采用满足Edge-LDP或Node-LDP的隐私参数.

为了明确分析算法GS-LDP与其他不同算法在采集分布式图结构数据的不同统计指标时的时间复杂度差异，分为不同统计指标进行分析，如表3所示.

1）度分布. GS-LDP在采集度分布时用户和数据采集者的时间复杂度分别为$O\left( {2L + 1} \right)$和$O\left( {n\left( {L + 1} \right)} \right)$，其中，$L$为组距，且$L \ll {d_{\max}}$；算法RJ中用户和数据采集者的时间复杂度分别为$O\left( 1 \right)$和$O\left( n \right)$；算法NodeProj中用户和数据采集者的时间复杂度分别为$O\left( {3K + 1} \right)$和$O\left( {K\left( {n + 1} \right) + n} \right)$；算法EdgeProj中用户和数据采集者的时间复杂度分别为$O\left( {3K + \theta } \right)$和$O\left( {\left( {K + n} \right)\left( {n + 1} \right)} \right)$，其中$K \leqslant {d_{\max}},\theta \leqslant {d_{\max}},{d_{\max}} \ll n$. 可见，GS-LDP的时间复杂度高于RJ，优于NodeProj和EdgeProj. 但由于RJ满足传统LDP，不能保护图结构数据的结构性隐私，而GS-LDP，NodeProj，EdgeProj都满足Node-LDP，故GS-LDP在同类度采集算法中具有效率优势.

2）三角计数序列. GS-LDP在采集三角计数序列时，用户和数据采集者的时间复杂度分别为$O\Bigg( 2\left( L + \theta + \right. \Bigg.$ $\left.\left. 1 \right) + \dfrac{{{d_i}\left( {{d_i} - 1} \right)}}{2} \right)$和$O\left( {n\left( {L + 2 + \theta } \right)} \right)$，其中，$L \ll {d_{\max}}, {d_i} \leqslant {d_{\max}}, \theta \leqslant {d_{\max}},{d_{\max}} \ll n$；算法RNL中用户和数据采集者的时间复杂度分别为$O\left( n \right)$和$O\left( {2n + {n^2}} \right)$；算法Local2Round_△中用户和采集者的时间复杂度分别$O\left( {2 + \dfrac{{n + {d_i}\left( {{d_i} - 1} \right)}}{2}} \right)$和$O\left( {\dfrac{{2n + {n^2}}}{2}} \right)$. 可见，3种算法中用户的计算时间开销相差不大；而GS-LDP中数据采集者的计算时间开销要显著小于RNL和Local2Round_△. 故而，GS-LDP在采集三角计数序列时具备显著的效率优势.

3）聚类系数. GS-LDP在采集聚类系数时，用户和数据采集者的时间复杂度分别为$O\left( 2\left( L + \theta \right) + \right. \left. \dfrac{{{d_i}\left( {{d_i} - 1} \right)}}{2} + 3 \right)$和$O\left( {n\left( {L + 3 + \theta } \right)} \right)$，其中$L \ll {d_{\max}}, {d_i} \leqslant {d_{\max}},\theta \leqslant {d_{\max}},{d_{\max}} \ll n$；算法RNL中用户和数据采集者的时间复杂度分别为$O\left( n \right)$和$O\left( {4n + {n^2}} \right)$；算法Local2Round_△中用户和数据采集者的时间复杂度分别$O\left( {2 + \dfrac{{n + {d_i}\left( {{d_i} - 1} \right)}}{2}} \right)$和$O\left( {\dfrac{{2n + {n^2}}}{2}} \right)$；算法LF-GDPR中用户和数据采集者的时间复杂度分别$O\left( {n + 1} \right)$和$O\left( {3n + \dfrac{{{n^2}}}{2}} \right)$. 可见，4种不同算法中用户的计算时间开销相差不大；而GS-LDP中数据采集者的计算时间开销要显著小于其他3种算法.

7.3   度分布采集效用对比与分析

本节对比算法GS-LDP，NodeProj，EdgeProj，RJ在采集度分布时的效用差异.

在对比实验中，对4种不同的算法均设定隐私预算$\varepsilon \in \left\{ {0.5,1.0,1.5,2.0,2.5,3.0} \right\}$和$L = 10$，对比算法在3个数据集上采集度分布时的效用. 实验结果如图3所示，其中图3（a）~（c）分别为不同算法在3个数据集上的MSE效用对比结果，图3（d）~（f）分别为不同算法在3个数据集上的MAE效用对比结果.

图  3  4种不同度分布采集算法的效用对比

Figure  3.  Utility comparison of four different degree distribution collecting algorithms

下载: 全尺寸图片 幻灯片

由图3可知，所提算法GS-LDP在采集度分布时的效用显著优于NodeProj和EdgeProj，但差于RJ. 具体而言，如图3（a）（d）所示，当数据集为Facebook时，GS-LDP相较于NodeProj和EdgeProj，MSE和MAE分别降低了63%~99%和19%~90%；相较于RJ，MSE和MAE分别提升了68%~90%和43%~73%. 类似地，如图3（b）（c）和图3（e）（f）所示，当数据集为AstroPh和Email-Enron时，GS-LDP的数据效用比NodeProj和EdgeProj具有明显优势，但略差于RJ.

所提出的基于Node-LDP的度分布采集算法的效用大幅度提升的原因是，GS-LDP采用了分组编码的方式，通过SUE机制扰动分布式用户的度向量，从而在满足Node-LDP的同时，减少所添加的噪声. 此外，RJ仅为传统的LDP算法，并不能保护图结构数据的结构隐私，隐私约束相对宽松. 因此相较于RJ，GS-LDP在采集度分布时具备略微的效用劣势，但隐私保护强度要远优于RJ.

总体而言，GS-LDP满足Node-LDP，在提高隐私保护效果的同时提升了采集度分布的效用.

7.4   三角计数序列采集效用对比与分析

本节将对比GS-LDP与RNL，Local2Round_△采集三角计数序列时的效用差异.

由7.2节可知，GS-LDP和Local2Round_△可满足2种隐私约束，而RNL仅能在Edge-LDP约束下具备实用性. 因此，在对比实验中，对3种算法均设定隐私预算为$\varepsilon\in \left\{ {1,2,3,4,5,6} \right\}$和$L = 10$，对比不同算法在3个数据集上采集不同隐私约束（Node-LDP和Edge-LDP）三角计数序列时的效用，实验结果如图4和图5所示. 在此，通过在算法名后加Node和Edge符号作为满足Edge-LDP和Node-LDP约束的区分. 其中图4为GS-LDP-Edge，RNL-Edge，Local2Round_△-Edge的效用对比结果，图5为GS-LDP-Node和Local2Round_△-Node的效用对比结果，其中，满足Edge-LDP的实验中$Level = 0.98$，满足Node-LDP的实验中$Level = 0.8$.

图  4  满足Edge-LDP约束时不同三角计数序列采集算法的效用对比

Figure  4.  Utility comparison of different triangle count sequence collecting algorithms when meeting Edge-LDP requirements

下载: 全尺寸图片 幻灯片

图  5  满足Node-LDP约束时不同三角计数序列采集算法的效用对比

Figure  5.  Utility comparison of different triangle count sequence collecting algorithms when meeting Node-LDP requirements

下载: 全尺寸图片 幻灯片

由图4可知，在大多数情况下，所提算法GS-LDP在Edge-LDP约束下采集分布式图结构数据三角计数序列时的效用在2个指标度量下较RNL-Edge和Local2Round_△-Edge具备一定的优势. 具体而言，如图4（a）（d）所示，在数据集Facebook上，当$\varepsilon \in \left\{ {1,2,3} \right\}$时，GS-LDP-Edge相比其他2个算法的MSE和MAE分别降低了14%~99%和50%~99%，而当$\varepsilon \in \left\{ {4,5,6} \right\}$时，GS-LDP-Edge相较于Local2Round_△-Edge的MSE有－36%~10%的波动，MAE降低了51%~62%，但相较于RNL-Edge在MSE和MAE上具备一定的劣势. 同理，如图4（b）（c）和图4（e）（f）所示，在数据集AstroPh和Email-Enron上，无论隐私预算$\varepsilon$为何值，GS-LDP-Edge相较于Local2Round_△-Edge在MSE和MAE上均存在不同程度的优势. 而与RNL-Edge相比，当$\varepsilon \in \left\{ {1,2,3,4} \right\}$时GS-LDP-Edge具备明显的效用优势，但当$\varepsilon \in \left\{ {5,6} \right\}$时GS-LDP-Edge的效用较RNL-Edge存在劣势.

整体而言，在不同数据集上，GS-LDP-Edge相较于RNL-Edge的MSE和MAE随着隐私预算$\varepsilon$的取值不同而各有优势，而相较于Local2Round_△-Edge具备明显优势；特别是隐私预算$\varepsilon$较小时，GS-LDP-Edge效用优势更为突出. 具体而言，在满足Edge-LDP约束及隐私预算较小时，Prune算法和2轮交互模型在一定程度上可以减少三角计数估计过程中的噪声量；但当隐私预算$\varepsilon$较大时，噪声量的减少使得Prune算法可能会删掉部分无需删除的边从而导致最终估计精度受一定影响. 但整体而言，在大多数情况下，GS-LDP-Edge仍然具备相应的效用优势.

由图5可知，所提出的基于Node-LDP的分布式图结构数据三角计数序列采集算法GS-LDP-Node的效用在2个指标度量下都优于算法Local2Round_△-Node. 具体而言，如图5（a）（d）所示，在数据集Facebook上，当$\varepsilon \in \left\{ {1,2,3,4,5,6} \right\}$时，GS-LDP-Node相较于Local2Round_△-Node的MSE和MAE分别降低了74%~96%及58%~84%. 类似地，如图5（b）（c）和图5（e）（f）所示，在数据集AstroPh和Email-Enron上，GS-LDP-Node的数据效用也明显优于Local2Round_△-Node. 所提出的基于Node-LDP的三角计数序列采集算法的效用大幅度提升的原因是Prune算法可大幅度限制噪声边的数量以及解决Node-LDP随机化过程隐私预算分配过小等问题，进而提升估计精度.

7.5   聚类系数对比实验分析

本节将对比所提算法GS-LDP与算法RNL，Local2Round_△，IF-GDPR在采集聚类系数时的效用差异.

由7.2节可知，GS-LDP和Local2Round_△可满足2种隐私约束，而RNL和IF-GDPR仅能在Edge-LDP约束下具备实用性. 因此，在对比实验中，分别设置2组实验，测试满足Edge-LDP时算法GS-LDP与RNL，Local2Round_△，IF-GDPR的效用差异以及满足Node-LDP时GS-LDP与Local2Round_△的效用差异.

首先，设置隐私预算$\varepsilon \in \left\{ {1,2,3,4,5,6} \right\}$，$L = 10$和$Level = 0.98$，将所提基于Edge-LDP的分布式图结构数据聚类系数采集算法与算法RNL-Edge，Local2Round_△-Edge，IF-GDPR-Edge在表2中3个真实数据集上进行效用对比，结果如图6所示；其次，由于真实数据集上的稀疏性，GS-LDP-Node和Local2Round_△-Node的效用差距也难以彰显. 因此，采取在生成数据集上测试算法GS-LDP-Node和Local2Round_△-Node采集聚类系数的效用. 实验设置$\varepsilon \in \left\{ {5,10,15} \right\}$，$L = 10$，$Level = 0.5$，生成数据集规模$n \in \left\{ 1\times10^{3},2\times10^{3}, …,\right. \left. 15\times10^{3} \right\}$，将所提基于Node-LDP的分布式图结构数据聚类系数采集算法GS-LDP-Node与Local2Round_△-Node的效用对比，结果如图7所示.

图  6  满足Edge-LDP约束时不同聚类系数采集算法的效用对比

Figure  6.  Utility comparison of different clustering coefficient collecting algorithms when meeting Edge-LDP requirements

下载: 全尺寸图片 幻灯片

图  7  满足Node-LDP约束时不同聚类系数采集算法的效用对比

Figure  7.  Utility comparison of different clustering coefficient collecting algorithms when meeting Node-LDP requirements

下载: 全尺寸图片 幻灯片

由图6可知，在不同的数据集上，GS-LDP-Edge相较于其他算法效用表现各有不同. 在数据集Facebook和Email-Enron上时，如图6（a）（c）和图6（d）（f）所示，IF-GDPR-Edge的数据效用最优，GS-LDP-Edge与Local2Round_△-Edge的数据效用相近，且大多数情况下都比RNL-Edge的数据效用更优. 特别是当隐私预算$\varepsilon$<5时，算法GS-LDP-Edge相比于RNL-Edge的数据效用优势更加明显. 在数据集AstroPh上，如图6（b）（e）所示，无论隐私预算$\varepsilon$如何取值，GS-LDP-Edge的数据效用都比RNL-Edge和Local2Round_△-Edge更优，MSE和MAE分别降低了0.3%~50%和−1%~43%. 同时，与IF-GDPR-Edge的数据效用相比在隐私预算$\varepsilon$取值不同时各有优势，当$\varepsilon \in \left\{ {2,3,4} \right\}$，GS-LDP-Edge相较于IF-GDPR-Edge在MSE和MAE上降低了4%~13%和4%~8%，而当$\varepsilon \in \left\{ {1,5,6} \right\}$时，GS-LDP-Edge在MSE和MAE具有−2%~−11%和−4%~−10%的劣势.

整体而言，随着数据集的规模和隐私预算$\varepsilon$的逐步增大，GS-LDP-Edge相较于RNL-Edge和Local2Round_△-Edge的数据效用优势越大，且逐步与算法IF-GDPR-Edge的效用越接近. 具体原因与采集满足Egde-LDP约束下三角计数序列时大同小异，Prune算法和2轮交互模型在一定程度上可以减少三角计数估计过程中的噪声量，整体可提升聚类系数的估计精度. 但与IF-GDPR相比，GS-LDP-Edge无法进一步引入度值优化机制，因而最终的聚类系数估计精度较算法IF-GDPR优势各异.

由图7可知，随着生成图结构数据集的规模逐步扩大，无论隐私预算$\varepsilon$取何值，GS-LDP-Node 的数据效用均优于Local2Round_△-Node，MAE和MSE分别降低了6%~23%和5%~20%. 与7.4节同理，Prune算法可大幅度限制噪声边的数量以及Node-LDP随机化过程隐私预算过小等问题；且GS-LDP-Node可通过度分布算法获取阈值，在一定程度上也可降低度值报告过程中所需添加的噪声量，进而可提升估计精度.

7.6   通信代价分析

GS-LDP和Local2Round_△^[9]在采集三角计数序列和聚类系数时，都应用2轮交互机制在第2轮交互中需要数据采集者将噪声数据下发给各分布式用户，以便用户能对自身局部三角计数进行估计. GS-LDP引入算法Prune降低了噪声结构数据中的噪声边的数量，能够降低噪声图结构数据下发时的通信代价. 为直观表明GS-LDP的通信优势，本节将GS-LDP与Local2Round_△进行通信代价实验对比分析. 同时，进一步引入文献[13]中的算法ARRTwoNS_△进行通信代价实验对比，其中ARRTwoNS_△是Imola等人^[13]在Local2Round_△基础上引入边采样方法所提出的一种低通信代价的三角计数采集算法，其通过对噪声图进行采样下载，从而减少通信代价和其他计算开销. 因此，本节分别对比上述3个算法交互过程中下载所需的通信代价，结果如图8所示.

图  8  通信代价实验分析

Figure  8.  Experimental analysis of communication cost

下载: 全尺寸图片 幻灯片

图8中，设置了2组实验. 首先，在数据集Facebook上设置隐私预算$\varepsilon\in \left\{ {1,2,3,4,5,6,7} \right\}$，$L = 10$，$Level = 0.98$，验证算法GS-LDP，Local2Round_△，ARRTwoNS_△分别在满足Edge-LDP和Node-LDP时，在第2轮交互过程中噪声图结构数据下载的通信数据量，结果如图8（a）（b）；其次，数据集规模为$n \in \left\{ 1\times10^{3},2\times10^{3}, \right. \left. 3\times10^{3},4\times10^{3},5\times10^{3} \right\}$的生成图设置隐私预算$\varepsilon = 5$，$L = 10$，$Level = 0.5$，验证算法GS-LDP，Local2Round_△，ARRTwoNS_△分别在满足Edge-LDP和Node-LDP时，在第2轮交互过程中噪声图结构数据下载的通信数据量，结果如图8（c）（d）.

由图8（a）（b）可知，GS-LDP在真实数据集上，无论满足Edde-LDP还是满足Node-LDP时，其通信代价都显著低于算法Local2Round_△，特别是隐私预算$\varepsilon$越小，GS-LDP的优势越大；而相较于ARRTwoNS_△而言，满足Node-LDP时GS-LDP仍旧具备显著的优势；但在满足Edge-LDP时，GS-LDP仅在隐私预算$\varepsilon$较小时具备通信代价优势，但随着隐私预算$\varepsilon$的逐步上升，GS-LDP则具备一定的劣势. 进一步地，由图8（c）（d）可知，在模拟的生成图结构数据集上，GS-LDP的通信代价依旧远小于Local2Round_△，特别是数据规模越大，GS-LDP的优势越大. 但相对于ARRTwoNS_△而言，实验结果与真实数据集结果一致，即满足Node-LDP时GS-LDP具备显著优势，而满足Edge-LDP时GS-LDP所需的通信代价较ARRTwoNS_△存在劣势.

GS-LDP在满足Node-LDP时相较于Local2Round_△和ARRTwoNS_△具备显著通信代价优势的原因在于，GS-LDP分配了部分隐私预算以通过度分布过程获得更小的度值扰动阈值，并以此对各个用户的子图邻接向量进行裁剪，大幅度减少添加的噪声边，降低通信代价. 同理，在满足Edge-LDP时，GS-LDP相较于Local2Round_△仍旧能够一定程度地通过裁剪算法优化随机化过程中存在的噪声边，降低下载过程中所需的通信代价. 但是，由于在Edge-LDP下，噪声边缘的增加量相较于Node-LDP会弱化许多，且噪声边缘的增加程度与隐私预算$\varepsilon$成反比，因此仍需直接下载噪声图的GS-LDP相较于使用采样方法的ARRTwoNS_△而言在满足Edge-LDP时，通信代价具备一定的劣势.

7.7   其他参数影响

本文所提算法GS-LDP在采集度分布、三角计数序列及聚类系数时，均需设置合理的组距$L$和频率上限$Level$，以达到更优的效用. 因此，本节分别测试$L$和$Level$对GS-LDP在Edge-LDP和Node-LDP下收集的统计指标的效用影响，主要分为2个部分. 此处，本节采用Facebook数据集和生成图结构数据集进行实验，并使用MSE作为度量指标.

1）无论是采集度分布，还是采集三角计数序列和聚类系数时，组距$L$均需被调用. 因此，设置$L \in\left\{10,15,20,25,30\right\}$，分别测试其对各统计指标的影响，实验结果如图9所示. 首先，针对度分布采集，设置$\varepsilon\in\left\{0.5,1.0,1.5,2.0,2.5,3.0\right\}$进行实验，结果如图9（a）所示. 可直观看出，随着$L$的逐步上升，GS-LDP在收集度分布时的效用随之降低. 具体原因在于，更小的$L$对应于SUE扰动的阈值更小，可一定程度减少噪声输入量，进而提升采集精度. 其次，设置$\varepsilon \in \left\{ {1,2,3,4,5,6} \right\}$和$Level = 0.98$对Edge-LDP约束下采集三角计数序列和聚类系数时的效用进行测试，实验结果如图9（b）（c）所示. 与度分布同理，二者的效用也随着$L$的逐步下降而上升. 原因在于，随着$L$的下降，度分布效用逐步上升，使得度阈值更精确，从而可避免删除过多有效边. 再次，我们分别设置$\varepsilon \in \left\{ {1,2,3,4,5,6} \right\}$和$Level = 0.8$，在Facebook数据集上测试GS-LDP在Node-LDP约束下采集三角计数序列的效用，并设置$\varepsilon = 5$及$Level = 0.5$在生成图上测试Node-LDP约束下GS-LDP采集聚类系数的效用，其中生成图的大小为$n \in \left\{ 6\times10^{3},8\times10^{3},\right. \left.10\times10^{3},12\times10^{3}, 15\times10^{3} \right\}$，实验结果分别为图9（d）（e）. 如图9（d）（e）所示，GS-LDP在满足Node-LDP时采集三角计数序列和聚类系数的效用与$L$不具备线性关系. 同时，随着隐私预算$\varepsilon$的逐步上升，无论$L$为何值，GS-LDP的效用均相近. 具体原因为，GS-LDP在Node-LDP下采集三角计数序列和聚类系数时，随机化过程的噪声量更大，尽管$L$会影响度分布的精度，但相较于Node-LDP约束下随机化过程所产生的噪声量仍较小. 最后，由于$L$的值还对应于算法1中用户报告的噪声度向量的长度，进而将会影响各分布式用户度向量报告过程所需的时间开销. 因此，在Facebook数据集上测试采集度分布时，$L$对分布式用户时间开销的影响的实验结果如图9（f）所示. 如图9（f）所示，可直观看出，GS-LDP采集度分布时，用户所需的时间开销随着$L$的增大而上升. 整体而言，在条件允许的情况下，$L$可设置相对较小，以保证低时间开销的同时提供更优的效用.

图  9  $L$对MSE的影响

Figure  9.  The impact of $L$ on MSE

下载: 全尺寸图片 幻灯片

2）GS-LDP采集三角计数序列和聚类系数时，需通过频率上限$Level$设定合理的度阈值$\theta$. 因此，设置$Level\in \left\{0.5,0.6,0.7,0.8,0.9,0.98\right\}$，分别测试$Level$对三角计数序列和聚类系数指标采集的影响. 其中，由于计算$\theta$时使用的是度分布估计，可能造成阈值溢出问题，因此使用$Level = 0.98$代替$Level = 1$. 实验结果如图10所示. 首先，设置$\varepsilon \in \left\{ {1,2,3,4,5,6} \right\}$和$L = 10$，测试Edge-LDP约束下$Level$对GS-LDP采集三角计数序列和聚类系数的效用影响，如图10（a）（b）所示. 可直观发现，三角计数序列和聚类系数的效用随$Level$的增大而逐步上升，当$Level = 0.98$时，效用最优. 具体原因为：$\theta$与$Level$成正比，随着$Level$的逐步上升，$\theta$值越大. 因此，在满足Edge-LDP时，其能够在通过剪枝算法弱化噪声量的同时避免删除过多有效边，进而可将效用最大化. 其次，设置$\varepsilon \in \left\{ {1,2,3,4,5,6} \right\}$和$L = 10$，在Facebook数据集上测试Node-LDP约束下$Level$对GS-LDP采集三角计数序列的效用影响；同时，设置$\varepsilon = 5$和$L = 10$，在生成图上测试Node-LDP约束下聚类系数的采集效用，其中生成图大小$n \in \left\{ 6\times10^{3},8\times10^{3}, \right. \left.10\times10^{3},12\times10^{3},15\times10^{3} \right\}$，实验结果分别为图10（c）（d）. 如图10（c）（d）所示，在满足Node-LDP时，GS-LDP采集三角计数序列和聚类系数时的效用与$Level$成反比. 具体原因为：在满足Node-LDP时，随机响应机制所产生的噪声量更高. 此时，更小的$\theta$可更好地限制噪声边的上限，进而可采集更高效用的指标. 因此，可得出结论，当需要在Edge-LDP约束下采集统计时，可在条件允许的情况下将$Level$设置大一些（但不能设为1，因为可能造成阈值溢出）；而当需要在Node-LDP约束下采集统计时，则可将$Level$设置小一些，以保证更优的采集效用.

图  10  $Level$对MSE的影响

Figure  10.  The impact of $Level$ on MSE

下载: 全尺寸图片 幻灯片

8.   结　　论

本文提出一种基于LDP的分布式图结构数据统计指标采集算法GS-LDP，旨在满足不同隐私保护强度和数据效用需求的同时实现图结构数据多统计指标高效用采集. 首先，针对特性单一且易泄露隐私的度分布，采取分组机制和对称一元编码机制进行扰动采集，使算法满足Node-LDP的同时采集数据效用更高的度分布. 其次，针对强结构性统计指标（三角计数序列和聚类系数），提出剪枝算法解决随机过程中噪声边添加过多的问题. 进一步地，根据分布式图结构场景不同的隐私性和安全性需求，结合剪枝算法和2轮交互模型分别提出基于Node-LDP和Edge-LDP的三角计数序列和聚类系数采集算法，同时提高算法安全性和数据效用. 最后，利用真实数据集和生成数据集对不同的图结构数据统计指标采集算法进行理论和实验对比，结果表明所提算法在采集度分布、三角计数序列和聚类系数时有显著的优势，同时大幅度降低了2轮交互采集算法的通信代价.