  Social network based trust relationships present a critical foundation for
designing trustworthy systems, such as Sybil defenses, secure routing, and
anonymous/censorshipresilient communications. A key issue in the design of such
systems, is the revelation of users' trusted social contacts to an
adversary-information that is considered sensitive in today's society.
  In this work, we focus on the challenge of preserving the privacy of users'
social contacts, while still enabling the design of social trust based
applications. First, we propose LinkMirage, a community detection based
algorithm for anonymizing links in social network topologies; LinkMirage
preserves community structures in the social topology while anonymizing links
within the communities. LinkMirage considers the evolution of the social
network topologies, and minimizes privacy leakage due to temporal dynamics of
the system.
  Second, we define metrics for quantifying the privacy and utility of a time
series of social topologies with anonymized links. We analyze the privacy and
utility provided by LinkMirage both theoretically, as well as using real world
social network topologies: a Facebook dataset with 870K links and a large-scale
Google+ dataset with 940M links. We find that our approach significantly
outperforms the existing state-of-art.
  Finally, we demonstrate the applicability of LinkMirage in real-world
applications such as Sybil defenses, reputation systems, anonymity systems and
vertex anonymity. We also prototype LinkMirage as a Facebook application such
that real world systems can bootstrap privacy-preserving trust relationships
without the cooperation of the OSN operators.
