Differentially Private Densest Subgraph Detection
Differentially Private Densest Subgraph Detection
复制标题
DOI：
--
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Dung Nguyen;A. Vullikanti
中科院分区：
文献类型：
--
作者：
Dung Nguyen;A. Vullikanti
最密集子图检测是一个基本的图挖掘问题，有着大量的应用。对于在大规模网络中寻找最密集子图的有效算法，人们已经做了大量的工作。然而，在许多领域中，网络是私有的，返回最密集的子图可以揭示有关网络的信息。差分隐私是处理此类设置的强大框架。研究了边隐私模型中的最密集子图问题，其中图的边是隐私的。本文首次提出了该问题的顺序和并行差分私有算法。我们证明了我们的算法具有加性近似保证。我们在大量现实世界的网络上评估了我们的算法，并观察到当网络具有高密度时，良好的隐私-准确性权衡。
Densest subgraph detection is a fundamental graph mining problem, with a large number of applications. There has been a lot of work on efficient algorithms for finding the densest subgraph in massive networks. However, in many domains, the network is private, and returning a densest subgraph can reveal information about the network. Differential privacy is a powerful framework to handle such settings. We study the densest subgraph problem in the edge privacy model, in which the edges of the graph are private. We present the first sequential and parallel differentially private algorithms for this problem. We show that our algorithms have an additive approximation guarantee. We evaluate our algorithms on a large number of real-world networks, and observe a good privacy-accuracy tradeoff when the network has high density.