Abstract

As network becomes increasingly prevalent, significant attention has

been devoted to addressing privacy issues in publishing network data. One of

the critical challenges for data publishers is to preserve the topological structures

of the original network while protecting sensitive information. In this paper, we

investigate the utility of community detection in multi-layer networks under a

personalized edge-flipping mechanism. This mechanism enables data publishers

to protect edge information based on each node’s privacy preferences. Within

this framework, the community structure under the multi-layer degree-corrected

stochastic block model remains invariant after appropriate debiasing, making

consistent community detection in privatized multi-layer networks achievable.

Theoretically, we establish the consistency of community detection in the privatized multi-layer network, demonstrating the fundamental privacy-utility tradeoff

in differentially private community detection in multi-layer networks under the

proposed mechanism. Moreover, the proposed method is further supported by

extensive numerical experience on synthetic and real-life multi-layer networks.

Information

Preprint No.SS-2023-0287
Manuscript IDSS-2023-0287
Complete AuthorsYaoming Zhen, Shirong Xu, Junhui Wang
Corresponding AuthorsYaoming Zhen
Emailsyzhen8-c@my.cityu.edu.hk

References

  1. Abawajy, J. H., M. I. H. Ninggal, and T. Herawan (2016). Privacy preserving social network data publication. IEEE Communications Surveys & Tutorials 18(3), 1974–1997.
  2. Alaggan, M., S. Gambs, and A.-M. Kermarrec (2015). Heterogeneous differential privacy. arXiv preprint arXiv:1504.06998.
  3. Carrington, P. J. (2014). Crime and social network analysis. In The SAGE Handbook of Social Network Analysis, pp. 236–255. SAGE Publications Ltd.
  4. Chen, R., B. C. Fung, P. S. Yu, and B. C. Desai (2014). Correlated network data publication via differential privacy. The VLDB Journal 23, 653–676.
  5. Chen, S., S. Liu, and Z. Ma (2022). Global and individualized community detection in inhomogeneous multilayer networks. The Annals of Statistics 50(5), 2664–2693.
  6. Day, W.-Y., N. Li, and M. Lyu (2016). Publishing graph degree distribution with node differential privacy. In Proceedings of the 2016 International Conference on Management of Data, pp. 123–138.
  7. Du, N., B. Wu, X. Pei, B. Wang, and L. Xu (2007). Community detection in large-scale social networks. In Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 Workshop on Web Y. ZHEN, S. XU, AND J. WANG Mining and Social Network Analysis, pp. 16–25.
  8. Dwork, C., F. McSherry, K. Nissim, and A. Smith (2006). Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265–284. Springer.
  9. Epasto, A., V. Mirrokni, B. Perozzi, A. Tsitsulin, and P. Zhong (2022). Differentially private graph learning via sensitivity-bounded personalized pagerank. Advances in Neural Information Processing Systems 35, 22617–22627.
  10. Fan, Y., H. Zhang, and T. Yan (2020). Asymptotic theory for differentially private generalized β-models with parameters increasing. arXiv preprint arXiv:2002.12733.
  11. Ghoshdastidar, D. and A. Dukkipati (2017). Uniform hypergraph partitioning: Provable tensor methods and sampling techniques. The Journal of Machine Learning Research 18(1), 1638–1678.
  12. Granovetter, M. (2005). The impact of social structure on economic outcomes. Journal of Economic Perspectives 19(1), 33–50.
  13. Gregurec, I., T. Vraneˇsevi´c, and D. Dobrini´c (2011). The importance of database marketing in social network advertising. International Journal of Management Cases 13(4), 165–172.
  14. Guo, X., Y. Qiu, H. Zhang, and X. Chang (2023). Randomized spectral co-clustering for largescale directed networks. Journal of Machine Learning Research 24(380), 1–68.
  15. Hay, M., C. Li, G. Miklau, and D. Jensen (2009). Accurate estimation of the degree distribution of private networks. In 2009 Ninth IEEE International Conference on Data Mining, pp. MULTI-LAYER NETWORKS WITH DIFFERENTIAL PRIVACY 169–178. IEEE.
  16. Hehir, J., A. Slavkovi´c, and X. Niu (2022). Consistent spectral clustering of network block models under local differential privacy. The Journal of privacy and confidentiality 12(2), 10.29012/jpc.811.
  17. Ji, S., W. Li, M. Srivatsa, J. S. He, and R. Beyah (2014). Structure based data de-anonymization of social networks and mobility traces. In International Conference on Information Security, pp. 237–254. Springer.
  18. Jin, J. (2015). Fast community detection by score. The Annals of Statistics 43(1), 57–89.
  19. Jing, B.-Y., T. Li, Z. Lyu, and D. Xia (2021). Community detection on mixture multilayer networks via regularized tensor decomposition. The Annals of Statistics 49(6), 3181–3205.
  20. Karwa, V. and A. Slavkovi´c (2016). Inference using noisy degrees: Differentially private β-model and synthetic graphs. The Annals of Statistics 44(1), 87–112.
  21. Kasiviswanathan, S. P., K. Nissim, S. Raskhodnikova, and A. Smith (2013). Analyzing graphs with node differential privacy. In Theory of Cryptography Conference, pp. 457–476. Springer.
  22. Ke, Z. T., F. Shi, and D. Xia (2019). Community detection for hypergraph networks via regularized tensor power iteration. arXiv preprint arXiv:1909.06503.
  23. Klerks, N. P. (2004). The network paradigm applied to criminal organisations: theoretical nitpicking or a relevant doctrine for investigators? recent developments in the: Theoretical Y. ZHEN, S. XU, AND J. WANG nitpicking or a relevant doctrine for investigators? recent. In Transnational Organised Crime, pp. 111–127. Routledge.
  24. Kolda, T. G. and B. W. Bader (2009). Tensor decompositions and applications. SIAM review 51(3), 455–500.
  25. Lei, J., K. Chen, and B. Lynch (2020). Consistent community detection in multi-layer network data. Biometrika 107(1), 61–73.
  26. Lei, J. and A. Rinaldo (2015). Consistency of spectral clustering in stochastic block models. The Annals of Statistics 43(1), 215–237.
  27. Leskovec, J., K. J. Lang, and M. Mahoney (2010). Empirical comparison of algorithms for network community detection. In Proceedings of the 19th International Conference on World Wide Web, pp. 631–640.
  28. Li, N. and S. K. Das (2013). Applications of k-anonymity and l-diversity in publishing online social networks. In Security and Privacy in Social Networks, pp. 153–179. Springer.
  29. Ma, Z. and S. Nandy (2023). Community detection with contextual multilayer networks. IEEE Transactions on Information Theory 69(5), 3203–3239.
  30. Mohamed, M. S., D. Nguyen, A. Vullikanti, and R. Tandon (2022). Differentially private community detection for stochastic block models. In International Conference on Machine Learning, pp. 15858–15894. PMLR.
  31. Nayak, T. K. and S. A. Adeshiyan (2009). A unified framework for analysis and comparison of MULTI-LAYER NETWORKS WITH DIFFERENTIAL PRIVACY randomized response surveys of binary characteristics. Journal of Statistical Planning and Inference 139(8), 2757–2766.
  32. Paul, S. and Y. Chen (2022). Null models and community detection in multi-layer networks. Sankhya A 84(1), 163–217.
  33. Rudelson, M. and R. Vershynin (2009). Smallest singular value of a random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 62(12), 1707–1739.
  34. Thomas, K. and D. M. Nicol (2010). The koobface botnet and the rise of social malware. In 2010 5th International Conference on Malicious and Unwanted Software, pp. 63–70. IEEE.
  35. Ullman, J. and A. Sealfon (2019). Efficiently estimating erdos-renyi graphs with node differential privacy. Advances in Neural Information Processing Systems 32, 3770–3780.
  36. Wang, Q., T. Yan, B. Jiang, and C. Leng (2022). Two-mode networks: inference with as many parameters as actors and differential privacy. Journal of Machine Learning Research 23(292), 1–38.
  37. Wang, Y., X. Wu, and D. Hu (2016). Using randomized response for differential privacy preserving data collection. In EDBT/ICDT Workshops 1558(2), paper35.
  38. Xu, D., S. Yuan, X. Wu, and H. Phan (2018). Dpne: Differentially private network embedding. In Advances in Knowledge Discovery and Data Mining: 22nd Pacific-Asia Conference, PAKDD 2018, Melbourne, VIC, Australia, June 3-6, 2018, Proceedings, Part II 22, pp. 235–246. Springer. Y. ZHEN, S. XU, AND J. WANG
  39. Xu, S., Y. Zhen, and J. Wang (2023). Covariate-assisted community detection in multi-layer networks. Journal of Business & Economic Statistics 41(3), 915–926.
  40. Yan, T. (2021). Directed networks with a differentially private bi-degree sequence. Statistica Sinica 31(4), 2031–2050.
  41. Yan, T. (2025). Differentially private analysis of networks with covariates via a generalized β-model. Science China Mathematics 68, 2469–2500.
  42. Zhen, Y. and J. Wang (2023). Community detection in general hypergraph via graph embedding. Journal of the American Statistical Association 118(543), 1620–1629.

Acknowledgments

We thank the Associate Editor and two anonymous referees, whose constructive comments have lead to significant improvement of the paper.

This work is supported in part by HK RGC Grants GRF-11301521, GRF-

11311022, GRF-14306523, CUHK Startup Grant 4937091, and CUHK Direct Grant 4053588.

Supplementary Materials

The online Supplementary Material contains all necessary lemmas and technical proofs of the paper.

Supplementary materials are available for download.