Abstract
Social graph, as a representation of the network topology, contains users’ social relationship. In order to obtain a social graph, a server requires users to submit their relationships. As we know, using or publishing social graph will cause privacy leakage to users. For this sake, it is necessary to generate synthetic social graph for various usages. In this paper, we propose \(\mathbb {PSG}\), a local Privacy Preserving Synthetic Social Graph Generation method. In order to protect users’ privacy, we utilize the local differential privacy model and a truncated Laplace mechanism to allow users to perturb their own data before submission. We then model the graph generation as a combinatorial optimization problem and design a greedy algorithm to maximize the utility of the generated graph. Through theoretical analysis and extensive experiments, we show that our method satisfies local differential privacy as well as maintains attributes of the original social graph.
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
Seshadhri, C., Kolda, T.G., Pinar, A.: Community structure and scale-free collections of erdős-rényi graphs. Phys. Rev. E 85(5), 056109 (2012)
Chen, L., et al.: A privacy settings prediction model for textual posts on social networks. In: Romdhani, I., Shu, L., Takahiro, H., Zhou, Z., Gordon, T., Zeng, D. (eds.) CollaborateCom 2017. LNICST, vol. 252, pp. 578–588. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00916-8_53
Sweeney, L.: k-anonymity: a model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl. Based Syst. 10(05), 557–570 (2002)
Machanavajjhala, A., Kifer, D., Gehrke, J., Venkitasubramaniam, M.: l-diversity: privacy beyond k-anonymity. ACM Trans. Knowl. Discov. Data (TKDD) 1(1), 3-es (2007)
Zhang, X., Chen, R., Xu, J., Meng, X., Xie, Y.: Towards accurate histogram publication under differential privacy. In: Proceedings of the 2014 SIAM International Conference on Data Mining, pp. 587–595. SIAM (2014)
Ding, X., Zhang, X., Bao, Z., Jin, H.: Privacy-preserving triangle counting in large graphs. In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 1283–1292 (2018)
Sun, H., et al.: Analyzing subgraph statistics from extended local views with decentralized differential privacy. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 703–717 (2019)
Erdös, P., Rényi, A.: On the evolution of random graphs. In: The Structure and Dynamics of Networks, pp. 38–82. Princeton University Press (2011)
Aiello, W., Chung, F., Lu, L.: A random graph model for massive graphs. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 171–180 (2000)
Qin, Z., Yu, T., Yang, Y., Khalil, I., Xiao, X., Ren, K.: Generating synthetic decentralized social graphs with local differential privacy. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 425–438 (2017)
Zhu, H., Zuo, X., Xie, M.: DP-FT: a differential privacy graph generation with field theory for social network data release. IEEE Access 7, 164304–164319 (2019)
Zhu, T., Li, G., Zhou, W., Yu, P.S.: Preliminary of differential privacy. In: Differential Privacy and Applications. Advances in Information Security, vol. 69, pp. 7–16. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62004-6
Day, W.Y., Li, N., Lyu, M.: Publishing graph degree distribution with node differential privacy. In: Proceedings of the 2016 International Conference on Management of Data, pp. 123–138 (2016)
Karwa, V., Slavković, A.B.: Differentially private graphical degree sequences and synthetic graphs. In: Domingo-Ferrer, J., Tinnirello, I. (eds.) PSD 2012. LNCS, vol. 7556, pp. 273–285. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33627-0_21
Wang, T., Blocki, J., Li, N., Jha, S.: Locally differentially private protocols for frequency estimation. In: 26th USENIX Security Symposium (USENIX Security 2017), pp. 729–745 (2017)
Leskovec, J., Krevl, A.: Snap datasets: Stanford large network dataset collection (2014)
Luce, R.D., Perry, A.D.: A method of matrix analysis of group structure. Psychometrika 14(2), 95–116 (1949). https://doi.org/10.1007/BF02289146
Rousseau, R., Egghe, L., Guns, R.: Becoming Metric-Wise. A Bibliometric Guide for Researchers. Chandos-Elsevier, Kidlington (2018)
Rand, W.M.: Objective criteria for the evaluation of clustering methods. J. Am. Stat. Assoc. 66(336), 846–850 (1971)
Pinar, A., Seshadhri, C., Kolda, T.G.: The similarity between stochastic Kronecker and Chung-Lu graph models. In: Proceedings of the 2012 SIAM International Conference on Data Mining, pp. 1071–1082. SIAM (2012)
Acknowledgements
This work was partially supported by the National Natural Science Foundation of China under Grants 62072061 and U20A20176, and by the Fundamental Research Funds for the Central Universities under Grant 2021CDJQY-026.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Huang, H., Yang, Y., Li, Y. (2021). \(\mathbb {PSG}\): Local Privacy Preserving Synthetic Social Graph Generation. In: Gao, H., Wang, X. (eds) Collaborative Computing: Networking, Applications and Worksharing. CollaborateCom 2021. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 406. Springer, Cham. https://doi.org/10.1007/978-3-030-92635-9_23
Download citation
DOI: https://doi.org/10.1007/978-3-030-92635-9_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92634-2
Online ISBN: 978-3-030-92635-9
eBook Packages: Computer ScienceComputer Science (R0)