Curvature on Graphs With Negative Edge Weights

Discrete notions of curvature have yielded important insights into the fragility of networks, including financial, gene regulatory, and social networks. These quantitative measures help identify critical nodes and pathways whose failure may cause disruption to the networkś overall functionality. One such measure, the Ollivier-Ricci (OR) curvature, which is the focus of this paper, extends this inherently geometric concept into the setting of graphs by evaluation via the cost of transporting node distributions. However, a previously unstudied and salient feature of graphs is that links between nodes may reflect more than a spatial separation - links may be inhibitory or antagonistic, a quality that is not captured in the geometry of continuous spaces. To this end, we present the notions of a balanced graph and of graph frustration, to capture antagonistic effects of signed edge weights modeling promotion (+) or inhibition (-); a balanced graph is one where every cycle has an even number of negative edge weights, and frustration quantifies the degree of deviation from a balanced graph. Based on these concepts, we introduce modified Ollivier-Ricci-inspired fragility indices that point to pathways that magnify frustration in unbalanced graphs. We study two types of networks, gene regulatory and social networks, to demonstrate the utility of the fragility indices to impede or enhance functionality with respect to graph frustration. Our results demonstrate that, indeed, these new indices better identify critical edges, as quantified by several global measures, than other commonly used indices.