Asymptotic Distribution in Undirected Finite Weighted Random Graphs with an Increasing Differentially Private Degree Sequence

Abstract

The asymptotic normality of the fixed number of the parameter estimators in undirected weighted networks with an increasing differentially private sequence has been established recently. In this paper, we further derive the central limit theorem for linear combinations of all the parameter estimators with an increasing differentially private sequence for undirected finite weighted network. Simulation studies are provided to illustrate the asymptotic results.

Keywords

Central limit theorem / undirected finite weighted random graphs / differentially private / 62E20 / 62F12

References

[1] Backstrom, L., Dwork, C., Kleinberg, J.: Wherefore art thou r3579x? anonymized social networks, hidden patterns, and structural steganography. Communications of the Acm, 54(12):p.133–141 (2011)

[2] Bickel PJ, Chen A, Levina E, et al.. The method of moments and degree distributions for network models. Ann. Stat., 2011, 39(5): 2280-2301

[3] Billingsley P. Convergence of probability measures, 1968John Wiley & Sons

[4] Blitzstein J, Diaconis P. A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet Mathematics, 2011, 6(4): 489-522

[5] Britton T, Deijfen M, Martin-Löf A. Generating simple random graphs with prescribed degree distribution. J. Stat. Phys., 2006, 124(6): 1377-1397

[6] Campan, A., Truta, T. M.: Data and structural k-anonymity in social networks. Lecture Notes in Computer Science (2008)

[7] Chatterjee, S., Diaconis, P., Sly, A.: Random graphs with a given degree sequence. The Annals of Applied Probability, pages 1400–1435 (2011)

[8] Darmois G. Sur les lois de probabilitéa estimation exhaustive. CR Acad. Sci. Paris, 1935, 260(1265): 85

[9] Dwork, C., M. F. N. K. , Smith, A. .Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds) Theory of Cryptography. TCC 2006. Lecture Notes in Computer Science, vol 3876. Springer, Berlin, Heidelberg. pages 265–284(2006)

[10] Fan Y, Zhang H, Yan T. Asymptotic theory for differentially private generalized beta-models with parameters increasing. Statistics and Its Interface, 2020, 13(3385-398

[11] Fienberg SE. A brief history of statistical models for network analysis and open challenges. J. Comput. Graph. Stat., 2012, 21(4): 825-839

[12] Hay M., Li C., M. G., D., J.: Accurate estimation of the degree distribution of private networks. In Ninth IEEE International Conference on Data Mining, pages 169–178. IEEE (2009)

[13] Hillar, C., Wibisono, A.: Maximum entropy distributions on graphs. arXiv preprint arXiv:1301.3321 (2013)

[14] Holland PW, Leinhardt S. An exponential family of probability distributions for directed graphs. J. Am. Stat. Assoc., 1981, 76(373): 33-50

[15] Karwa V, Slavković A. Inference using noisy degrees: differentially private beta-model and synthetic graphs. Ann. Stat., 2016, 44(1): 87-112

[16] Koopman BO. On distributions admitting a sufficient statistic. Trans. Am. Math. Soc., 1936, 39(3): 399-409

[17] Lu, W. and Miklau, G. Exponential random graph estimation under differential privacy. In proceedings of the 20th ACM SIGKDD international conference on Knowlege discovery and data mining (2014)

[18] Narayanan, A., Shmatikov, V.: De-anonymizing social networks. In In 30th IEEE symposium on Security and Privacy, pages 173–187, New York. IEEE (2009)

[19] Pan, L., Yan, T.: Asymptotics in the beta\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$beta$$\end{document}-model for networks with a differentially private degree sequence. Communications in Statistics - Theory and Methods (2019)

[20] Pitman, E. J. G.: Sufficient statistics and intrinsic accuracy. In Mathematical Proceedings of the cambridge Philosophical society, volume 32, pages 567–579. Cambridge Univ Press (1936)

[21] Rinaldo A, Petrović S, Fienberg SE. Maximum lilkelihood estimation in the beta\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$ beta $$\end{document}-model. Ann. Stat., 2013, 41(3): 1085-1110

[22] Romney AK, Weller SC. Predicting informant accuracy from patterns of recall among individuals. Social Networks, 1984, 6(1): 59-77

[23] Wondracek, G., Holz, T., Kirda, E., Kruegel, C. . A practical attack to de-anonymize social network users. In 2010 IEEE Symposium on Security and Privacy, pages 1–15, Oakland. IEEE (2010)

[24] Yan T. A note on asymptotic distributions in maximum entropy models for networks. Statistics & Probability Letters, 2015, 98: 1-5

[25] Yan T, Qin H, Wang H. Asymptotics in undirected random graph models parameterized by the strengths of vertices. Stat. Sin., 2016, 26(1): 273-293

[26] Yan T, Xu J. A central limit theorem in the β\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\beta $$\end{document}-model for undirected random graphs with a diverging number of vertices. Biometrika, 2013, 100(2): 519-524

[27] Yan T, Zhao Y, Qin H. Asymptotic normality in the maximum entropy models on graphs with an increasing number of parameters. J. Multivar. Anal., 2015, 133: 61-76

[28] Yuan M, Lei C, Yu PS. Personalized privacy protection in social networks. Proceedings of the Vldb Endowment, 2011, 4(2): 141-150

[29] Zhang H, Liu Y, Li B. Notes on discrete compound poisson model with applications to risk theory. Insurance Math. Econom., 2014, 59: 325-336

[30] Zhao Y, Levina E, Zhu J. Consistency of community detection in networks under degree-corrected stochastic block models. Ann. Stat., 2012, 40(4): 2266-2292

[31] Zhou B, Pei J, Luk WS. A brief survey on anonymization techniques for privacy preserving publishing of social network data. ACM SIGKDD Explorations Newsl, 2008, 10(2): 12-22

RIGHTS & PERMISSIONS

School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature