论文部分内容阅读
从单个多图中挖掘频繁模式现已经成为研究热点,如社交网络中,两个人之间可能有诸如Facebook、Twitter和LinkedIn等多个关系,挖掘社交网络多图中的频繁子图对发现社会互动机制至关重要。但如果数据中含有敏感信息,此时将挖掘结果未经处理直接发布或者共享出去的话,将会对参与数据的用户的隐私造成威胁。因此,在发布这些信息之前需要进行适当的隐私保护处理。目前存在的频繁子图挖掘的差分隐私保护方法,都是对单边图进行操作的,还没有研究涉及多边图上频繁子图挖掘的隐私保护问题。因此本文提出一个针对单个多图的频繁子图挖掘差分隐私保护算法DPFS-LM(Differentially Private Frequent Subgraph Mining in a Single Large Multigraph),该算法根据多图自身的特点设计了一个二阶段机制:噪音挖掘频繁种子阶段和基于差分隐私的后续频繁子图挖掘阶段。为了提高效用性,该算法在噪音挖掘频繁种子阶段应用了智能截断的思想对超过长度限制的多边进行截断,进而降低了加入的噪音量。在基于差分隐私的后续频繁子图挖掘阶段结合指数机制和拉普拉斯机制来隐私的发现后续大小的频繁子图。最后经过严格的理论分析和在真实数据集上的实验来表明DPFS-LM算法的效用性和执行效率。本文针对单个多图数据上频繁子图挖掘方法存在的隐私问题展开研究,通过对多图数据的复杂结构以及进行频繁子图挖掘所产生的隐私问题进行分析,提出一种在单个多图中挖掘频繁子图的差分隐私保护方法,用以解决在蕴含更加丰富信息的多图数据中挖掘并发布频繁子图模式带来的隐私泄露问题。本文的主要研究工作如下:(1)对频繁子图挖掘和隐私保护方法的研究现状分别进行综述和分析,指出现有频繁子图挖掘的差分隐私保护方法的局限性,说明现有工作不能直接应用于多图数据隐私保护场景。(2)讨论在多图上挖掘频繁子图存在的隐私问题,针对该场景下多图数据受到推理攻击而引起隐私泄露的问题进行详细的分析,说明在多图数据中挖掘频繁模式会比单边图数据场景泄露更多的隐私。(3)提出针对单个多图的频繁子图挖掘差分隐私保护算法DPFS-LM。该算法主要包括两个阶段,第一阶段为噪音挖掘频繁种子阶段,主要是根据多图的数据特点对其多边进行处理,在此阶段隐私的挖掘出大小为1的频繁子图;第二阶段是在满足差分隐私保护的条件下挖掘后续大小的频繁子图,首先通过指数机制来挑选频繁子图模式,然后采用拉普拉斯机制来扰动挑选出的频繁子图的计数值。同时,对所提出的各阶段方法进行隐私分析,并以严谨的数学公式证明DPFS-LM算法整体上满足ε-差分隐私。(4)给出相应算法的伪代码描述,在两个真实的数据集Citeseer和DBLP-Multigraph上进行实验测试,选择相对误差(RE)、F-score和运行时间这三个评价指标进行评估。实验结果验证提出的多图场景下的频繁子图差分隐私保护方法在保护隐私的同时保证了数据的可用性。