Abstract
The characteristics of social networks has always been a hot topic of scientific research. In order to protect the privacy of users, the owner of the private data need to provide privacy protection when providing inquiries or publishing data. Local differential privacy (LDP) is difficult to construct a highly available social networks graph due to its independent perturbation process. Centralized differential privacy usually adds excessive noise due to the structural characteristics of social networks graphs. Higher security usually results in lower availability. Simply implementing any differential privacy mechanism will cause a large amount of data to be disturbed by noise. On the other hand, some spectral based privacy protection methods provide accurate spectrum, however ignore the disclosure of privacy data in spectrum query. Therefore, we propose a spectrum query algorithm based on personalized differential privacy. The algorithm effectively improves data availability by taking advantage of different privacy preferences of users in the social network and the characteristics of the spectrum. To verify the availability of these methods, experimental tests have been carried out in both model networks and actual networks, which shows that the algorithm improves the availability of data when it has the same security.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cormode, G., Srivastava, D., Yu, T., Zhang, Q.: Anonymizing bipartite graph data using safe groupings. In: Proceedings of the VLDB Endowment, vol. 1, pp. 833–844 (2008)
Li, N., Li, T., Venkata, S.: t-closeness: privacy beyond k-anonymity and l-diversity. In: IEEE 23rd International Conference on Data Engineering, April, pp. 106–115 (2007)
Dwork, C., Kobliner, Y.: Preserving privacy when statistically analyzing a large database. U.S. Patent Application 11/038,446, (2006).
Shen, E., Yu, T.: Mining frequent graph patterns with differential privacy. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM (2013)
Wang, Q.: Real-time and spatio-temporal crowd-sourced social network data publishing with differential privacy. IEEE Trans. Dependable Secure Comput. 15(4), 591–606 (2016)
Baden, R.: Persona: an online social network with user-defined privacy. In: ACM SIGCOMM Computer Communication Review, vol. 39 (2009)
Ebadi, H., Sands, D., Schneider, G.: Differential privacy: now it’s getting personal. ACM Sigplan Notices 50, 69–81 (2015)
Jorgensen, Z., Yu, T., Cormode, G.: Conservative or liberal? Personalized differential privacy. In: 2015 IEEE 31St International Conference on Data Engineering (2015).
Zhang, S., Kang, H., Yan, H.: Privacy preserving for social network relational data based on Skyline computing. J. Comput. Appl. 39, 1394-1399 (2019)
Chamikara, M.A.P., Bertók, P., Liu, D.: An efficient and scalable privacy preserving algorithm for big data and data streams. Comput. Secur. 87, 101570 (2019)
Cui, L., Qu, Y., Yu, S., Gao, L.: A Trust-grained personalized privacy-preserving scheme for big social data. In: 2018 IEEE International Conference on Communications (ICC). 20–24 May, pp. 1938–1883 (2018)
Van Dam, E.R., Haemers, W.H.: Which graphs are determined by their spectrum. Linear Algebra Appl. 373, 241–272 (2003)
Xu, S., Zhang, J., Han, D.: Singular value decomposition-based data distortion strategy for privacy protection. Knowl. Inf. Syst. 10, 383–397 (2006)
Wu, L., Ying, X., Wu, X.: Reconstruction from randomized graph via low rank approximation. In: Proceedings of the 2010 SIAM International Conference on Data Mining, Society for Industrial and Applied Mathematics, pp. 60–71 (2010)
Liu, D., Wang, H., Van Mieghem, P.: Spectral perturbation and reconstructability of complex networks. Phys. Rev. E 81, 016101 (2010)
Yong, Z., Lingjie, Z., Zhongyuan, J.: Security analysis of weighted network anonymity based on singular value decomposition. J. Commun. 39, 23 (2018)
Wang, Y., Wu, X., Wu, L.: Differential privacy preserving spectral graph analysis. In: Pei, J., Tseng, V.S., Cao, L., Motoda, H., Xu, G. (eds.) PAKDD 2013. LNCS (LNAI), vol. 7819, pp. 329–340. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37456-2_28
Dwork, C., Roth, A.: The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. 9, 211–407 (2014)
Li, C., Hay, M., Miklau, G., Wang, Y.: A data-and workload-aware algorithm for range queries under differential privacy. PVLDB 7(5) (2014)
Shekhar S., Xiong H., Zhou X.: Root-Mean-Square Error. Encyclopedia of GIS. Springer, Cham (2017).https://doi.org/10.1007/978-3-319-17885-1_101137
Stanford network dataset collection. https://snap.stanford.edu/dat
Acknowledgements
We would like to thank the anonymous reviewers for their insightful comments. This work was sponsored by the National Natural Science Foundation of China (No. 61941105).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Liu, Y., Zeng, Y., Liu, Z., Ma, J. (2021). Spectrum Privacy Preserving for Social Networks: A Personalized Differential Privacy Approach. In: Wu, Y., Yung, M. (eds) Information Security and Cryptology. Inscrypt 2020. Lecture Notes in Computer Science(), vol 12612. Springer, Cham. https://doi.org/10.1007/978-3-030-71852-7_18
Download citation
DOI: https://doi.org/10.1007/978-3-030-71852-7_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-71851-0
Online ISBN: 978-3-030-71852-7
eBook Packages: Computer ScienceComputer Science (R0)