Finding the nearest node to a given set of nodes in a graph I am looking for an algorithm that, given a large weighted undirected graph, would find the node that has minimum average distance from a given set of nodes in the graph.
I think Dijkstra's shortest path algorithm would be suitable for your problem. But since you want to find the shortest-path node from a set of nodes and not from just one node, you need to tweak it.

The algorithm is quite straightforward but a bit obtuse, try searching for animated expositions on YouTube.