Effective resistance criterion for negative curvature: Application to congestion control

摘要

This paper develops the asymptotic relation between the resistance of the least resistive path Rlrp(i; j) and the effective resistance Reff (i; j) between two extreme points i; j of a resistive lattice, as an electrical engineering mean to check negative curvature of a graph. More specifically, it is suggested that the behavior of Rlrp(i; j)=Reff (i; j), understood asymptotically in the sense of a growing size network, is able to discriminate a Euclidean grid versus a hyperbolic grid. It is shown that the fraction asymptotically saturates in case of a hyperbolic grid, while it grows without bound in the Euclidean case. In the popular case of a Gromov hyperbolic grid quasi-isometric to a tree, the asymptotic saturation of Rlrp(i; j)=Reff (i; j) is easy to prove, but the major contribution of this paper is to show that the same result holds under the by far less trivial situation of a hyperbolic grid not quasi-isometric to a tree. Applications include the role of curvature in congestion control problems understood in the broad sense as they apply to data network and power grid.