  Given a graph, the densest subgraph problem asks for a set of vertices such
that the average degree among these vertices is maximized. Densest subgraph has
numerous applications in learning, e.g., community detection in social
networks, link spam detection, correlation mining, bioinformatics, and so on.
Although there are efficient algorithms that output either exact or approximate
solutions to the densest subgraph problem, existing algorithms may violate the
privacy of the individuals in the network, e.g., leaking the
existence/non-existence of edges.
  In this paper, we study the densest subgraph problem in the framework of the
differential privacy, and we derive the first upper and lower bounds for this
problem. We show that there exists a linear-time $\epsilon$-differentially
private algorithm that finds a $2$-approximation of the densest subgraph with
an extra poly-logarithmic additive error. Our algorithm not only reports the
approximate density of the densest subgraph, but also reports the vertices that
form the dense subgraph.
  Our upper bound almost matches the famous $2$-approximation by Charikar both
in performance and in approximation ratio, but we additionally achieve
differential privacy. In comparison with Charikar's algorithm, our algorithm
has an extra poly-logarithmic additive error. We partly justify the additive
error with a new lower bound, showing that for any differentially private
algorithm that provides a constant-factor approximation, a sub-logarithmic
additive error is inherent.
  We also practically study our differentially private algorithm on real-world
graphs, and we show that in practice the algorithm finds a solution which is
very close to the optimal
