大型社交网络的差分隐私保护算法  

Differential privacy protection algorithm for large social network

作　　者：王婷婷[1] 龙士工[1,2] 丁红发[3] WANG Ting-ting;LONG Shi-gong;DING Hong-fa(College of Computer Science and Technology,Guizhou University,Guiyang 550025,China;State Key Laboratory of Public Big Data,Guizhou University,Guiyang 550025,China;College of Information,Guizhou University of Finance and Economics,Guiyang 550025,China)

机构地区：[1]贵州大学计算机科学与技术学院,贵州贵阳550025 [2]贵州大学公共大数据国家重点实验室,贵州贵阳550025 [3]贵州财经大学信息学院,贵州贵阳550025

出　　处：《计算机工程与设计》2020年第6期1568-1574,共7页Computer Engineering and Design

基　　金：贵州省科技计划基金项目(黔科合重大专项字[2018]3001、黔科合支撑[2019]2004、黔科合支撑[2018]2162、黔科合基础[2019]1049);贵州财经大学科研基金项目(2017XJC01)。

摘　　要：为解决大型社交网络隐私保护中的复杂度过高及可用性差的问题,提出一种基于随机投影及差分隐私的社交网络隐私保护算法。利用随机投影对社交网络图的邻接矩阵进行指定投影数量的降维,进一步在降维后的矩阵中加入少量高斯噪声生成待发布矩阵。该算法满足(ε,δ)-差分隐私定义且能保持用户间欧氏距离的可计算性不变。实验和对比分析结果表明,该算法较传统差分隐私能大幅提升数据可用性且计算复杂性较小,适用于大规模社交网络隐私保护。To address the issue of high complexity and poor utility of privacy protection in large social networks,a privacy protection algorithm based on random projection and differential privacy was proposed.Random projection was used to reduce the dimension of social network’s adjacency matrix,and the projected matrix with small amount of Gaussian noise was perturbed to generate the matrix to be released.The proposed algorithm satisfied differential privacy and preserves the utility of Euclidean distance.Results of experiments and analysis show that the proposed algorithm improves the data availability and reduces the computational complexity significantly compared with traditional differential privacy,and it is suitable for privacy protection of large-scale social networks.

关 键 词：社交网络 隐私保护 数据发布 随机投影 差分隐私 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]