Not Entirely Anonymous

For anyone interested in privacy, I highly recommend reading “De-anonymizing Social Networks” by Arvind Narayanan and Vitaly Shmatikov.

Here’s a snippet from the introduction:

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.

So, basically, what they’ve done is effectively identify matching Twitter and Flickr accounts. Abstracted, though, their algorithm points out that all they need to map the relationships is an undirected data graph (with indications a directed graph would improve the effectiveness). Graphs like this can be found everywhere, and is what drives the behavioral targeting industry.

With this algorithm running around now, I guess data brokers will have to work a bit harder to anonymize your data. Perhaps they’ll pinch some ideas from Alex Ntoulas at Microsoft and start injecting noise into your systems.