Resistance Distance, Kirchhoff Index, Foster's Theorems, and Generalizations

Abstract

The emerging area of network science studies structural characteristics of networks and dynamical processes on networks such as spread of epidemics, vulnerability of power grids to cascading failures etc. In this area, several measures of network performance have been introduced and studied. In this dissertation, we study two measures, namely, resistance distance and Kirchhoff index. Treating each element of a graph as a resistance, resistance distance between two nodes u and v is the effective resistance across u and v. Kirchhoff index defined by the chemistry community is the sum of the effective resistances across all pairs of nodes of the graph. Kirchhoff index, also called network criticality, has been studied by the communication network community. Kirchhoff index has been studied using the graph Laplacian matrix which is the same as the indefinite admittance matrix of a resistance network. Our research is on reducing the computational effort in calculating the Kirchhoff index in networks. First a simpler formula for Kirchhoff index based on the properties of node-to-datum resistance matrix is presented. To avoid computational complexity and extraneous efforts of Moore-Penrose pseudoinverse, Kirchhoff index is calculated in terms of the inverse of the reduced Laplacian matrix. The notion of Laplacian matrix is then generalized using the fundamental cutset matrix of a graph. Two approaches to compute Kirchhoff index are presented: The first approach is based on a matrix transformation, and the second approach uses the concept of Kirchhoff polynomial of a graph. Kirchhoff polynomial of a graph introduced in this work is defined for each spanning tree of the graph. In 1949 and 1961 Foster established two theorems that give identities involving resistance distances. We introduce the concept of Weighted Kirchhoff index of a graph and study its relationship to Foster’s theorems. We present a generalization of Foster’s theorems that retains the circuit-theoretic flavor and elegance of Foster’s theorems, and develop a dual form of this theorem. Kirchhoff index captures the effect of topological structure on the performance of networks. It also captures the path diversity between nodes in a network. Kirchhoff index can be used to determine node betweenness in networks that are of interest in network vulnerability studies. In view of this, an efficient methodology to compute Kirchhoff index is required. For this purpose, we propose sequential and parallel algorithms. In addition, we introduce a novel 3-step approximation algorithm for calculation of resistance distance and Kirchhoff index.