殷轶平，徐睿峰

(1.哈尔滨工业大学深圳研究生院 计算机科学与技术学院，广东 深圳 518055；2.哈尔滨工程大学 国家保密学院，黑龙江 哈尔滨 150001)

0 引言

近年来，以Twitter、Facebook、微博为代表的在线社交网络得到飞速发展。由于可以实时获取海量真实用户的用户属性、个人表达、交互关系等内容，社交网络被广泛用于用户建模、社区发现、信息推荐等应用和研究。例如Facebook作为全球最受欢迎的在线社交网络之一，拥有大量的好友关系信息，可以被用来分析社群关系，挖掘社会观点。然而，一些存在的关系可能被用户视为敏感信息，直接发布会导致个人信息的严重泄露。2018年3月16日，美国纽约时报曝光Facebook超过5000万用户的个人信息数据被泄露并被用于选举干预等非法行为。这一事件突显出社交媒体数据的滥用可能带来的严重后果，为数据持有者敲响了警钟。因此，在发布社交媒体数据之前，必须对其进行处理，使数据在具有隐私保证的基础上支持相关的研究工作。

因此，考虑到社交网络数据的紧密关联性，本文研究将注意力放在添加尽可能少的噪声来实现图数据的差分隐私保护。为此，本文提出了一种非交互式的严格差分隐私方法，称为DP2Gsister(Two- phase Differential Privacy for Gsister)。这一方法的主要思想是分两个阶段实现差分隐私以形成与原图结构信息相似且具有隐私保证的发布图Gsister。第一阶段引入层次随机图模型重构图结构特征，用满足ε1-差分隐私的MCMC在原图上采集样本Tsample；第二阶段计算Tsample的连接概率，对其添加隐私预算为ε2的拉普拉斯噪声以生成概率噪声序列{Pn}；……