Network science meets circuit theory: Kirchhoff index of a graph and the power of node-to-datum resistance matrix

摘要

The emerging area of network science studies the properties of networks and dynamic processes on networks (such as spread of epidemics) that arises in a variety of applications including electrical, communication, internet, biological, ecological networks etc. Treating each element of a graph as a resistance, Kirchhoff index defined by the chemistry community is the sum of the effective resistances across all pairs of nodes of the graph. This index has been studied using the graph Laplacian (same as the indefinite admittance matrix). In this paper we present a simpler formula for Kirchhoff index based on the properties of the node-to-datum resistance matrix, considerably reducing the computational effort. A byproduct of this formula is a new invariant property of node-to-conductance matrix that does not depend on the choice of the datum node, extending the currently available knowledge on the determinant of the node-to-conductance matrix. Furthermore it can be shown that link congestion (if random-walk routing is used) can be estimated using the elements of the node-to-datum resistance matrix.