LI Xiaoye, YANG Jing, SUN Zhenlong, ZHANG Jianpei. Publishing Social Graphs with Differential Privacy Guarantees Based on wPINQ[J]. Chinese Journal of Electronics, 2019, 28(2): 273-279. doi: 10.1049/cje.2018.12.003
Citation: LI Xiaoye, YANG Jing, SUN Zhenlong, ZHANG Jianpei. Publishing Social Graphs with Differential Privacy Guarantees Based on wPINQ[J]. Chinese Journal of Electronics, 2019, 28(2): 273-279. doi: 10.1049/cje.2018.12.003

Publishing Social Graphs with Differential Privacy Guarantees Based on wPINQ

doi: 10.1049/cje.2018.12.003
Funds:  This work is supported by the National Natural Science Foundation of China (No.61672179, No.61370083, No.61402126), the Natural Science Foundation of Heilongjiang Province (No.F2015030), the Youth Science Fund of Heilongjiang Province (No.QC2016083, No.QC2017079), the Postdoctoral Fellowship of Heilongjiang Province (No.LBHZ14071), and the Fundamental Research Funds in Heilongjiang Provincial Universities (No.135109245, No.135109314).
More Information
  • Corresponding author: YANG Jing (corresponding author) was born in 1962. She is a professor at the College of Computer Science and Technology, Harbin Engineering University. Her research interests cover enterprise intelligence computing, database theory, knowledge engineering, and privacy protection.(
  • Received Date: 2017-07-05
  • Rev Recd Date: 2018-05-10
  • Publish Date: 2019-03-10
  • To publish social graphs with differential privacy guarantees for reproducing valuable results of scientific researches, we study a workflow for graph synthesis and propose an improved approach based on weighted Privacy integrated query (wPINQ). The workflow starts with a seed graph to fit the noisy degree sequence, which essentially is the 1K-graph. In view of the inaccurate assortativity coefficient, we truncate the workflow to replace the seed graph with an optimal one by doing target 1K-rewiring while preserving the 1K-distribution. Subsequently, Markov chain Monte Carlo employs the new seed graph as the initial state, and proceeds step by step guided by the information of Triangles by intersect to increase the number of triangles in the synthetic graphs. The experimental results show that the proposed algorithm achieves better performance for the published social graphs.
  • loading
  • A. Bekiari and S. Spyropoulou, “Exploration of verbal aggressiveness and interpersonal attraction through social network analysis: Using university physical education class as an illustration”, Open Journal of Social Sciences, Vol.4, No.6, pp.145-155, 2016.
    W. Tawileh, “Evaluating virtual collaborative learning platforms using social network analysis”, International Conference on Digital Information Processing & Communications, pp.80-86, 2016.
    S. Chakraborty and B. K. Tripathy, “Alpha- anonymization techniques for privacy preservation in social networks”, Social Network Analysis & Mining, Vol. 6, No.1, pp.1-11, 2016.
    B. K. Tripathy and S. Chakraborty, “Privacy preserving anonymization of social networks using eigen vector centrality approach”, Intelligent Data Analysis, Vol.20, No.3, pp.543-560, 2016.
    P. Liu, Y. Bai, L. Wang, et al., “Partial k-anonymity for privacy-preserving social network data publishing”, International Journal of Software Engineering & Knowledge Engineering, Vol.27, No.1, pp.71-90, 2016.
    C. Dwork, “Differential privacy”, International Colloquium on Automata, Languages, and Programming, pp.1-12, 2006.
    M. Hay, C. Li, G. Miklau, et al., “Accurate estimation of the degree distribution of private networks”, Ninth IEEE International Conference on Data Mining, pp.169-178, 2009.
    D. J. Mir and R. N. Wright, “A differentially private graph estimator”, IEEE International Conference on Data Mining Workshops, pp.122-129, 2009.
    J. Leskovec, D. Chakrabarti, J. Kleinberg, et al., “Kronecker graphs: An approach to modeling networks”, Journal of Machine Learning Research, Vol.11, No.3, pp.985-1042, 2008.
    Y. Wang and X. Wu, “Preserving differential privacy in degree-correlation based graph generation”, Transactions on Data Privacy, Vol.6, No.2, pp.127-145, 2013.
    P. Mahadevan, D. Krioukov, K. Fall, et al., “Systematic topology analysis and generation using degree correlations”, ACM Sigcomm Computer Communication Review, Vol.36, No.4, pp.135-146, 2006.
    A. Sala, X. Zhao, C. Wilson, et al., “Sharing graphs using differentially private graph models”, ACM SIGCOMM Conference on Internet Measurement Conference, pp.81-98, 2011.
    R. E. Barlow and H. D. Brunk, “The isotonic regression problem and its dual”, Publications of the American Statistical Association, Vol.67, No.337, pp.140-147, 1972.
    D. Proserpio, S. Goldberg and F. Mcsherry, “A workflow for differentially-private graph synthesis”, ACM Workshop on Workshop on Online Social Networks, pp.13-18, 2012.
    D. Proserpio, S. Goldberg and F. Mcsherry, “Calibrating data to sensitivity in private data analysis: A platform for differentially private analysis of weighted datasets”, Proceedings of the VLDB Endowment, Vol.7, No.8, pp.637-648, 2014.
    F. Mcsherry, “Privacy integrated queries: An extensible platform for privacy-preserving data analysis”, Communications of the ACM, Vol.53, No.9, pp.89-97, 2010.
    P. Samarati, “Protecting respondents’ identities in microdata release”, IEEE Transactions on Knowledge and Data Engineering, Vol.13, No.6, pp.1010-1027, 2001.
    K. Nissim, S. Raskhodnikova, and A. Smith, “Smooth sensitivity and sampling in private data analysis”, ThirtyNinth ACM Symposium on Theory of Computing, pp.75-84, 2007.
    R. Chen, B. C. M. Fung, P. S. Yu, et al., “Correlated network data publication via differential privacy”, VLDB Journal — the International Journal on Very Large Data Bases, Vol.23, No.4, pp.653-676, 2014.
    C. Dwork, F. Mcsherry, K. Nissim, et al., “Calibrating noise to sensitivity in private data analysis”, Proceedings of the 3rd Conference on Theory of Cryptography, pp.265-284, 2006.
    C. Dwork, and G. N. Rothblum, “Concentrated Differential Privacy”, arXiv preprint arXiv:1603.01887, 2016.
  • 加载中


    通讯作者: 陈斌,
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (134) PDF downloads(185) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint