Appears in collection : Nexus Trimester - 2016 - Secrecy and Privacy Theme

Social networks are an integral part of our lives. They provide significant amount of explicit and implicit information about their users. On one hand this data could be analyzed and harnessed for multitude of purposes: conducting polls, market analysis, etc. On the other hand, release of data could seriously compromise user privacy. Thus, before its release, the data must be processed in a manner that minimizes the risk of sharing private information of the users while allowing for performing the desired data analytics. In this talk we study the limits of de-anonymizability of social networks by casting the problem as graph matching. Specifically, for the class of Erdos-Renyi random graph models, we ask when does the correlation induced by the structural properties of the graph allow the users to be de-anonymized? We provide achievability and converse bounds that differ by a factor of two throughout the parameter space.