2008 Poster Sessions : Link Privacy in Social Networks

Student Name : Aleksandra Korolova, Ying Xu, and Shubha Nabar
Advisor :
Research Areas: Computer Systems
We consider a privacy threat to a social network in which the goal of an attacker is to obtain knowledge of a significant fraction of the links in the network. We formalize the typical social network interface and the information about links that it provides to its users in terms of lookahead. We consider a particular threat where an attacker subverts user accounts to get information about local neighborhoods in the network and pieces them together in order to get a global picture. We analyze, both experimentally and theoretically, the number of user accounts an attacker would need to subvert for a successful attack, as a function of his strategy for choosing users whose accounts to subvert and a function of lookahead provided by the network. We conclude that such an attack is feasible in practice, and thus any social network that wishes to protect the link privacy of its users should take great care in choosing the lookahead of its interface, limiting it to 1 or 2, whenever possible.

Ying Xu received her B.S. and M.S. in Computer Science from Beijing University in China. She is currently pursuing her Ph.D in Computer Science at Stanford University advised by Rajeev Motwani. Her research focuses on applying randomized algorithms to web and database. She is a recipient of the Stanford Graduate Fellowship.

Aleksandra Korolova received a B.S. degree in Mathematics with Computer Science from MIT. She is currently a Ph.D. candidate in Computer Science at Stanford University, advised by Rajeev Motwani. Her research focuses on algorithmic problems that arise in Internet applications, such as Web search, online advertising, and social networks.

Shubha Nabar received a B.S.E. in Computer Science from Princeton University and is currently pursuing a Ph.D. in Computer Science at Stanford University under the supervision of Rajeev Motwani. Her research interests are in data privacy, data mining and search.