[Air-L] Paper: De-anonymizing Social Networks

[Richard Forno]

De-anonymizing Social Networks


Abstract:

Operators of online social networks are increasingly sharing  
potentially sensitive information about users and their relationships  
with advertisers, application developers, and data-mining researchers.  
Privacy is typically protected by anonymization, i.e., removing names,  
addresses, etc.

We present a framework for analyzing privacy and anonymity in social  
networks and develop a new re-identification algorithm targeting  
anonymized social-network graphs. To demonstrate its effectiveness on  
real-world networks, we show that a third of the users who can be  
verified to have accounts on both Twitter, a popular microblogging  
service, and Flickr, an online photo-sharing site, can be re- 
identified in the anonymous Twitter graph with only a 12% error rate.

Our de-anonymization algorithm is based purely on the network  
topology, does not require creation of a large number of dummy “sybil”  
nodes, is robust to noise and all existing defenses, and works even  
when the overlap between the target network and the adversary’s  
auxiliary information is small.

< - >

http://33bits.org/2009/03/19/de-anonymizing-social-networks/