论文周报——Sharing Graphs using Differentially Private Graph Models
针对这篇论文中的基于差分隐私的算法进行概括解析:
|输入
输入为结点对格式,用一个整数代表一个结点。
例如下图,假如将A-F表示成1-6,则表示成节点对格式为:
1 2
2 3
3 4
4 5
4 6
|输出
输出和输入的格式相同,结果为经差分隐私处理后的结点对。
|算法解析
- 需求分析:
建立一个系统,通过将原始图G提取成图结构的统计表示,添加受控水平的“噪声”,然后使用结果统计信息生成一个新的图G’。
所以,可分成两部分工作:
- 首先,需要一种方法来准确地捕获一个图的结构作为一组结构统计数据,以及一个生成器将它转换回一个图。
- 其次,我们需要一种方法来确定适当的噪音,以保证一个理想的隐私水平。
- 算法实现:
1.读取图数据
数据结构:
HashMap<Integer,HashSet<Integer>
生成各结点的邻接表。
2.生成dK-2 series
如上图所示,红色数字标识各结点的度(degree),dK-2 series定义为度的不同组合与各组合的出现次数的映射。
例如:<1,2> = 1 (A-B),表示的是degree=1和degree=2的结点相连的边只有AB一条。
考虑合适的数据结构来存储dK-2 series,可采用Hashmap,其中key为其中一个结点的degree(两个结点中较小的degree),value为一个HashSet,为第二个结点的degree和degree组合数的映射。
HashMap<Integer,HashMap<Integer,Integer>>
例如上图所示图结构提取出的dK-2 series数据为:
然后按照顺序放到优先队列中,排序规则是degree对中较大的放后面,例如:
(2,(4,3))< (1,(5,3))<(2,(5,2))
3.添加噪音
所需添加的拉普拉斯噪声量是用户指定的隐私参数epsilon和DK函数的灵敏度S的函数。定义了dK-2 series后,导出它的灵敏度SdK−2。灵敏度被计算为所有G的邻域图中dk-2 series的最大变化数。接着描述了dk扰动算法(dK-PA)在原dK-2 series中的注入噪声,并证明了该算法的有效性,即保证了访问所需的ε-差分隐私。
证明得dK-2灵敏度上限为4·dmax + 1,故代码中添加噪声体现为:
然后对其随机产生的负度数进行统计,归零,然后在正degree部分上减去一些,以保持基本分布不变。
4.分组
作者首先将数据作为整体一起处理,结果显示为若要满足较高的隐私保护要求,最终生成的图与原始的图G差距较大,使得其可用性较低。
于是,改进措施是将排序好的dK-2 series分成一定的tuples,在每个tuples中计算各自的maxdegree,添加噪声,然后再将各个分组合并成整个图。这样就使得大多数元组的maxDegree变小,添加的噪声较小,使得数据更好地保持原样。
LaplaceDistribution(0,(4*maxDegree + 1)/epselon);
5.生成新图并输出
(生成器的具体实现过程没看懂,结果就是根据差分隐私保护后的degree生成了新的图,嗯。)然后把HashMap的键值对输出到自定义的文件中,和输入的图G格式相同。
得到的几组数据:
_____________________________________________________________________
ps: 整个算法的过程大致如上。如有描述不当的地方请指正(#^.^#)