Differentially Private Densest Subgraph Detection
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph MiningSimilar Papers 제목 키워드 기반
Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling
We study the sublinear space continual release model for edge-differentially private (DP) graph algorithms, with a focus on the densest subgraph problem (DSG) in the insertion-only setting. Our main result is the first c…
Differentially Private Densest-$k$-Subgraph
Many graph datasets involve sensitive network data, motivating the need for privacy-preserving graph mining. The Densest-$k$-subgraph (D$k$S) problem is a key primitive in graph mining that aims to extract a subset of $k…
Graph MiningPrivacy PreservingSensitivityDifferentially Private Clustering: Tight Approximation Ratios
We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient differentially private algorithms that a…
ClusteringParallel Algorithms for Densest Subgraph Discovery Using Shared Memory Model
The problem of finding dense components of a graph is a widely explored area in data analysis, with diverse applications in fields and branches of study including community mining, spam detection, computer security and b…
Computer SecuritySpam detectionDifferentially Private Range Subgraph Counting
Subgraph counting is a fundamental problem in graph analysis. Motivated by practical scenarios where graph analytics are performed on subgraphs induced by selected vertices -- rather than on the entire graph -- and by gr…