论文部分内容阅读
各种网络应用的出现给人们的生活带来了极大的便利,与此同时,用户的隐私问题也受到了越来越多的关注。网络数据通常采取图来表示,如社交网络图、商业贸易网络图等。这些图可能由节点、边及边上的权重组成,包含着大量的敏感信息,在对图发布前采取适当的隐私保护手段是很有必要的。目前,在网络图数据的隐私保护工作中,要么只是节点、边等结构的隐私保护,要么只是边权重的隐私保护,几乎都是单方面保护图数据的隐私。因此,本文采用差分隐私这一隐私保护模型对带权网络图数据进行隐私保护,提出相对有效的算法,实现同时保护网络图数据中边权重和结构的隐私。本文首先提出了带权图的隐私保护算法(WGPA)。边权重保护先于图的结构保护,二者是互相关联与影响的关系。在对图数据集中的边权重扰动时,采用的是差分隐私的Laplace机制进行扰动,为每个图中的边权重序列分配隐私预算,设计合理的隐私预算分配策略。考虑到图结构的复杂性,将图转化成编码模式,并在对图的编码过程中将扰动后的权重值融入其中;再利用频繁子图挖掘算法,在挖掘的过程中采用差分隐私的Laplace机制和指数机制对图的结构进行扰动和筛选,最终得到最为理想的噪音版的带权网络图数据。因此本文的算法适合用于带权网络图数据集的隐私保护,可以实现同时保护用户的个人隐私及用户之间关系的隐私。本文提出了扰动图集的图生成算法。在图的生成过程中,对边的频繁度添加Laplace噪音扰动,每次按增加一条边的形式生成图,并根据已选边继续生成候选邻居边集。为了很好的选择可能生成的邻居边,设计了合理的邻居边筛选条件,最后输出扰动后的图数据集。同时,本文对整个隐私预算再分配,并将该算法应用到WGPA算法中,提出图的生成与保护算法。本文最后针对提出的算法进行了实验验证。采用真实的图数据集验证了本文算法的有效性,从数据效用性等方面对比分析了本文提出的算法,实验结果证明本文的算法是有效的。