改进的k度匿名图构造算法

摘要：

在社交网络中,为防范用户隐私泄漏,在用户数据发布前需要做匿名化处理.针对以节点度数为背景知识的隐私攻击,将社交网络匿名化问题建模为图的k度匿名化问题;其主要方法是对图添加尽可能少的边或点来满足度匿名化要求,其中要求添加边或点较少是期望尽可能保持原图结构特性.目前,加边类算法并不能很好地保留平均路径长度等结构特性;加边且可加点类算法尽管能更好地保留原图结构特性,但添加的边或点较多.本文融合两类算法的策略提出改进算法.新算法利用贪心法生成匿名度序列,然后基于社区结构加边,并且优先满足其匿名代价高于平均匿名代价的节点的匿名化要求;若加边不能完成匿名化,则通过加点实现图匿名化.真实数据集上的实验结果表明新算法能更好地保留图的几种典型的结构特性,并且添加的边或点更少.

关键词：社交网络、隐私保护、k度匿名化、度序列、加边、加点、复杂网络

所属期刊栏目：31

分类号：TP301.6;O157.5;TP181

在线出版日期：2022-05-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：157-164