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 ?

  • 2
    $\begingroup$ 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. $\endgroup$ – Has QUIT--Anony-Mousse Oct 12 '17 at 19:07
  • $\begingroup$ what gave you the idea to use a stochastic process (random walk) as a distance metric? $\endgroup$ – develarist Oct 9 '20 at 9:20

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.