# Does random walk is good metric to compute distances of two sets of nodes in the graph?

I have a big graph and I have three sets(A,B,C) of labeled nodes on it. I would like to compute on average how fare each sets are from each others. In other word, I want to compute distance matrix for these sets. My primary thought was to use random walk, but I'm not sure whether random walk will necessarily give me symmetric distance matrix. Would someone give some suggestions about how can I compute distances of this sets in the graph ?

• There is more than one definition of "average" on graphs. I can imagine that for a distance, the average shortest paths would be more reliable. – Anony-Mousse Oct 12 '17 at 19:07

How about a Hausdorff-like distance on these subsets? All you need would be a proper metric $d$ on the nodes of your graph, which could be just the node-distance (i.e., the number of edges in a shortest path).