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.