Actually, even without mentioning his Bitcoin address someone may leak enough information to be tied to it. Let’s say you overhear someone say “hey, I’ll send you $100 today at noon”. The researchers demonstrate that it is possible to identify potential transactions matching this information. That means that the innocuous overheard sentence may leak the identity of two persons.
Scrapping websites and correlating transactions means that it is possible to enrich the Bitcoin graph. Instead of just looking at a set of addresses, we can tie in the public identities used unsafely by Bitcoin users. These identities are not necessarily easy to match with “real” persons though. For non transparent identities, one would have to investigate further to find the name or location of the person using the identity. That practice is called doxing and can have good results.
All of this doesn’t mean Bitcoin is not anonymous. People who are tying themselves publicly to Bitcoin addresses are less anonymous than the average Bitcoin user though.
An other interesting finding is that Bitcoin is similar to the web. Both can be modeled as graphs. With Bitcoin we have addresses and transactions, with the web it is websites and hypertext links. As a consequence, the tools used to analyse the web can be used for Bitcoin. The PageRank algorithm helped Google assess credibly the authority of different websites on topics. Michael Fleder, Michael S. Kester and Sudeep Pillai applied it to Bitcoin.
They found for example that among the Bitcoin addresses with a high PageRank is the account of the FBI. During the seizure of the Silk Road, it orchestrated a series of 445 transactions of exactly 324 Bitcoins. Without knowing that Bitcoin address or the seizure, they could have identified the importance of the event.
Bitcoin has a complicated relationship with anonymity. Just because the public addresses used by its users are weird doesn’t mean that they can’t be tied to real persons. Every transaction, every public mention of Bitcoin addresses contribute to give a clearer picture of the person (or persons) behind a public address. And with graph analytics, that data can be analysed and deliver interesting insights.