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

Richard Forno rforno at infowarrior.org
Mon Mar 30 07:09:26 PDT 2009

De-anonymizing Social Networks


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.

< - >


More information about the Air-L mailing list