In the book The Algorithmic Foundations of Differential Privacy by Cynthia Dwork, Aaron Roth on page 24, databases that take the form of graphs are discussed.
We could on the other hand consider differential privacy at a level of granularity corresponding to edges, and ask our algorithms to be insensitive only to the addition or removal of single, or small numbers of, edges from the graph. This is of course a weaker guarantee, but might still be sufficient for some purposes. Informally speaking, if we promise $\epsilon$-differential privacy at the level of a single edge, then no data analyst should be able to conclude anything about the existence of any subset of $1/\epsilon$ edges in the graph. In some circumstances, large groups of social contacts might not be considered sensitive information: for example, an individual might not feel the need to hide the fact that the majority of his contacts are with individuals in his city or workplace, because where he lives and where he works are public information. On the other hand, there might be a small number of social contacts whose existence is highly sensitive (for example a prospective new employer, or an intimate friend). In this case, edge privacy should be sufficient to protect sensitive information, while still allowing a fuller analysis of the data than vertex privacy. Edge privacy will protect such an individual’s sensitive information provided that he has fewer than $1/\epsilon$ such friends.
How do they derive the number $\large\frac{1}{\epsilon}$ in this discussion? Does the amount of $\epsilon$ still stand for privacy loss? Thanks for your help in advance!
