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 ?
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).