Abstract

We study the family of p-resistances on graphs for This family generalizes the standard resistance distance. We prove that for any fixed graph, for p = 1 the p-resistance coincides with the shortest path distance, for p = 2 it coincides with the standard resistance distance, and for it converges to the inverse of the minimal s-t-cut in the graph. Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. We prove that an interesting phase transition takes place. There exist two critical thresholds such that if then the p-resistance depends on meaningful global properties of the graph, whereas if it only depends on trivial local quantities and does not convey any useful information. We can explicitly compute the critical values: where d is the dimension of the underlying space (we believe that the fact that there is a small gap between is an artifact of our proofs). We also relate our findings to Laplacian regularization and suggest to use q-Laplacians as regularizers, where q satisfies