基于层次随机图的社会网络差分隐私数据发布  

Differentially private network data publishing via hierarchical random graph

作　　者：张伟[1] 仓基云 王旭然[1] 陈云芳[1] 

机构地区：[1]南京邮电大学计算机学院,江苏南京210023

出　　处：《南京邮电大学学报（自然科学版）》2016年第3期23-32,共10页Journal of Nanjing University of Posts and Telecommunications：Natural Science Edition

基　　金：国家自然科学基金(61272422)资助项目

摘　　要：在线社会网络已经成为社会学和信息科学的数据宝库,但是直接分析社会网络数据会造成敏感信息泄漏,对用户隐私构成威胁。传统的基于数据匿名化技术的隐私保护技术面对不断提高的背景攻击显得无能为力。对此,差分隐私作为一种可以严格定义的可量化技术被引入到社会网络的隐私保护中。文中提出一种基于层次随机图(Hierarchical Random Graph)的满足ε-差分隐私的社会网络图发布算法DP-HRGP(Differential Privacy-Hierarchical Random Graph Publishing)。该算法的噪声增加机制分为两个阶段:首先通过指数机制计算HRG结构树的得分,并利用马尔科夫蒙特卡洛(Markov Chain Monte Carlo)方法进行采样得到HRG结构树候选集合,然后通过拉普拉斯机制对稳态采样集合中的HRG的内部节点进行加噪,将加噪后的HRG转化为下三角矩阵,并求出所有稳态采样HRG的下三角均值矩阵,最后,根据均值矩阵内元素值即层次随机图的内部节点的连接概率值生成净化后的社会网络发布图。实验证明了DP-HRGP算法在满足ε-差分隐私的同时具有较好的数据可用性。Online Social Network has become a rich source of insights in social and information sciences.However, the direct analysis of the data will result in the leakage of sensitive information, it is a threat to personal privacy. Since facing the rising of background attack traditional privacy protection technologies based on data anonymization techniques seem powerless, differential privacy as a rigorously definable quantifiable technique is introduced. This paper presents a new algorithm with s-differential privacy for releasing the social network graph based on the hierarchical random graph, differential privacy-hierarchi- cal random graph publishing （DP-HRGP）. In DP-HRGP the noise adding mechanism is divided into two stages：1 ） the score of HRG structure tree is calculated by the exponential mechanism, and the Chain Monte Carlo Markov method is used to obtain the candidate set of the HRGs. 2） the noise is added to the internal nodes of each HRG in the stationary distribution sample set through the Laplace mechanism, and then each HRG is converted into a lower triangular matrix and the mean matrix of all the HRGs is compu- ted. Finally, according to the value of the mean matrix, the purify version of social network graph is released. The experimental results show that DP-HRGP preserves good utility as well as it satisfies the ε- differential privacy theoretically.

关 键 词：社会网络 差分隐私 层次随机图 数据发布 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术] TP393[自动化与计算机技术—计算机科学与技术]