基于差分隐私的社交网络隐私保护*

黄茜茜，蒋千越，蒋 琳，熊圳天

(1.哈尔滨工业大学 计算机科学与技术学院，广东 深圳 518000;2.国防科学技术大学 计算机学院，湖南 长沙 410000)

0 引言

社交网络的飞速发展为人们工作生活带来了极大的便利，而其中的个人隐私问题也越来越引发关注和担忧。在社交网络上公开信息是用户的自愿活动，用户通常不知道谁能够访问他们的数据以及他们的数据如何被使用，社交网络中包含很多敏感信息，比如个人信息、朋友关系等，攻击者甚至可能通过个体与个体之间的连接来推断他们的朋友关系以及其他敏感信息。社交网络的隐私保护是以网络节点为对象，利用某种隐私保护模型对其敏感信息进行保护。

对社交网络的研究通常将其抽象为图结构，即形式化为G=(V,E)，图G表示社交网络，每个个体抽象化为一个节点，V表示节点集，节点之间的链接关系用边表示，E代表边集。还可以用三元组表示G=(V,E,W)，其中W表示边上的权值。

常用的隐私保护技术有SWEENEY L提出的k-anonymity[1]、MACHANAVJJHALA A等提出的l-diversity[2]和LI N等提出的t-closeness[3]等，以及在这些模型基础上不断完善的隐私模型。这些基于匿名方法的模型能够在一定程度上保护社交网络的隐私信息，但是对于拥有背景知识的攻击者却无能为力。比如对于匿名发布的社交网络图，攻击者从外部信息得知其中某两个节点来自同一个研究小组，那么攻击者就有很大把握推断他们是朋友关系。

DWORK C提出的差分隐私(Differential Privacy)[4]近年来成为新的研究热点。差分隐私是一种严格的且能被证明的隐私定义，其基本思想是对原始数据或者统计结果添加噪音，使攻击者无法区分某个记录加入或者删除于某个数据集。差分隐私技术能够抵抗攻击者所具有的背景知识，并且根据其隐私参数ε，在隐私保护程度和数据可用性之间取得良好的平衡。

研究人员已经将差分隐私应用于社交网络的隐私保护上，并且取得了很好的效果。本文首先对社交网络中的特点和隐私威胁进行了介绍，然后对差分隐私的定义进行了阐述，最后结合前人所做的研究，着重对差分隐私在社交网络隐私保护的应用进行了综述。

1 社交网络上的隐私信息

可将社交网络图分为有向图和无向图，本文只研究连通的无向图的隐私保护。社交网络的隐私信息包括节点隐私(个体隐私信息)、边隐私(个体之间的连接关系)、图结构隐私[5]。下面将对社交网络的隐私特点进行叙述。

1.1 节点隐私

Twitter、新浪微博上的用户即可看作社交网络的节点。节点隐私信息可分为下面两类：

(1) 存在性信息，可根据某节点是否存在于某个社交网络图获取。比如在Twitter中，某用户是否被其他用户关注。

(2) 标识符信息，可细分为身份信息(Identifier, ID)、准标识符信息(Quasi-Identifier, QI)和敏感信息(Sensitive Attribute, SA)。身份信息即用户的唯一身份；准标识符本身并不是唯一的标识符，但可以与其他准标识符组合以创建唯一标识符，攻击者可利用准标识符信息进行重识别攻击；敏感信息指用户不愿发布的隐私信息，泄露会导致严重的影响。

1.2 边隐私

社交网络中的边通常表示节点之间的关系，比如微信中的朋友关系、新浪微博中用户之间互相关注等等。边的隐私信息中最重要的是边权重信息，边权重信息表示两个节点的紧密程度，权重越大，节点之间联系的越紧密。例如微信上两个用户频繁交流的次数。攻击者可以根据权重信息进行攻击，挖掘出隐私信息。

我们的目标是在尽可能保持数据可用性的情况下保护社交网络中的权重信息。DAS S等[6]提出边权重的匿名。他们提出了一个线性规划模型来保护图的一些性质，比如最短路径、最小生成树等，这些都是权重的线性函数。LIU L等[7]设计了两种权重保护方法：基于图论的高斯随机乘法和贪婪摄动算法。

这些方法都是对于边隐私信息的初步保护，难以抵抗拥有背景知识的攻击者的攻击，后面将会介绍用差分隐私技术对边隐私信息的保护[8-9]。

1.3 图结构隐私

图的结构隐私信息是社交网络图特有的，比如节点度数、邻接信息、中心区域距离以及图的割集等。图结构信息的隐私保护更为重要。ZHOU B等[10]提供了保护图邻接信息的一种方法，将k-anonymity应用于对邻接信息的处理，能对图的隐私信息进行有效的保护。

节点度数指与目标节点直接链接的节点数目，如果攻击者得到某节点的度信息，可以与数据中节点的度数信息进行比对，获取该节点的隐私。攻击者还可以通过节点度数进行链接攻击。

2 差分隐私的定义

2.1 (ε,δ)-差分隐私

给定某随机函数K，若函数K在给定的相邻数据集D1和D2(二者至多相差一条记录)上的任意输出结果S(S∈Range(K))满足下面的不等式，则K满足(ε,δ)-差分隐私[11]。

Pr[K(D1)∈S]≤exp(ε)*Pr[K(D2)∈S]+δ

(1)

其中，δ是松弛因子，如果δ=0，则随机函数K给出严格的ε-差分隐私[12]。ε称为隐私参数，用来平衡隐私保护程度和数据可用性。ε越小，隐私保护程度越高，而数据可用性越低。实现差分隐私技术需要引入噪声，而噪声大小与数据集的全局敏感性密切相关，下面介绍全局敏感性。

2.2 全局敏感性

对于任意的查询函数Q:D→Rk(函数Q将数据集D映射到k维的实数空间)，函数Q的全局敏感性[8]由ΔQ表示：

(2)

D1和D2是相邻的数据集，全局敏感性衡量对相邻数据集作查询操作的所得到的最大差异，比如一个数据集插入或者删除一条记录后所得到的最大查询差异值。

2.3 噪声机制

最常用的噪声机制[11]是Laplace机制，它通过Laplace分布产生噪声对查询操作产生的输出值进行扰动，使攻击者无法区分真实值和扰动后的值，从而实现差分隐私保护。如下：

对于任意查询函数Q:D→Rk，全局敏感性为ΔQ，随机算法K(D)=Q(D)+Y满足ε-差分隐私，其中Y～(Lap(ΔQ/ε))k为添加的Laplace噪声，是k维的独立同分布的向量。噪声大小与全局敏感性ΔQ成正比，与隐私参数ε成反比，即ΔQ越大，ε越小，添加的噪声越大，隐私保护效果越好，数据可用性越低。

3 差分隐私在社交网络隐私保护的应用

3.1 边-差分隐私和点-差分隐私

因为传统差分隐私要求两个数据集是相邻的数据集，即二者只相差一条记录，那么应用到社交网络图中可以分为边-差分隐私和点-差分隐私[13]。对于边-差分隐私，要求图G′为图G删除或添加某一条边得到的。形式化定义为对于任意图G=(V,E)，G′=(V′,E′)，它们是边相邻的，如果对于任一条边e∈E′，满足V′=V,E′=E-{e}。HAY M等[14]对边-差分隐私做了扩展，提出k边-差分隐私,即图G′为图G删除或添加k条边得到的。对于点-差分隐私，要求图G′为图G删除或添加某一点以及与该点相关联的所有边。即G=(V,E)，G′=(V′,E′)，它们是点相邻的，如果对于任一点x∈V，如果V′=V-x，E′=E-{(v1,v2)|v1=x∨v2=x}。点-差分隐私比边-差分隐私提供更强的隐私保护，但对数据可用性的破坏也更严重。例如在一个星形的社交网络图中，一个点与其他所有点相连接，删除该点后，图中不存在任何一条边，完全失去研究价值。实验证明，k边-差分隐私能够和点-差分隐私提供相同的隐私保护。

3.2 权重信息的隐私保护

边权重是社交网络图中重要的信息，很多数据发布者将边权重作为图的统计信息。LI X等[15]提出MB-CI(Merging Barrels and Consistency Inference)方法来保护带权社交网络图。该方法通过将权重序列看作非属性的柱状图，再将差分隐私应用于柱状图中。该方法的独到之处在于网络图中很多边有相同的权重，可以把有相同计数的桶合并(即Merging Barrels)，这样可以减少所需的噪声量。除此之外，由于噪声本身的原因，简单的合并操作可能会泄露隐私，作者根据权重序列的原始顺序做一致性推理(Consistency Inference)，这是重要的后处理步骤。实验证明这种方法能很好提高数据的可用性。COSTEA S等[16]分析差分隐私如何用于边权重的隐私保护上，通过Dijkstra最短路径算法来评估发布数据的质量，得出具有较大权重值的网络图适合应用差分隐私技术进行保护的结论。

3.3 社交网络图的度数信息发布

度数分布是网络图的重要特征，直接发布度数信息可能导致隐私的泄露。HAY M等[14]利用改进的差分隐私技术，对含噪声的度数分布查询执行后处理步骤，证明可以在不牺牲隐私的情况下提高准确性，获得更为精确的度数分布。DAY W Y等[17]通过投影方法降低敏感度，研究在点-差分隐私下的度数分布的发布问题。在满足点-差分隐私的条件下对网络图作投影，使图的最大度数不超过度数阈值θ，并且在投影过程中尽量保护隐私信息。作者提出基于聚合和累积直方图的方法来发布度数分布。实验表明，这两种方法大大减少了逼近真实度数分布的误差，相对于现有的工作具有显着的改进。KARWA V等[18]研究了度数序列的发布问题，在满足差分隐私的条件下保护了隐私，同时允许分析人员使用发布的数据执行统计推断。

3.4 合成图的发布

因为差分隐私的本质是对数据作扰动，所以如果在原始图中加入大量噪声的话，很难得到可发布的有价值的合成图。SUN Y等[19]提出保护数据可用性的关键是在合成图中保留重要数据的原始值与否。作者分析了图数据的k三角形计数(图数据的一种统计信息)，提出了满足边-差分隐私的合成图发布的新方法，名为NoiseGraph。实验结果显示NoiseGraph在很低的隐私预算下，仍然能保证合成图的k三角形计数是精确的。QIN Z等[20]提出了LDPGen，一种满足本地差分隐私的合成图生成技术。每次用户报道信息时，LDPGen注入噪声确保本地差分隐私。在此过程中推导出最佳参数，将结构相似的用户聚集在一起。一旦获得了良好的用户聚类，LDPGen就会调整现有的社交图生成模型来构建新的合成图。WANG Y等[21]研究了在图生成中实施边-差分隐私的问题，其思想是对从原始网络图学习到的参数加噪声，然后使用加噪后的参数发布合成图。PROSERPIO D等[22]提供了一种基于差分隐私的图合成的工作流程。

3.5 差分隐私在社交网络图的其他应用

AHMED F等[23]利用随机矩阵的投影方法发布社交网络图的结构信息，并且满足差分隐私。关键思想是使用随机投影方法将图的邻接矩阵的每一行投影到一个低维空间中，然后添加少量噪声实现差分隐私。与现有的特征向量(邻接矩阵的特征向量是重要的结构信息)的近似方法相比，该方法计算效率高，保留了效用并满足差分隐私。WANG Y等[24]分析了基于差分隐私保的谱信息(特征值和特征向量)保护，因为经过噪声扰动的输出特征向量不再相互正交，作者通过向量正交技术对输出的特征向量作了后处理。SALA A等[25]提出了一个差分隐私图模型Pygmalion,Pygmalion将图的详细结构提取为度数相关统计量，将噪声引入到结果数据集中，并生成合成图。

LU W等[26]提出了针对于图结构参数估计的指数随机图模型ERGM。ERGM是一个满足差分隐私的统计建模工具，可以让分析人员分析社交网络的结构和形成过程。MIR D等[27]提出参数估计模型stochastic Kronecker graph model来对网络图建模，建立图的参数的估计器。SOMMER等[28]根据差异隐私框架对基于邻近社交网络设置的用户进行匹配，可以准确地配对类似的用户，同时提供不让恶意用户推断隐私信息的保护。

3.6 小结

将上述差分隐私在社交网络隐私保护的应用进行归纳总结，如表1所示。

表1 各种方法优缺点的比较

表1对差分隐私在社交网络隐私保护的应用的各种方法的优缺点进行了比较。各个方法有其特定的应用场景，比如文献[15]等使用KSP测量未改变的最短路径的比例；文献[16]使用Erdos-Renyi模型进行图的生成；文献[14]在合成的数据集和真实的数据集都做了实验验证；文献[17]使用了8个来自不同领域的真实数据集，包括社交网络、引用网络和邮件网络等；文献[18]提出的方法主要估计差分隐私算法产生的度数分布的统计特性；文献[19]在四个真实数据集(GrQc、HepPh、HepTh和wiki-Vote)做了应用场景的模拟等。

4 结论

本文主要讲述了差分隐私在社交网络中的各类应用，如权重信息的隐私保护、度数信息的发布问题、合成图的发布问题等。虽然已经提出了较多的方法，在未来还有很多的研究方向。比如在社交网络图的度数发布上，使用已保存的低度数信息预测高度数节点的分布是未来的一个研究方向；在合成图的发布上，可以考虑其他可用性度量标准，并使合成图满足多个可用性度量标准；在去中心社交网络的隐私保护上，结合更强大的隐私模型、处理权重信息和点/边属性是未来要做的工作。

[1] SWEENEY L. k-anonymity: a model for protecting privacy[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based System, 2002, 10(5): 557-570.

[2] MACHNAVAJJHALA A, KIFER D, GEHRKE J. l-diversity: privacy beyond k-anonymity[C]//Proceedings of the 22nd International Conference on Data Engineering(ICDE). Atlanta, Georgia, USA, 2006: 24-35.

[3] LI N, LI T. t-closeness: privacy beyond k-anonymity and l-diversity[C]//Proceedings of the IEEE International Conference on Data Engineering(ICDE). Istanbul, Turkey, 2007: 106-115.

[4] DWORK C. Differential privacy[C]//Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Venice, Italy, 2006: 1-12.

[5] 张冰，苗水清，李显峰. 社会网络隐私信息研究[J]. 无线互联科技, 2017(22).

[6] DAS S, EGECIOGLU O, ABBADI A E. Anonymizing weighted social network graph[C]//Proceedings of the 26th IEEE International Conference on Data Engineering (ICDE ’10), Long Beach, Calif, USA, 2010:904-907.

[7] LIU L, WANG J et al. Privacy preserving in social networks against sensitive edge disclosure[R]. Tech Rep CMIDA-HiPSCCS 006-08, Department of Computer Science, University of Kentucky, 2008.

[8] TASK C, CLIFTON C. A guide to differential privacy theory in social network analysis[C]//The 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012), Istanbul, Turkey,2012.

[9] XIAO Q, CHEN R, TAN K L. Differentially private network data release via structural inference[M]. KDD, 2014:911-920.

[10] ZHOU B, PEI J. The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks[J]. Knowledge & Information Systems, 2011, 28(1):47-77.

[11] DWORK C, MCSHERRY F, NISSIM K. Calibrating noise to sensitivity in private data analysis[C]//Proceedings of the 3th Theory of Cryptography Conference (TCC). New York, USA, 2006: 365-385.

[12] 孟晓峰，张啸剑. 面向数据发布和分析的差分隐私保护[J]. 计算机学报, 2014,37(4):927-949.

[13] LANGWEG H, MEIER M. Towards a differential privacy theory for edge-labeled directed graphs[M]. Sicherheit 2018, Lecture Notes in Informatics (LNI), Gesellschaft für Informatik, Bonn,2018: 273.

[14] HAY M, LI C, MIKLAU G, et al. Accurate estimation of the degree distribution of private networks[C]//Proceedings of the 2009 Ninth IEEE International Conference on Data Mining, 2009:169-178.

[15] LI X, YANG J, Sun Z, et al. Differential privacy for edge weights in social networks[J]. Security and Communication Networks. Volume 2017, 4(8):1-10.

[16] COSTEA S, BARBU M, RUGHINIS R. Qualitative analysis of differential privacy applied over graph structures[C]//2013 11th RoEduNet International Conference, 2013:1-4.

[17] DAY W Y, LI N, LYU M. Publishing graph degree distribution with node differential privacy[M]. ACM SIGMOD, 2016.

[18] KARWA V, SLAVKOVIC A. Differentially private ′ graphical degree sequences and synthetic graphs[M]. Privacy in Statistical Databases, Springer, 2012.

[19] SUN Y, ZHAO H, Han Q, et al. Composite Graph Publication Considering Important Data[C]//International Conference of Pioneering Computer Scientists, Engineers and Educators. ICPCSEE, 2017: 207-219.

[20] QIN Z, YU T, Yang Y, et al. Generating synthetic decentralized social graphs with local differential privacy[C]//CCS ’17 Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas, Texas, USA, 2017:425-438.

[21] WANG Y, WU X. Preserving differential privacy in degree-correlation based graph generation[M]. TDP, 2013.

[22] PROSERPIO D, GOLDBERG S, MCSHERRY F. A workflow for differentially-private graph synthesis[C]//Proceedings of ACM Workshop on Online Social Networks (WOSN), 2012:13-18.

[23] AHMED F, JIN R, LIU A. A random matrix approach to differential privacy and structure preserved social network graph publishing[J]. arXiv preprint. arXiv:1307.0475, 2013.

[24] WANG Y, WU X, WU L. Differential privacy preserving spectral graph analysis[M]. PAKDD, 2013.

[25] SALA A, ZHAO X, WILSON C, et al. Sharing graphs using differentially private graph models[C]//Proceedings of the 11th ACM SIGCOMM Conference on Internet Measurement. Berlin, Germany, 2011: 81-98.

[26] LU W, MIKLAU G. Exponential random graph estimation under differential privacy[C]//20th ACM SIGKDD International Conference on Knowledge discovery and data mining, 2014:921-930.

[27] MIR D, WRIGHT R. A differentially private estimator for the stochastic Kronecker graph model[C]//EDBT-ICDT’12: Proceedings of the 2012 Joint EDBT/ICDT Workshops, ACM, 2012:167-176.

[28] SOMMER M, LIM L, Li D, et al. A differentially private matching scheme for pairing similar users of proximity based social networking applications[C]//Proceedings of the 51st Hawaii International Conference on System Sciences, 2018.