Abstract
We propose a novel mechanism to release an accurate and differentially private estimate of the link set of social networks. Differential privacy is one of the most common notations to quantify the privacy level of information publication. Several methods have been proposed to publish edge set information, among which one of the notable mechanisms is based on stratified sampling. While it is very scalable, social network information can be significantly altered by this technique. In fact, when we use mechanism based on stratified sampling, a totally random network may get published even when the input network is sparse. We aim to overcome this drawback in our work. We provide an efficient two-stage mechanism to control the edge set size and quality independently. To confirm the practical utility of our proposal, we apply it to the maximum matching problem when the edge information is spread between two different bipartite networks. We validate through experiments that the error induced by our framework is at least 20 times smaller than that of the original stratified sampling based mechanism when privacy level is 5. In addition, the computation time of our framework is 3 times shorter than the original method.
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
Narayanan, A., Shmatikov, V.: Robust de-anonymization of large sparse datasets. In: SP. IEEE 2008, 111–125 (2008)
Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 265–284. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_14
Roohi, L., Rubinstein, B.I., Teague, V.: Differentially-private two-party egocentric betweenness centrality. INFOCOM IEEE 2019, 2233–2241 (2019)
“Crime network dataset - KONECT,” April 2017. http://konect.uni-koblenz.de/networks/moreno_crime
Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: a recursive model for graph mining. SDM SIAM 2004, 442–446 (2004)
Ullman, J., Sealfon, A.: Efficiently estimating erdos-renyi graphs with node differential privacy. In: Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8–14 December 2019, Vancouver, BC, Canada, 2019, pp. 3765–3775 (2019)
Day, W.-Y., Li, N., Lyu, M.: Publishing graph degree distribution with node differential privacy. ICDM 2016, 123–138 (2016)
Kasiviswanathan, S.P., Nissim, K., Raskhodnikova, S., Smith, A.: Analyzing graphs with node differential privacy. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 457–476. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_26
Hay, M., Li, C., Miklau, G., Jensen, D.D.: Accurate estimation of the degree distribution of private networks. In: The Ninth IEEE International Conference on Data Mining, Miami, Florida, USA 6–9(2009), pp. 169–178 (2009)
Kenthapadi, K., Korolova, A., Mironov, I., Mishra, N.: Privacy via the Johnson-Lindenstrauss transform, arXiv preprint arXiv:1204.2606 (2012)
Ahmed, F., Liu, A.X., Jin, R.: Publishing social network graph eigen-spectrum with privacy guarantees. In: IEEE Transactions on Network Science and Engineering, pp. 1–14 (2019)
Mir, D.J., Wright, R.N.: A differentially private estimator for the stochastic kronecker graph model. EDBT/ICDT Workshops 2012, 167–176 (2012)
Li, D., Zhang, W., Chen, Y.: Differentially private network data release via stochastic kronecker graph. In: Cellary, W., Mokbel, M.F., Wang, J., Wang, H., Zhou, R., Zhang, Y. (eds.) WISE 2016. LNCS, vol. 10042, pp. 290–297. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48743-4_23
Paul, A., Suppakitpaisarn, V., Bafna, M., Rangan, C.P.: Improving accuracy of differentially private kronecker social networks via graph clustering. In: ISNCC 2020, 2020 (accepted)
Hsu, J., Huang, Z., Roth, A., Roughgarden, T., Wu, Z.S.: Private matchings and allocations. SIAM J. Comput. 45(6), 1953–1984 (2016)
Varma, N., Yoshida, Y.: Average sensitivity of graph algorithms, arXiv preprint arXiv:1904.03248 (2019)
Huang, Z., Zhu, X.: Scalable and jointly differentially private packing. In: 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9–12, 2019, Patras, Greece, ser. LIPIcs, 2019, pp. 73:1–73:12 (2019)
McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: FOCS 2007. IEEE 94–103 (2007)
Cochran, W.G.: Sampling techniques. Wiley (2007)
Kleinberg, J., Tardos, E.: Algorithm design. Pearson Education (2006)
Durstenfeld, R.: Algorithm 235: random permutation. Commun. ACM 7(7), 420 (1964)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Adhikari, M.B., Suppakitpaisarn, V., Paul, A., Rangan, C.P. (2020). Two-Stage Framework for Accurate and Differentially Private Network Information Publication. In: Chellappan, S., Choo, KK.R., Phan, N. (eds) Computational Data and Social Networks. CSoNet 2020. Lecture Notes in Computer Science(), vol 12575. Springer, Cham. https://doi.org/10.1007/978-3-030-66046-8_22
Download citation
DOI: https://doi.org/10.1007/978-3-030-66046-8_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-66045-1
Online ISBN: 978-3-030-66046-8
eBook Packages: Computer ScienceComputer Science (R0)