Abstract: The development of various social network applications inspires the emergence of vast amounts of users, which forms a large-scale social graph structure. Amounts of private data are involved in such a graph structure, which should be preserved before being released in order to prevent privacy leakage. And meanwhile, the intricate social relationships between users are not equivalent, and the sensitivity of individual relationships may directly affect the distribution of privacy and the effect of protection. Currently, there are many privacy protection methods for social network graphs without weights, however these methods cannot be directly applied to the scenarios with weighted values (i.e. uneven sensitivity of social relations). To solve this problem, we propose a weighted social network graph perturbation method based on non-interactive differential privacy protection model, named as dp-noisy, which can achieve strong protection of edge weights and graph structure. This method adds disturbance noise based on the single-source shortest path constraint model, classifies the critical edges and non-critical edges according to the weights, and effectively reduces the edge links that need to be disturbed. The experimental results show that in a large-scale dataset (the number of nodes is 30 000), the execution efficiency of the proposed method is improved by 47.3% than that of K-MPNP(K-shortest path privacy), 41.8% than that of LWSPA(protection algorithm based on Laplace noise for weighted social networks) and 52.6% than that of DER(density-based exploration and reconstruction). With similar degree of data privacy protection, the data availability of dp-noisy is 10% higher than that of lp-noisy, superior to that of DER and slightly better than that of LWSPA. The average perturbation quality of dp-noisy is 14% higher than that of lp-noisy, 11.3% higher than that of DER and 27% higher than that of K-MPNP. In the case of the best data availability (ε=10), the average perturbation quality of dp-noisy is 6% higher than that of LWSPA. Compared with the classical methods, our proposal achieves the satisfactory execution efficiency and data availability, which can resist graph structure attack, so it is suitable for large-scale social network applications.

Key words: social network, privacy protection, differential privacy, edge weight, shortest path, linear programming