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

为解决大型社交网络隐私保护中的复杂度过高及可用性差的问题,提出一种基于随机投影及差分隐私的社交网络隐私保护算法。利用随机投影对社交网络图的邻接矩阵进行指定投影数量的降维,进一步在降维后的矩阵中加入少量高斯噪声生成待发布矩阵。该算法满足(ε,δ)-差分隐私定义且能保持用户间欧氏距离的可计算性不变。实验和对比分析结果表明,该算法较传统差分隐私能大幅提升数据可用性且计算复杂性较小,适用于大规模社交网络隐私保护。

Differential privacy protection algorithm for large social network

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.