2华北理工大学管理学院 河北 唐山 063210；
3华北理工大学建筑工程学院 河北 唐山 063210
摘要：以直方图形式的节点度信息的发布提供关于图形的有用信息以及隐私披露的风险。在节点差动隐私（not-dp）的鲁棒性保护下，发布结果的准确性主要取决于该发布任务的全局灵敏度。因此，降低灵敏度是非常重要的。现有的节点dp下的度直方图发布方法大多是基于最大度的限制，其灵敏度仍然很高，导致了难以承受的噪声尺度。本文创新性地提出了解决这一问题的方法。首先，我们引入平均滤波来处理直方图，几乎将原始灵敏度减半。然后，利用一系列的技术，进一步提高了发布的准确性，建立了一个完整的节点-DP下的度直方图发布流程。实验结果表明，本文方法的计算结果表明：提高了精度。
介绍
在互联网和大数据时代，个人信息频繁地被收集和存储，这引起了人们对信息安全的严重关注。特别是，社会网络等许多应用都被建模为由节点和边组成的图。差分隐私（DP）被认为是一种鲁棒的隐私保护模型，它通过随机干扰发布结果来掩盖一条记录的存在，从而保护个人隐私。包含所有节点度信息的度直方图是图的重要统计量。它反映了图形的结构属性。此外，许多其他有用的统计数据，如K星的计数也可以从中得出。在发布程度直方图的同时，也有一些研究使用DP来防止隐私的泄露。然而，所有上述方法旨在满足较弱的边缘-DP，这保护了图形中一个边缘的存在。对于节点-DP，需要更强的保护定义，限制最大程度是控制噪声尺度的必要条件。在Smith的工作中，将原图转化为边加权图，并利用最大流算法确定要删除的边。DATE等人提出了一种以稳定的顺序贪婪地保持边缘的方法，它是程度直方图发布的最佳结果。如下一节所示，在节点DP下，发布结果的准确性与全局灵敏度密切相关。上述方法虽然都进行了尝试，但仍为进一步限制灵敏度提供了空间。幸运的是，均值滤波是一种成熟的技术，在图像处理等领域得到了广泛的应用。
准确度比较
我们首先比较了我们的方法与其他两种工作流程的节点-DP度直方图公布的准确性。它们都来自Day 8的工作，并依赖于π θ度约束。（θ，Ω）-直方图（简称AS（θ，Ω）-Hist）算法在聚合和后处理步骤上与传统算法相似，但没有平均滤波操作。θ累积直方图（简称θ Cu）的思想是不同的.它首先将程度直方图转换为累加形式，然后在加入噪声后将其恢复到每个桶中。在大多数情况下，MDHP的性能优于其他两种算法。然而，这种优势并不明显。这是因为将聚合和后处理优化添加到整个发布过程中，在一定程度上降低了灵敏度对错误的直接影响。然而，灵敏度仍然是决定噪声添加量的最重要因素。因此，难怪MHDP的性能优于其他方法。
期刊文章分类查询,尽在期刊图书馆在Facebook上，当ε较小时，MHDP的性能不如θ Cu.这是因为θ Cu算法使用了一种重组技术，使得该算法对某些数据集中的ε规模相对不敏感。
现在，我们将所有上述方法集合在一起，构成我们完整的工作流程。在此之前，仍然存在一个问题。我们工作流程中的两个步骤与噪声有关：经过一系列优化后，理论误差难以分析。根据组合属性，应该考虑如何将整个隐私预算ε划分为ε1（对于Laplace机制）和ε2（用于指数机制）。由于拉普拉斯机制直接决定了噪声的大小，所以它对隐私预算更加敏感。基于拉普拉斯机制的直方图扰动和基于指数机制的参数选择。当考虑时间效率时，对于额外的平均滤波步骤，我们只需要一个时间复杂度为O（θ）的线性扫描。由于大多数其他步骤的时间复杂度较大，因此对时间效率的影响是微乎其微的。然后，给出了一种完全基于均值滤波的度直方图发布（MDHP）方法的伪码.
同时，在不同的数据集中，同一方法的性能存在很大差异，这表明这些算法的性能受实际数据的影响很大。首先，数据规模越大，发布结果的相对误差越小。这表明，在加入一系列优化后，该方法的绝对误差与原始图像的大小不成正比。另外，结果曲线在不同图上的变化趋势是不一样的，这可能是由于每个图的结构特征不同所致。例如，就图形的密度（边缘/节点）而言，Facebook数据集明显大于其他两个数据集。与此相对应的是，Facebook在实验结果中的情况也有显着性差异。因此，可以认为，当ε的值太小时，对于某些数据集，这三种算法都不能满足实际应用的要求，且比较具有一定的意义。我们只能希望能有更好的算法出现。本文使用了从不同实际应用中导出的三个不同尺度的图形数据集。Facebook是一些用户在著名的社交网络Facebook上建立的朋友网络；CA在预发的网站上记录了高能物理领域研究人员之间的合作；迪泽尔在著名的音乐网站迪泽尔包含了来自某一国家的所有用户和他们的友谊。
结论
本文针对节点-DP下度直方图的发布，引入均值滤波，使灵敏度降低了50%左右。然后，利用聚合等一系列技术，进一步减小发布误差，最终构建出完整的程度直方图发布工作流。与同类方法的对比实验表明，该方法具有较高的精度.在今后的研究中，采用不同长度的滤波间隔是值得研究的。
参考文献：
[1]WORC差别隐私。第33届国际自动机学术讨论会议事录
[2]Hay M，Li C，Miklau G，Jensen D.专网度分布的精确估计。
[3]AI复杂网络的统计力学
论文作者:1杜天歌,2徐艳,3龙振杰
论文发表刊物:《文化时代》2019年19期
论文发表时间:2020/3/18
标签：直方图论文; 节点论文; 灵敏度论文; 方法论文; 算法论文; 噪声论文; 数据论文; 《文化时代》2019年19期论文;