Effective Resistance Metric for Networks: Graph Formalism, Algorithms, and Granular Intuition
Haverford College. Department of Computer Science
Place of Publication
Table of Contents
This thesis builds on insufficiency of local features of networks in analyzing complex networks. It motivates the need for multi-scale metrics by extracting intuition from a physical problem of granular packings. It introduces a metric of Effective Resistance on graphs and surveys the analytical solutions and efficient algorithms to solve it. The work explores properties of the metric, bringing them back into the motivating context of granular packings. Thesis provides a description of an algorithm to compute effective resistance between every two points in the network, bounded by cubic polynomial time complexity. It then describes an algorithm to find effective resistance between two points in the network of square polynomial time complexity. It concludes with a discussion of approximate algorithms for these two tasks.