Algorithm for finding "mean center" of unweighted graph

I have a large sparse unweighted undirected graph (20M vertices, 60M edges) and would like to find what I'm calling the "mean center" (the vertex w/ shortest mean distance to all other vertices. Does this already have a name?). I know of an $O(N^2)$ solution: Starting at every vertex: BFS to calculate the mean distance to all other vertices, choose the minimum. But $N^2$ is too slow for a graph this size, is there any way to calculate the "mean center" in faster than $N^2$ time? Are there any good approximation algorithms? Or more efficient algorithms which find some similar "center" of a graph?

Another heuristic idea: Find a long shortest path, and pick the vertex halfway along it.

Pick a vertex and run BFS from it. For some small $k$, take the $k$ furthest vertices from the original vertex that the BFS determines, and repeat the process on each of them, keeping the $k$ overall furthest vertices each time. Repeat a few times.

If the graph is a tree, this is in fact guaranteed to find the longest path with $k=1$ after the second iteration! For a general graph, I don't know of any such guarantee -- but you are likely to find a reasonably long shortest path.

Once you have a sufficiently long path, pick the vertex halfway along it. (This is uniquely determined if the path has an odd number of vertices; if it has an even number, you could choose arbitrarily, or run BFS again from the middle two vertices, and pick whichever scores higher.)

StackExchange Computer Science Q#119854, answer score: 2