本文是一篇计算机论文，本文主要分析了图数据统计信息发布过程中存在的问题，给出了相应的隐私保护方案，并通过理论分析了方案满足点差分隐私的约束以及仿真实验证明了所提方案的数据效用性。
第一章绪论
1.1研究背景及意义
尽管近几年，国家与社会高度重视数据隐私，从两会至央视“315”晚会，数据隐私引发的关注度日益增加。大数据时代，数据已经是一种新的生产资源，具有极高的经济价值和社会价值。对数据的分享、分析，挖掘数据中潜在的信息已经成为各行各业分析行业趋势的必要手段。数字时代，数据的广泛利用，伴随而来的是数据安全问题和个人隐私问题。对于大数据环境下人们的隐私安全保护，国家陆续颁行《数据安全法》以及《个人信息保护法》。但从近几年的隐私泄露案例来看，数据安全形式严峻，并不理想。例如，2016年，土耳其5000万公民的敏感信息被黑客公开放在网上，所有人均可随意访问下载；2017年，美国知名信用机构Equifax被黑客窃取了1.43亿名用户的社保、家庭住址等信息，对Equifax在用户中的信誉造成了毁灭性影响；2018年，剑桥分析公司在未经允许地情况下收集了5000万在Facebook上活跃用户数据后，用这些数据预测用户的个人特点和偏好之后，定向向用户推送消息；2019年，国内某人脸识别的公司出现大批数据泄露情况。超250万人的人脸、个人信息等数据遭遇泄露；2020年，Zoom爆发严重的数据泄露，包括会议录像、许多学校网课视频、私人间的亲密对话等视频记录在网上被公开；2021年，亚马逊公司因为违背数据隐私规定而面临欧盟8.88亿美元的巨额罚款，创新了记录。
1.2国内外研究现状
信息技术的飞速发展促生了许多新型信息系统，企业积累了大量的应用数据，图数据作为一种重要的新型数据也随着新型信息系统的产生而变得越来越常见。比如在社交网络中，近几年数据量呈指数增长，在传统关系型数据库上对社交网络进行分析十分困难，无法满足人们对数据日益增长的存储和计算要求。图数据库是专门用来存储图结构数据的数据库，在处理关联性强的数据上性能更强，当前核心数据库有TAO[7]、Pregel[8]、Graphchi[9]等。图数据存储了大量的个人信息，从而导致了许多图数据的发布和挖掘技术。伴随这新技术的出现，仅仅通过匿名化的方式来对数据进行处理达到隐私保护的目的远远不够。现有的文献就指出匿名化技术很容易遭受背景知识攻击和去匿名化攻击等多种攻击方式的攻击，从而使得个人隐私信息遭到泄露。数据发布、场景分析进程中的隐私泄露，严重影响到数据共享取得的效果，如何在保护隐私信息的前提下对图数据安全发布，国内外学者提出了大量解决方案。下面将介绍图数据发布中的传统隐私保护技术和差分隐私保护技术。
1.2.1图数据发布中传统隐私保护技术
目前，传统隐私保护主要有两大类别，在本节的分析中会围绕两类隐私保护技术在图数据中的研究成果开展综合论述。
（1）数据加密。即将消息基于加密函数转换为其他人无法辨识的密文，唯有接受方获得密钥的情况下，才可以将密文转化为明文。常用的基于加密技术的隐私保护模型有安全多方计算[10]、同态加密[11]、数字信封[12]和秘密共享[13]等。
社交网络发布的数据加密[14]是用已有的加密算法对数据加密，通过数学变换或公式将普通数据转换为密文。这样做虽然保护了发布数据的安全，但数据的利用范围只在拥有加密算法密钥的小圈子里，不利于数据的共享和再次利用。2010年，Chase等人[15]提出一种对结构化数据（如网络图）的加密机制，他们将可搜索加密的概念推广到图数据中，实现了在加密图上执行子图查询、邻居查询等操作。2017年，Wang等人[16]针对的大规模图数据提出了一种精确的最短路径查询的图加密方案，该方案为了在多个查询上更好的分摊时间复杂度，将历史查询结果存储在远程服务器上作为“缓存”资源，并允许对加密图进行高效的图更新查询。2019年，Lai等人[17]提出了一个加密的数据结构模型，可以实现在加密图上实现高效的隐私保护社交搜索，设计了一种用于在线社交网络服务的加密图数据库GraphSE2。2020年，Zhang等人[18]提出了一种支持约束最短路径查询的图加密方案，该方案将外包数据的存储和计算分离，使用约束过滤算法来过滤成本值。并提出了两种新颖的比较协议：安全整数比较（SIC）协议和安全最小值（SMin）协议。这两种协议都直接操作密文，从而不会泄漏有关明文的任何信息。Du等人[19]针对云平台不完全受信任的问题，对外包数据的敏感信息开展加密，获得可运用到网络图的结构化的加密方法。其可满足最短距离查询等需求，而且还允许在保证前向隐私的情况下更新加密图，实现了大规模动态图的安全查询。
第二章差分隐私模型
2.1差分隐私
差分隐私模型可以防范攻击者背景知识攻击，具有更高的安全性。差分隐私模型不仅仅是一个概念，而是有对隐私损失的测量，这使对不同的技术进行比较成为可能。
2.1.1定义及相关概念
有些应用场景中，我们希望能够得到“最佳”响应（含噪输出），但是直接对所计算的结果添加噪声则会完全损坏其可用性。例如，对于设定好的竞拍价格，其目的是将收益最大化，同时，出于保护竞价者隐私的考虑，可以对设定的好的最理想的价格添加一个很小的正噪声，但是这可能会极大地减少收入。指数机制的提出正是为了解决上述应用场景中的这种问题。对于具有任意效用且输出是任意非数值的查询，在需要满足差分隐私的前提下，指数机制是响应这些查询必不可少的构件。
在实际应用中，一个事件的隐私保护可能被分成几个过程完成，对该事件进行差分隐私保护，要求对隐私预算进行拆分，划分给不同过程的隐私保护算法。面对这种问情况，差分隐私模型存在两类组合性质加以应对，分别是串行组合性质和并行组合性质。串行组合性质被应用在事件当中数据集没有被分割，事件完成的过程是相关的，这时需要对事件完成过程中的隐私保护算法分配隐私预算，事件的整体隐私保护算法总的隐私预算是个过程中隐私保护算法隐私预算的和。并行组合性质被应用件数据集没有被分割，事件完成的过程是独立的，事件的整体隐私保护算法总的隐私预算是个过程中隐私保护算法隐私预算的最大值。
2.2图数据发布中的差分隐私
图是无固定形状的一种数据结构，其具体形状可结合物理或者抽象问题决定，因为它的逻辑结构能够良好的反应现实世界，经常用来辅助解决某些具体的问题，是常见的一种数据结构。图数据发布中的差分隐私主要分为两种，边差分隐私和点差分隐私。
2.2.1点差分隐私
点差分隐私在图数据发布中保护的是一个节点以及该节点所有连边在图中存在性。一个网络图中，节点代表着实体，边代表联系，实体和边都有带有信息。比如在一个社交网络图中，实体就指用户，实体的信息就指用户的个人隐私信息。边的信息就指用户和外界的联系。如果我们想要保护一个用户在社交网络中的全部隐私，即包括个人的隐私信息和在网络中所有的交际关系。我们一般用点差分隐私来保护，因为在点差分隐私的约束下，图中增加或减少一个节点及与该节点相连的边，图的统计特性查询结果不会因此有较大的改变。这样攻击者就不能确定一个用户具体在不在网络图中，以此来达到隐私保护的目的。
2.2.1边差分隐私
边差分隐私和点差分隐私不同，边差分隐私保护的是图中的边，如在社交网络中，某个用户不想让人知道自己和另外一个人的关系，那么可以用边差分隐私来实现。边差分隐私的约束下，图中增加或减少一边，图的统计特性查询结果不会因此有较大的改变，攻击者就无法断定这个关系存不存在。相较于点差分隐私，边差分隐私的隐私保护能力较弱，但容易实现。
第三章点差分隐私下的三角计数发布算法...............................14
3.1章节引言.........................14
3.2基于图全局结构的图投影算法........................15
第四章基于点差分隐私的动态图节点度直方图发布算法...................27
4.1章节引言.....................................27
4.2增量-投影算法..................................28
第五章总结与展望.................................40
5.1工作总结.................................40
5.2展望..............................41
第四章基于点差分隐私的动态图节点度直方图发布算法
4.1章节引言
随着大数据技术的快速发展，人们对于图数据的处理不再满足于分析静态图数据，因为对静态图数据进行挖掘不能够充分了解到随着时间推移图数据中节点的整体分布和节点间关系发展趋势。例如，医生需要了解某一地区HIV病毒的传播规律，就要在该地区收集多年的HIV患者记录。对照不同年限内的HIV患者数据，通过使用测序技术测量从不同患者获得的HIV序列之间的相似性来推断假定的传播链接，再将这些链接解析为传输网络，随着时间的推移研究这些网络的特性，反映HIV病毒在该地区人群中的传播模式。社会学家想深度分析某热搜话题的传播以及发展进程，就要从增量式的社交网络图着手来研究传播进程的关键节点以及时间。但是动态图之中包含丰富的用户隐私以及敏感数据，怎样在维护隐私的基础上开展统计特性发布，即本章节研究的关键内容。
动态社交网络中一种常用的隐私保护方式是图数据匿名。Bhagat等人[46]认为对每个时间间隔网络单独匿名化网络是不够的，通过比较不同时刻的网络的数据，很容易泄露信息。因此，初始匿名所做的决定会影响以后的迭代，后续匿名化工作必须与初始匿名化保持一致，但是他们并没有给出一种较好的动态匿名方案。考虑到动态社交网络结构变化的复杂性以及现实生活中的社交网络是不断扩大的，Wang等人[47]将动态网络视为一个增量图序列，将连续动态网络离散化，并给出了图序列的匿名化方法。Zhang等人[48]提出了一种动态社交网络有向图K-in&out-degree匿名模型，可以保护动态社交网络有向图的社区结构，同时保证匿名图在不同时间满足匿名性。
第五章总结与展望
5.1工作总结
数字社会，智能时代对数据的共享和分析已经成为主流，如何安全的共享数据已经成为一大难题。面对多种多样的攻击手段，数据安全面临的形势严峻。差分隐私保护模型是一个随机概率模型，因此无需对攻击做特定的背景假设，适用于多种隐私保护情景，具有更高的安全性。并且它有对隐私损失的测量，可以比较不同技术下的隐私保护程度。随着大数据时代到来，社交网络数据、物联网数据等具有图结构性质的数据规模越来越大，对图结构的共享和挖掘越来越频繁，相应的隐私泄露问题也越严重，对图数据的隐私保护也越有必要。
论文的研究内容是在点差分隐私约束下的图数据统计信息发布算法，具体的研究工作包括：
1.研究了社交网络图中节点三角计数的发布问题，针对在点差分隐私下，发布算法敏感度高和图投影过程全局结构发生较大变化这两个问题。提出了一种基于图全局结构特征的图投影算法，该方法参考图中节点的紧密中心度和间接中心度,在图投影的实现过程中保留了原图较完整的结构信息的同时降低了全局敏感度，原图中保留了更多的三角形；在直方图发布阶段,进一步提出了一种基于k-means聚类分组的直方图发布机制，进一步提出了一种采用k-means聚类直方图发布机制，此机制运用统计学中直方图制作分组的思想确定k-means聚类中的聚类个数k，然后将直方图中的桶按数值降序排序，平均分成k个组从每个组中选取一个桶作为k-means算法的初始聚类中心，避免了k-means算法随机选取中心点对聚类结果的影响。理论分析表明我们提出的图投影算法和直方图发布算法是满足点差分隐私约束的，在真实数据集上的仿真实验表明，我们的算法发布结果与原始结果相比，误差更小，数据可用性更高。
2.研究点差分隐私约束下节点度的持续发布问题，针对动态网络随时间更新情况复杂（可能有新的节点和边加入，也可能有旧的节点和边一出）这一问题，我们首先将动态图数据抽象成增量图序列。针对增量图序列的数据量随时间不断增加，增量图序列的度发布的全局敏感度与时间呈正相关这一问题，提出图的增量-投影算法对增量图序列进行投影压缩，得到的压缩图序列仍然是一个增量序列，有效的约束了发布过程的全局敏感度。
参考文献（略）