龚卫华，兰雪锋，裴小兵，杨良怀

(1.浙江工业大学计算机科学与技术学院，浙江杭州 310023； 2.华中科技大学软件学院，湖北武汉 430074)



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

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

(1.浙江工业大学计算机科学与技术学院，浙江杭州 310023； 2.华中科技大学软件学院，湖北武汉 430074)

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

社会网络；隐私保护；k-度匿名；信息损失

1　引言

近年来，社会网络的流行已深刻地改变了人们的日常生活和交流方式，国内外著名社交网站如Facebook、QQ、人人网等注册用户数量不断攀升，以Facebook为例，用户总数在2013年已突破10亿，其中包含1500亿条朋友链接，这些社会网络数据蕴含巨大的商业价值和应用前景，例如可促进广告、游戏、零售等业务迅速增长.然而，人们在使用基于社会网络的应用同时面临着严重的……