My first guess was that they used the artist.getSimilar API method. I dug around a little and found this:

"In April 2009, we crawled the website [last.fm] by starting with Beethoven, and the top 20 musicians most similar to Beethoven, provided that each has at least 100,000 listeners. We then found the top 20 most similar musicians to each of those with at least 100,000 listeners and proceed recursively. Our crawl yielded a graph with 2782 musicians, with edge weights the similarity between musicians."

- Emden Gansner, Yifan Hu, Stephen Kobourov and Chris Volinsky, Putting Recommendations on the Map - Visualizing Clusters and Relations: http://arxiv.org/abs/0906.5286

On an semi-related note, there is a wealth of information on visualizing music in the slide deck here: http://visualizingmusic.com/2009/10/22/using-visualizations-...

thanks!