Generalizing Kirchhoff Laws for Signed Graphs

Overview

Signed graphs are commonly used in social networks to model relationships, and Kirchhoff-type conservation laws can be applied to signed networks to simulate the diffusion of information or emotion. By analyzing Kirchhoff-laws on signed graphs, we can better understand stability in social networks and ways to balance social networks to be conservative or have less energy loss. It has been proven by William T. Tutte that all unsigned graphs are Kirchhoff-law conservative. The central question of this project is whether signed graphs can be Kirchhoff-law conservative and under what specific conditions. This project generalizes transpedances through an incidence-oriented structure of bidirected graphs called a contributor. These contributor-based transpedances are proven to be equivalent to Tutte’s classical 2-arborescence interpretation when applied to unsigned graphs and provide novel results on Kirchhoff-conservativity for signed graphs. It is also proven in this project that signed graphs are globally conservative when all edges are positively signed and locally conservative when the only negative edge is between the source and the sink. It is conjectured that signed graphs are Kirchhoff-law globally conservative if and only if all edges are positively signed. This project also shows that contributors possess a unique source-sink path property and that there exists a matching between contributors on adjacent edges. The new contributor-based transpedance agrees with prior work on unsigned graphs and provides a novel interpretation for signed graphs, giving new insights into balancing signed graphs and social networks.

Competition history

• ISEF 2021 Mathematics · Entry MATH037

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.