  A growing body of research leverages social network based trust relationships
to improve the functionality of the system. However, these systems expose
users' trust relationships, which is considered sensitive information in
today's society, to an adversary.
  In this work, we make the following contributions. First, we propose an
algorithm that perturbs the structure of a social graph in order to provide
link privacy, at the cost of slight reduction in the utility of the social
graph. Second we define general metrics for characterizing the utility and
privacy of perturbed graphs. Third, we evaluate the utility and privacy of our
proposed algorithm using real world social graphs. Finally, we demonstrate the
applicability of our perturbation algorithm on a broad range of secure systems,
including Sybil defenses and secure routing.
