电子学报 ›› 2016, Vol. 44 ›› Issue (6): 1437-1444.DOI: 10.3969/j.issn.0372-2112.2016.06.026

• 学术论文 • 上一篇    下一篇

基于k-度匿名的社会网络隐私保护方法

龚卫华1, 兰雪锋1, 裴小兵2, 杨良怀1   

  1. 1. 浙江工业大学计算机科学与技术学院, 浙江杭州 310023;
    2. 华中科技大学软件学院, 湖北武汉 430074
  • 收稿日期:2015-01-25 修回日期:2015-10-23 出版日期:2016-06-25 发布日期:2016-06-25
  • 作者简介:龚卫华 男,1977年生于湖北武汉,博士,现为浙江工业大学计算机学院副教授.主要研究方向:数据挖掘、社会网络、大数据计算等.E-mail:whgong@sohu.com;兰雪锋 男,1990年生于浙江丽水,浙江工业大学硕士生.主要研究方向:社会网络、隐私保护;裴小兵 男,1971年生于湖北,博士,现为华中科技大学软件学院副教授.主要研究方向:机器学习、数据挖掘、软件工程、电信网络管理.E-mail:xiaobingp@hust.edu.cn;杨良怀 男,1967年生于浙江新昌,博士,现为浙江工业大学计算机学院教授,主要研究方向:数据库系统、数据挖掘、大数据计算等.E-mail:yanglh@zjut.edu.cn
  • 基金资助:

    浙江省自然科学基金(No.LY13F020026,No.Y1080102,No.LY14F020017,No.LY14C130005);国家自然科学基金(No.61571400,No.61070042);中国博士后科学基金(No.2015M581957);浙江省博士后科研项目择优资助(No.BSH1502019)

Privacy Preservation Method Based on k-Degree Anonymity in Social Networks

GONG Wei-hua1, LAN Xue-feng1, PEI Xiao-bing2, YANG Liang-huai1   

  1. 1. School of Computer Science and Technology, Zhejiang University of Technology, Hangzhou, Zhejiang 310023, China;
    2. School of Software Engineering, Huazhong University of Science and Technology, Wuhan, Hubei 430074, China
  • Received:2015-01-25 Revised:2015-10-23 Online:2016-06-25 Published:2016-06-25

摘要:

针对当前社会网络的匿名化隐私保护方法存在信息损失量巨大、网络关系结构被改变严重等问题,提出一种保持网络结构稳定的k-度匿名隐私保护模型SimilarGraph,运用动态规划方法对社会网络按照节点度序列进行最优簇划分,然后采用移动边操作方式重构网络图以实现图的k-度匿名化.区别于传统的数值扰乱或图修改如随机增加、删除节点或边等方法,该模型的优势在于既不增加网络边数和节点数,也不破坏网络原有连通性和关系结构.实验结果表明,SimilarGraph匿名化方法不仅能有效提高网络抵御度属性攻击的能力,并且还能保持网络结构稳定,同时具有较理想的信息损失代价.

关键词: 社会网络, 隐私保护, k-度匿名, 信息损失

Abstract:

To preserve the privacy of social networks, most existing methods are applied to satisfy different anonymity models, but some serious problems are involved such as often incurring large information losses and great structural modifications of original social network after being anonymized.Therefore, an improved privacy protection model called SimilarGraph is proposed, which is based on k-degree anonymous graph derived from k-anonymity to keep the network structure stable.Where the main idea of this model is firstly to partition network nodes into optimal number of clusters according to degree sequences based on dynamic programming, and then to reconstruct the network by means of moving edges to achieve k-degree anonymity with internal relations of nodes considered.To differentiate from traditional data disturbing or graph modifying method used by adding and deleting nodes or edges randomly, the superiority of our proposed scheme lies in which neither increases the number of nodes and edges in network, nor breaks the connectivity and relational structures of original network.Experimental results show that our SimilarGraph model can not only effectively improve the defense capability against malicious attacks based on node degrees, but also maintain stability of network structure.In addition, the cost of information losses due to anonymity is minimized ideally.

Key words: social network, privacy preservation, k-degree anonymity, information loss

中图分类号: