第一章 绪论
1.1 研究背景
随着移动终端及网络技术的更迭，移动社交网络在世界范围内发展极为迅速，国内移动社交软件微信的注册用户已超 10 亿，微博的活跃用户数也日益增加至超大规模的数据量级。 数以亿计的用户通过各种各样的社交网络与家人朋友直接进行通信和分享信息。然而，用户隐私和安全问题也面临着巨大的威胁。如个人数据被各种数据挖掘工具及有关的背景知识攻击者随意的频繁收集分析，如何保护个人的隐私信息，得到了社会各界的极大关注。在网络环境中，个人数据信息的传播范围大，速度快，影响广，因而也更容易遭受到恶意攻击[1]。而社会网络如今早已成为我们生活中必不可少的一部分，极大改变了我们社会中人员信息联系的交互方式。用户分享的大量个人数据成为了攻击者的理想目标，攻击者可以简单的获取到用户的敏感信息，从而进行各种恶意骚扰，如垃圾邮件、恶意软件、骚扰电话、身份盗窃等[2]。为了保护用户隐私，社交网站通常让用户对自己的信息设置隐私权限，如微博、微信、QQ 等，用户可以规定哪些人可以申请加为好友，并浏览个人信息。但这些设置并不能提供严格的隐私保证，攻击者还可以通过分析用户的数据，推测出用户其他未共享的重要隐私数据，来实施网络犯罪[3]。在当前时代下，传统的隐私保护理论和技术逐渐体现出疲软之态，已无法涵盖大数据隐私的内涵，大数据隐私保护问题需要重新思考与定位[4-6]。
关于社交网络中的隐私保护问题，现存的方法主要有两类：一是基于聚类的方法，如Casas-Roma 等人[7]提出的基于 k-匿名的保护方法，这一类方法主要是将节点（边）按规则分为不同组，并隐藏组内的详细信息，能实现较高的隐私保护程度，但隐藏子图的内部信息严重影响了社交网络的局部结构分析，从而降低了数据可用性，因此如何进行有效的分组以提高数据的可用性成为这类方法需要解决的最大问题。另一类是基于网络图结构的扰动算法，如通过添加、删除和交换等操作修改网络图结构[8-9]，使得发布数据和原始数据产生差异从而起到隐私保护作用，同时也保持了社交网络的原有规模，相比于聚类方法具有较高的数据可用性。其后，Dwork[10]提出差分隐私的概念，能实现数据的强隐私保护。前述的两类方法可以很好结合差分隐私的模型和定义，例如，通过添加、删除等操作修改网络结构图并使其满足差分隐私的需求[11-12]。
............................
1.2 研究目的及意义
本文研究的主要目的是设计基于社交网络的差分隐私技术的隐私保护方案。随着移动社交网络数据的广泛应用和大数据技术的快速发展，用户的个人隐私数据的安全性问题急需解决[15-16]。针对移动社交网络中不同的隐私需求，以及防止用户节点信息重新识别与抵御基于图结构的背景知识攻击，等都拥有重要的研究价值。迄今为止，社交网络中边结构信息的隐私保护研究还有许多的热点问题仍未解决，如针对社交网络图数据中，边权值的隐私保护研究仍然不能满足当下的隐私保护需求，隐私保护的程度不高，数据可用性缺损太多及算法时间复杂度过高效率较差等[17]。
目前在相关的学术会议及顶级的国际期刊中针对社交网络实现差分隐私保护的相关研究，主要的研究成果聚焦在网络结构中的节点以及边的非交互性差分隐私问题点上。但是在现实生活中我们在社交网络中所面临的隐私泄露问题绝非仅限于此，一方面，带边权值的社交网络图所涵盖的信息更加丰富同时隐私保护需求也更大[18]。另一方面差分隐私最初是开发应用在表数据的隐私标准，针对社交网络图数据之间密切的相关性这一不可忽视的重点问题，如何设计符合图要求的隐私处理模型或者考虑将图转化为方便处理的统计数据，进而解决传统的差分隐私并不能很好处理相关数据的隐私泄露[19]。
所以本文的研究重点在于解决社交网络敏感结构数据信息的隐私保护问题，在实现差分隐私保护的前提下，确定一种新的隐私保护强度评价标准，同时也针对带权值的社交网络图数据提出了一种效率更高数据可用性更好的隐私保护方案。使得差分隐私技术在社交网络的隐私保护方面有着更加广阔的发展空间与应用前景。综上所述，本文基于社交网络的差分隐私技术应用研究在理论和实践应用上都有着重要的意义。
...............................
第二章 相关背景知识介绍
2.1 社交网络隐私信息
随着移动终端及网络技术的更迭，移动社交网络在世界范围内发展极为迅速，国内移动社交软件微信的注册用户已超 10 亿，微博的活跃用户数也日益增加至超大规模的数据量级。数以亿计的用户通过各种各样的社交网络与家人朋友直接进行通信和分享信息。通常情况下，社交平台会鼓励用户使用真实信息进行注册，并且这些信息是可以被其他用户直接查看到的，如新浪微博等。
通常，社交网络数据被建模成一个无向图 G=(V，E，W)，其中 E 为图中全体边的集合，V 为全体节点集合，W 为边对应的权值集合。与一般的图结构相比，社交网络图数据还具有“小世界现象”特性以及节点度符合幂律分布。社交网络中，敏感信息即用户的隐私经常遭到数据拥有者不经意的泄露，其中泄漏方式主要分为标识符泄露、连接泄露和属性泄露三种。如何对这些隐私数据进行保护成为当下研究的热点，本文中主要采用差分隐私方式对移动设计网络中的隐私信息进行保护。
..........................
2.2 差分隐私保护模型
2.2.1 差分隐私基本定义
由于差分隐私模型通过对发布数据进行随机扰动，因此从统计意义上讲，无论是否存在背景知识，都不能识别该记录是否在原始数据表中。这种模式的优点是它不需要特殊攻击的前提，不关心攻击者的背景知识，并提供了一个定量分析，显示隐私泄露的风险。
差分隐私的严格数学定义保证了无论单条数据纪录 r 是否存在于数据表 D 中，算法 M 的输出内容的概率几乎不变，而差分隐私框架下的差分隐私系数 ε 一定程度上决定了它们的相似度。
图 2-1 中为算法 M 对数据集 D1和 D2的输出概率密度函数示意图[1]，其中 D1和 D2为存在且仅存在一条记录相异的兄弟数据表。在这两个数据集中，算法 M 的输出概率密度非常相似，并且攻击者仅使用返回的结果来确定数据集 D1和 D2是否不同，这是不容易的。差分隐私策略通过保护数据库中的记录免受攻击者的获知而保护用户的隐私。
..............................
第三章 基于差分隐私的移动社交网络隐私保护方案(PBCN).........................................11
3.1 问题背景 ...................................11
3.2 基于差分隐私的保护方案 PBCN ...................................11
第四章 带权值的大规模社交网络数据隐私保护方法 ............................ 32
4.1 问题背景 .................................... 32
4.2 约束模型 ......................................... 32
第五章 总结与展望 ................................. 55
5.1 总结 .................................. 55
5.2 展望 ............................... 55
第四章 带权值的大规模社交网络数据隐私保护方法
4.1 问题背景
第三章详细叙述了 PBCN 方案，这是一种针对无权值的社交网络图数据隐私保护方案，随着带边权值的社交网络所涵盖的信息日益增加其需求也在不断扩大。在本章中，将设计满足带边权值的大规模社交网络图数据隐私保护方案。在一个带有边权值的社交网络图中，图的一系列属性可以通过边权值的线性组合来表示，因此，可以根据这种线性组合关系生成约束模型，对添加的噪声进行线性约束。该方案的特点在于保证发布数据满足差分隐私保护的同时，极大程度上保留数据可用性。
针对边权值的分析，本实验中 dp-noisy 的隐私预算 ε 取值为 1。如图 4-2 所示，本方法dp-noisy 的扰动效果明显高于 lp-noisy 的扰动效果。数据规模较小时，如图 4-2(a)和(b)所示，lp-noisy 的扰动效果还比较明显，这是因为 lp-noisy 方案通过线性规划方法重新定义单源最短路径上的边权值，并且只对不在路径上的权值噪，对于较低的权值并没有很好的扰动，但由于数据规模小，所达到的效果也算差强人意。如图 4-2(c)和(d)所示，当数据规模较大时用lp-noisy 扰动与原数据差异很小，尤其在权值极大和极小处，lp-noisy 扰动后分布几乎与原始数据一致。出现这种情况是因为数据规模大时，边数的增加会引起约束集的增加，这使得线性规划求出的最优解无限接近与原始数据。而本方法，除了对不在最短路径上的边权值扰动之外，还对线性规划的解添加差分隐私噪声，同时本方法在节点扰动过程中也对权值分布产生了较大改变，在图 4-2(a)(b)(c)(d)可以发现，本方法总能产生非常明显的扰动。
................................
第五章 总结与展望
5.1 总结
本论文的研究目的在移动社交网络和大数据技术快速发展的背景情况下，对用户发布的个人隐私数据的安全保护问题亟待解决。对社交网络中不同的隐私需求，防止节点重新识别与抵御结构背景知识的攻击，阻止网络中的边连接信息被披露等都拥有重要的研究价值。就目前来说，社交网络边结构信息的隐私保护研究还有许多的热点问题，网络结构固有的相关性与差分隐私脆弱的数据相关，隐私保护的程度不高，数据功用缺损太多及算法处理效率不高等。针对这些问题，本文在结合了现有的隐私保护实现技术的基础上提出了一种面向无权值图的基于差分隐私保护方案 PBCN 以及面向带权图的差分隐私保护方法，设计并实现了基于差分隐私保护机制的隐私保护方法和相关的原型系统，该系统满足数据的输入、数据加密、效果监测及数据发布等需求。综上，本文从隐私保护角度出发，针对现存的用户隐私问题所做的主要贡献如下：
1) 提出的 PBCN 方案在达到同等的隐私保护程度的前提下，极大程度上保留了数据的可用性，并且针对社交网络数据规模大，更新速度快的特点，PBCN 在执行效率上具有显著的优势。
2) 根据邻接度的改变量计算隐私保护性参数 P 来从数值上衡量扰动对原始图结构上的影响程度，对隐私保护程度分析具有重要的意义。
3) 针对带权值的社交网络图，提出的基于约束模型添加扰动噪声的方式，可以极大程度上保留原始图中的属性关系从而提高数据可用性。
4) 设计的原型系统具有优秀的交互性，并能够满足使用者的大部分需求，这使得数据拥有者可以将手中的数据对外发布而几乎不会导致隐私泄露问题，提高了数据的使用效率，降低了数据的维护成本。
参考文献（略）