I need to compute an affinity matrix for an unweighted undirected graph of related musical artists for the purposes of spectral clustering. Now, the most obvious affinity measure to use is shortest distance. However, this is quite a large graph (1 million+ nodes and vertices), so finding the all-pairs shortest path lengths is quite computationally difficult. Even for an unweighted graph, the runtime would still amount to running a breadth-first search for each node. The Floyd-Warshall algorithm wouldn't help in this case either, since the graph in question is more sparse than it is dense.
Are there any other (more efficient) ways of generating an affinity matrix for a graph of this size? Perhaps there are alternative affinity measures that would be more well-suited to this task?