Effective Resistance Metric for Networks: Graph Formalism, Algorithms, and Granular Intuition
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Advisor
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Dark Archive
Terms of Use
Tripod URL
Identifier
Abstract
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.