LAUSR

We consider the network analytics problem of comparing two distance metrics on the same set of n entities. The classical solution to this problem is the Mantel test, which uses permutation testing to accept or reject the null hypothesis that there is “no relationship between the two metrics.” Its computational complexity is n2 times the number of permutations (based on a user supplied parameter). This work makes two contributions: (1) DIMECOSTP, a more efficient hypothesis test based on uniform random spanning trees whose complexity is n times the number of permutations. (2) DIMECOSTCC, which uses the correlation coefficient between the two sets of edge weights in a random spanning tree as an indication of the strength of the relationship between the two distance metrics. Both methods utilize sound statistical principles. Experimental results confirm the efficacy of our methods.