Top-k 频繁子图挖掘的差分隐私保护算法

来源：计算机技术与发展杂志2022年第05期北京时间：

作者：徐捷;杨庚;';白云璐;'

单位：1. 南京邮电大学 计算机学院,江苏 南京 210046;2. 江苏省大数据安全与智能处理重点实验室,江苏 南京 210023;3. 南京中医药大学 信息技术学院,江苏 南京 210003

摘要：频繁子图挖掘是频繁模式挖掘的一种具体形式,广泛应用于社会网络分析、生物技术、推荐系统等领域。 然而,图数据集中可能包含一些敏感的信息,在挖掘过程中或发布频繁子图信息时都可能造成隐私的泄露。 对此,提出一种面向差分隐私保护的 top-k 子图挖掘算法———DP-TGM( Differential Private Top-k subGraph Mining) 。 算法首先依据挖掘出的频繁点和边对数据集剪枝,然后将频繁的边依次进行扩展挖掘,得到最终的 top-k 频繁子图。 该算法使用一个优先权队列存储临时挖掘到的前 k 个最频繁的子图,在扩展挖掘的过程中不断更新队列里的元素,并将阈值始终更新为队列里的最小噪音支持度,减少图的扩展次数。 算法使用拉普拉斯机制在三个不同的阶段对子图的真实支持度添加噪音,并且采用均分法和特殊级数法对隐私预算进行合理的分配以提高数据可用性。 文章用理论证明算法满足 着 - 差分隐私保护,且在不同规模的数据集上验证了算法的可用性。

关键词：top-k 频繁子图;差分隐私;拉普拉斯机制;隐私预算;数据可用性