社交网络隐私保护中的随机算法

刘华玲, 郑建国, 孙辞海

刘华玲, 郑建国, 孙辞海. 社交网络隐私保护中的随机算法[J]. 信息与控制, 2012, (2): 197-201,209. DOI: 10.3724/SP.J.1219.2012.00197
引用本文: 刘华玲, 郑建国, 孙辞海. 社交网络隐私保护中的随机算法[J]. 信息与控制, 2012, (2): 197-201,209. DOI: 10.3724/SP.J.1219.2012.00197
LIU Hualing, ZHENG Jianguo, SUN Cihai. Randomized Algorithm for Privacy Preservation in Social Networks[J]. INFORMATION AND CONTROL, 2012, (2): 197-201,209. DOI: 10.3724/SP.J.1219.2012.00197
Citation: LIU Hualing, ZHENG Jianguo, SUN Cihai. Randomized Algorithm for Privacy Preservation in Social Networks[J]. INFORMATION AND CONTROL, 2012, (2): 197-201,209. DOI: 10.3724/SP.J.1219.2012.00197
刘华玲, 郑建国, 孙辞海. 社交网络隐私保护中的随机算法[J]. 信息与控制, 2012, (2): 197-201,209. CSTR: 32166.14.xk.2012.00197
引用本文: 刘华玲, 郑建国, 孙辞海. 社交网络隐私保护中的随机算法[J]. 信息与控制, 2012, (2): 197-201,209. CSTR: 32166.14.xk.2012.00197
LIU Hualing, ZHENG Jianguo, SUN Cihai. Randomized Algorithm for Privacy Preservation in Social Networks[J]. INFORMATION AND CONTROL, 2012, (2): 197-201,209. CSTR: 32166.14.xk.2012.00197
Citation: LIU Hualing, ZHENG Jianguo, SUN Cihai. Randomized Algorithm for Privacy Preservation in Social Networks[J]. INFORMATION AND CONTROL, 2012, (2): 197-201,209. CSTR: 32166.14.xk.2012.00197

社交网络隐私保护中的随机算法

基金项目: 国家自然科学基金资助项目(70971020);上海市高等教育内涵建设工程“085工程”资助项目(08509008)
详细信息
  • 中图分类号: G203

Randomized Algorithm for Privacy Preservation in Social Networks

  • 摘要: 提出了一种基于高斯随机乘法的社交网络隐私保护方法.该算法利用无向有权图表示社交网络,通过高斯随机乘法来扰乱其边的权重, 保持网络最短路径不变并使其长度应与初始网络的路径长度尽可能接近,以实现对社交网络的隐私保护.从理论上证明了算法的可行性及完美算法的不存在性. 采用这种随机乘法得到的仿真结果符合理论分析结果.
    Abstract: A privacy preservation method in social networks is proposed based on Gaussian randomization multiplication. The method applies an undirected weighted graph to representing a social network and perturbs the weights of some edges by using the Gaussian randomization multiplication to maintain the shortest path of the social network and to make its length as close as possible to that in the original network in order to realize the the privacy preservation in social networks. The feasibility of the proposed algorithm and the nonexistence of the perfect algorithm are proved theoretically. Simulation results obtained by the randomization multiplication method agree well with the theoretical analysis.
  • [1] Bapna S, Gangopadhyay A. A wavelet-based approach to preserve privacy for classification mining[J]. Decision Sciences, 2006, 37(4): 623-642.
    [2] Muralidhar K, Parsa R, Sarathy R. A general additive data perturbation method for database security[J]. Management Science, 1999, 45(10): 1399-1415.
    [3] Han J, Kamber M. Data mining: Concepts and techniques[M]. Amsterdam, Netherlands: Elsevier Science Publishers, 2006.
    [4] Liu L, Wang J, Zhang J. Wavelet-based data perturbation for simultaneous privacy-preserving and statistics-preserving[C]//Proceedings of the 2008 IEEE International Conference on Data Mining Workshops. Piscataway, NJ, USA: IEEE, 2008: 27-35.
    [5] Mukherjee S, Chen Z Y, Gangopadhyay A. A privacy preserving technique for Euclidean distance-based mining algorithms using Fourier-related transforms[J]. The VLDB Journal, 2006, 15(4): 293-315.
    [6] Xu S T, Zhang J, Han D W, et al. Datadistortion for privacy protection in a terrorist analysis system[C]//Proceedings of the 2005 IEEE International Conference on Intelligence and Security Informatics. Piscataway, NJ, USA: IEEE, 2005: 459-464.
    [7] Xu S T, Zhang J, Han D W, et al. Singular value decomposition based data distortion strategy for privacy protection[J]. Knowledge and Information Systems, 2006, 10(3): 383-397.
    [8] Evfrmievski A. Randomization in privacy preserving data mining[J]. SIGKDD Explorations Newsletter, 2002, 4(2): 43-48.
    [9] Hay M, Miklau G, Jensen D, et al. Anonymizing social networks[R]. Amherst, MA, USA: University of Massachusetts, 2007.
    [10] Zheleva E, Getoor L. Preserving the privacy of sensitive relationships in graph data[C]//Proceedings of the 1st ACM SIGKDD International Conference on Privacy, Security, and Trust in KDD. New York, NY, USA: ACM, 2007: 153-171.
    [11] Zhou B, Pei J. Preserving privacy in social networks against neighborhood attack[C]//Proceedings of the 24th International Conference on Data Engineering. New York, NY, USA: ACM, 2008: 506-515.
    [12] Tang J, Zhang D, Yao L M. Social network extraction of academic researchers[C]//Proceedings of 2007 IEEE International Conference on Data Mining. Piscataway, NJ, USA: IEEE, 2007: 292-301.
    [13] 李锋.面向数据挖掘的隐私保护方法研究[D].上海:上海交通大学,2008. Li F. Research on privacy preserving methods for data mining[D]. Shanghai: Shanghai Jiaotong University, 2008.
    [14] 杨维嘉.在数据挖掘中保护隐私信息的研究[D].上海:上海交通大学,2008. Yang W J. Research on Privacy Preserving Data Mining[D]. Shanghai: Shanghai Jiaotong University, 2008.
    [15] Cormen T H, Leiserson C E, Rivest R L. Introduction to algorithms[ M]. 1st ed. Cambridge, MA, USA: MIT Press, 1990.
    [16] Stigler S M. Statistics on the table[M]. Cambridge, Massachusetts, USA:Harvard University Press, 1999.
    [17] Agrawal R, Srikant R. Privacy-preserving data mining[C]// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York, NY, USA: ACM, 2000: 439-450.
计量
  • 文章访问数:  1973
  • HTML全文浏览量:  2
  • PDF下载量:  289
  • 被引次数: 0
出版历程
  • 收稿日期:  2011-04-10
  • 发布日期:  2012-04-19

目录

    /

    返回文章
    返回
    x