摘要
频繁图模式挖掘是数据挖掘中的研究热点，频繁子图挖掘是频繁图模式挖掘的新兴研究方向，在社交网络中发现频繁子图对于理解社会互动、研究疾病的传播有重要的作用，然而在挖掘及发布时又会带来隐私泄露的风险。因此，针对静态场景及动态场景的频繁子图挖掘的隐私问题，提出了以下两个算法： (1)针对静态场景，本文提出了一种更加安全有效的满足差分隐私的深度优先搜索频繁子图挖掘算法DP-gSpan。传统方法主要是基于差分隐私的广度优先搜索进行的频繁子图挖掘，这些算法普遍存在支持度计算复杂、候选图集太多导致准确率以及效率不高等问题。与以往不同，DP-gSpan算法通过设计一个隐私预算分配策略实现了隐私预算的合理化分配，剪枝截断策略实现了候选集合尺寸的缩减，从而解决了此前算法存在的不足。经过理论分析及实验验证，DP-gSpan算法相对于现有的解决方案具有更好的效用性。 (2)针对动态场景，本文提出了一种增量图中的差分隐私频繁诱导子图挖掘算法DPSR。为了更好的平衡统计结果的隐私性及时效性，DPSR算法在滑动窗口模型中结合差分隐私，并在挖掘及发布的过程中设计了合适的隐私预算分配策略，根据计算连续时间戳隐私挖掘的频繁图模式集合之间的差异来判断当前时间戳的统计结果是需要对支持度加噪后发布还是采用之前的隐私结果近似代替发布。本文最后对DPSR算法进行了理论分析及实验评估，证明了DPSR算法可以在满足数据隐私性的同时高效的完成挖掘任务。
NETL