第一章 绪论
研究背景
随着互联网的急速发展与智能移动终端的大量普及，社交网络（Social Network）应运而生。在社交网络中一般都会包含一些敏感的个体信息及属性、个体间的关系、图关系结构等信息，但是这些隐私信息在分析及发布过程中可能被破坏，所以我们对社交网络进行功用信息的处理研究的同时而保护社交网络隐私信息成为目前这一研究领域中一个极其重要的研究课题。社交网络紧紧地依赖于真实存在的社交关系，如图 1.1 所示，社交网络结构看作是节点和节点之间连接关系的集合，节点表示社交网络中的具体个体或单位，而连接关系则表示节点之间存在联系与否。针对社交网络的背景分析，主要是针对其中的节点及其边连接关系，并分析获取其中的网络结构特征，在实际应用中不仅应用于研究具体个体或网络关系，同时还可以分析研究社会现象[1]。
社交网络如今早已成为我们生活中必不可少的一部分，极大的改变了我们社会中人员信息联系的交互方式。如国内的微博及人人网的应用能够使得社会新闻快速传播及网络人物迅速蹿红，这都少不了社交网络关系的推动发展。社交网络可以以一张图结构的形式存在，存在度数较多的中心节点（以微博网络中的明星为例），中心节点将会引出许多条边（粉丝关注），产生出度数较少的节点，社交网络图中可存在多个中心节点，并且相互之间可以产生关系（例如 A 明星和 B 明星是夫妻或者恋人），也可以是一个节点通过某个点认识另一个点（例如通过一个都认识的导演）。某些中心节点与周围节点组成的紧密联系往往会形成单独的社区网络。为确保关系网络中个体的隐私安全，在社交网络发布前需对信息进行隐私保护处理（媒体记者往往会从明星社交网络中的关系变化制造新闻，例如 A 明星取消@B 明星）。社交网络发布的隐私保护，其目的是在保证社会个体敏感信息不被泄漏的情况下实现有效的信息共享，其实现途径大多采用了差分隐私技术。
........................
1.2研究目的及意义
本文研究的主要目的是设计基于社交网络的差分隐私技术的隐私保护方案。在移动社交网络和大数据技术快速发展的背景下，对用户发布的个人隐私数据的安全保护问题亟待解决。对社交网络中不同的隐私需求，防止节点重新识别与抵御结构背景知识的攻击，阻止网络中的边连接信息被披露等都拥有重要的研究价值。就目前来说，社交网络边结构信息的隐私保护研究还有许多的热点问题仍未解决，网络结构固有的相关性与差分隐私脆弱的数据相关保证，隐私保护的程度不高，数据功用缺损太多及算法处理效率不高等。
目前在相关的学术会议及顶级的国际期刊中针对社交网络实现差分隐私保护的相关研究，主要的研究成果聚焦在网络结构中的节点以及对边关系的非交互性差分隐私问题点上。但是在现实生活中我们在社交网络中所面临的隐私泄露问题绝非仅限于此，一方面，在每次图查询没有相关性的非交互情况下的差分隐私保护可以取得很好的效果，但还需考虑当前的用户查询依赖之前的查询知识条件这一点。另一方面差分隐私最初是开发应用在表数据的隐私标准，针对社交网络图数据之间密切的相关性这一不可忽视的重点问题，如何设计符合图要求的隐私处理模型或者考虑将图转化为方便处理的统计数据，进而解决传统的差分隐私并不能很好处理相关数据的隐私泄露。
所以本文的研究重点在于解决社交网络敏感结构数据信息的隐私保护问题，在实现差分隐私测算图结构相关性程度的前提下，使得原有的社交关系通过分组转换和加噪处理后能够较好地保护原有的社交关系隐私，同时也使发布的社区网络数据具有可接受的数据效用。使得差分隐私技术在社交网络的隐私保护方面有着更加广阔的发展空间与应用前景。综上所述，本文基于社交网络的差分隐私技术应用研究在理论和实践应用上都有着重要的意义。
..........................
第二章 面向社交网络的差分隐私研究现状
2.1社交网络隐私信息
在当前互联网相关应用快速普及的背景下，也在国外的 Facebook、Twiter 等社交网站的发展刺激下，中国也出现了大量的 SNS(Social Networking Service)社交网站，其中的许多优秀的社交网站如腾讯、陌陌 、新浪微博、人人网等。在研究社交网络数据背后的知识和潜在价值的同时，伴随而来的也是隐私泄露与保护的问题。在社交网络中，组成社交网络的任何一个元素都可能潜在地涉及到相关的隐私信息，主要包括了结点、边和图结构性质等。在本文中主要对结点隐私、边隐私、图性质隐私等社交网络隐私信息进行介绍。
2.1.1 社交网络数据特点
社交网络是由众多节点及节点间的相互连接关系组成。在其中节点可能是社交网络中的某一个人或机构，而连接关系就是节点之间交流的内容和形式等。通常分析社交网络数据就是对节点间的连接关系来进行分析，从而捕获网络数据的结构特征。在日常生活中不仅可以用于研究个人数据信息，而且也可用于分析各种社会现象等。
社交网络结构图与一般的图结构相比，有两个特性还需满足，即节点度数符合幂律分布和“小世界现象”特性，这些特殊的性质在我们社交社交网络数据处理算法及分析中可能起着特殊的作用。(a)节点度数符合幂律分布：一般当社交网络的规模较大时，节点的度数通常都会满足幂律分布。这一性质已在通信网络、朋友网络等中得到验证。(b)小世界现象：可简单描述为：“你和其他任何一个陌生人之间所相隔的人不会超过 6 位，我们只需要经过 6 个人就可以结交任何一个陌生朋友”，即被称为“6 度分隔现象”，这一特性说明在较大的社交网络中一般只有较小的平均最短路径。
敏感信息就是我们所认为的用户的隐私，在社交网络中有许多的信息都被定义为用户的隐私，即设计社交网络中的隐私模型。一个百万富翁网络中的隐私可能为节点的存在性；一个金融服务网络中的敏感信息可能为节点的度数；一个通信网络中用户联系的频繁程度用节点间权重表示也被视为用户的隐私；一个朋友网络中某一点的子图结构也可被攻击者作为识别目标节点的依据。文献[8]为我们归纳出社交网络数据中的隐私信息的泄露主要被分为三类：标识符泄露、连接泄露、属性泄露。
..........................
2.2差分隐私保护模型
自从 Backstrom[10]等人对社交网络数据的隐私攻击的先驱研究以来，社交网络数据的隐私保护问题已引起越来越多的人的关注，为有效地解决社交网络应用中所面临的隐私和安全隐患，结合差分隐私技术模型的社会网络研究已成为目前国内外研究的热点。差分隐私保护模型假设攻击者获得了数据集中除目标记录信息外的其他所有记录信息，这些信息便是我们理解的攻击者所能掌握的最大背景知识，而差分隐私即使在最大背景知识的假设下也能实现抵御攻击者背景知识的攻击。同时，差分隐私对隐私泄露风险给出了定量化的分析与证明，建立于严格的数学基础之上，较好的保证数据可用性。如何在满足差分隐私的需求下进一步提高发布数据的可用性及算法效率，是当前差分隐私数据发布研究的热点问题。
2.2.1 差分隐私定义及相关概念
差分隐私保护发展于数据失真的隐私保护技术，是通过向敏感数据中添加噪声机制来保证数据隐私与功用性，可以实现在数据集中增删一条数据并不会影响最后的查询结果。
....................
3.1问题背景 ........................ 20
3.2问题描述与系统模型 ................................. 21
3.3基于社区密度聚集和矩阵扰动的差分隐私保护方案 ................. 23
第四章 基于邻接度的边介数模型差分隐私处理方案 ....................... 43
4.1问题背景 ...................... 43
4.2问题描述与系统模型 ........................ 44
4.3dK 图模型的图差分隐私保护处理方案 ...................... 46
第五章 总结与展望 ................... 63
5.1总结 ........................... 63
5.2展望 ......................... 64
第四章 基于邻接度的边介数模型差分隐私处理方案
4.1问题背景
隐私研究人员已经尝试通过图形匿名化技术提高安全性，通过在节点参数和图结构中添加噪声来提高安全性[53]。然而，即使是有引入噪声的图数据也可以进行去匿名化，特别是如果攻击者具有相应的网络数据的背景知识。目前来说，社交网络边结构信息的隐私保护研究还有许多热点亟待解决，社交网络结构固有的相关性与差分隐私脆弱的数据相关，隐私保护程度不高，数据功用缺损太多及算法处理效率不高等。
为了将差分隐私应用到交互式社交网络分析领域，研究者们进行了很多尝试。最早的差分隐私只是用于对社交网络数据进行一些简单的统计分析，如分析其中的节点度分布、属性值分布等。然而，这些应用依然只涉及到了社交网络中的属性信息，而忽略了其中的结构信息。目前，面向社交网络图结构的差分隐私研究大多是针对一类被称作“子图计数查询”的查询函数。子图计数查询只是简单地返回一个图在另一个图中以子图形式出现的次数。尽管如此，只要通过适当的组合，许多重要的图属性都可以通过子图计数查询得到。因此子图计数查询不仅相当有用，而且非常重要。在这些工作中最具代表性的当属“关系差分隐私”框架。关系差分隐私保护的是社交网络中用户之间的社交关系，它保证了社交网络中任何一条边的变动都不会对查询结果造成太大的影响。但是，尽管通过仅允许满足特定条件的子图计数查询，关系差分隐私将需要添加的噪声大小从网络中节点数量的多项式级别（polynomial）减少到了多项式对数级别（poly-logarithmic），相对于查询函数中节点的数目，关系差分隐私需要添加的噪声大小依然是超指数级别的（super-exponential）。对于稍大一些的查询函数，查询结果的可用性依然很难保证。
........................
第五章 总结与展望
5.1总结
本论文的研究主要是为了在现有的社交网络数据隐私发布处理的基础上，弥补现有研究的不足，如网络结构数据的聚类划分分组，差分隐私度结构划分以及网络结构中差分隐私数据相关组合等。并针对这些新问题，结合前人在差分隐私技术、隐私保护社交网络数据技术等方面的若干思路与方法，通常社交网络的处理要么按照节点度数方向的划分，要么是转换为邻接矩阵的思路，如现有的矩阵聚集处理和网络结构图模型构建方案技术等。对在社交网络背景下的差分隐私技术实现的隐私保护进行了深入的研究，如何设计一种有效的差分隐私模型，既能保护社交网络的数据隐私，又能通过掩盖节点间的相互联系而不破坏网络的结构特性。综合以上的要点，本文的主要工作总结如下：
针对社交网络数据的差分隐私发布问题，第三章提出了基于社区密度聚集的矩阵扰动的差分隐私保护方案，引入相关系数 k 确保存在边相关数据的差分隐私及其可用性。具体总结如下：
1）将社区检测算法与社交网络差分隐私相结合，利用模块度 Q 值设计指数差分隐私来截取最佳的社区检测聚集结果，使得社交网络的结构划分可行性较高，根据划分的结果来进行网络节点标签的重新命名也使得网络的密集和稀疏区域更易区分和处理。
2）采用二分树结构对网络邻接矩阵的上三角部分进行密集区域的识别，依据社区检测算法的标签结果可高效识别出社交网络图的密集部分与稀疏连接部分，同时根据识别后划分区域密度聚集的不同来设计具体的边还原分配方法。
3）仿真实验表明，相比其他社交网络的矩阵处理方案，本方案能实现网络区域划分结构化并保持原始数据的相关性，能有效提升数据隐私发布的处理效率，保证隐私性的同时有效提升了数据的可用性，同时采用的上三角部分的矩阵处理杜绝边关系重安排至矩阵对角线处的错误情况，提高数据效用。
参考文献（略）