基于差分隐私保护的社交网络发布图生成模型

Differential Privacy Protection Based Generation Model of Social Network Publication Graph

摘要:

社交网络在帮助人们建立社会性网络应用服务的同时，收集了大量的用户资料和敏感数据，通过分析这些数据可能泄露潜在的隐私信息.目前差分隐私保护模型对隐私泄露风险给出了严谨、定量化的表示和证明，极大地保证了数据的可用性.设计了一个满足差分隐私保护的社交网络发布图生成模型，首先通过图模型表示社交网络结构，并将原图按照节点特征分类为多个子图；然后利用四叉树方法对子图的密集区域进行划分，在树的叶子节点添加满足差分隐私保护的噪声；通过子图重构的方式，生成待发布图.最后，利用度分布、最短路径、聚类系数等统计分析方法，实验验证了该模型的可行性和有用性.

Abstract:

When Social Network helps people build various social networking applications, a large number of user information and sensitive data will be collected in the mean time, and through the analysis of these data, some potential privacy information may be disclosed. At present, differential privacy protection model provides a rigorous and quantitative representation of the risk of privacy disclosure, which greatly guarantees the availability of data. In this paper, a generation model of social network publication graph is designed to meet the differential privacy protection. First the social network structure is represented as a graph model, and the original graph is classified into multiple subgraphs according to the characteristics of nodes. Then intensive regional of every subgraph is divided with a Quadtree method, noises of differential privacy protection are added into leaf nodes of the trees, and publication graph is generated by the way of subgraph reconstruction,. Finally, the feasibility and usefulness of the model is verified by the statistical analysis, such as the degree distribution, the shortest path and the clustering coefficient.