This is my work with my advisor. Our paper is online, take a look if you're interested. http://randomwalker.info/social-networks/ We also have an FAQ that answers the common misconceptions: http://www.cs.utexas.edu/~shmat/socialnetworks-faq.html

I posted your paper yesterday (http://news.ycombinator.com/item?id=534399), no one seemed to bother... I am guessing bbc is sexier or something.

I really enjoyed it

I think it may just be because the title "De-anonymizing social networks" didn't actually convey what the experiment found, and it's the result (as communicated in the title here) that got people interested enough to click.

This seemed likely to many graph theorists. Glad someone proved it.

Privacy on pyre.