Differential Privacy for Social Networks

Contact: Lyudmila Yartseva
Room: BC148
Tel: 31343
Email: lyudmila [dot] yartseva [at] epfl [dot] ch

For the purpose of government and scientific research of social networks, it is desirable to have possibilities to reveal the information about a Social Network's structure. Applying a small amount of random modifications to the social network before publishing its structure or some aggregate characteristic is a common approach to preserving privacy. It is called anonymization. In the realm of relational databases, the notion of differential privacy is used as a means to measure the amount of utility of various characteristics of the database that is preserved by such changes.

The goal of the project is to extend the definition of differential privacy to Social Networks. In particular, to find proper measures of the information loss during anonymization.

Requirements: Solid Probability theory background, Graph theory, Random graphs desirable.