bridges function?

[mpadge]

https://www.geeksforgeeks.org/bridge-in-a-graph/ @Robinlovelace would this be useful for you? Pretty easy to implement straight from the code linked there. Plus the point-based version at https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

[Robinlovelace]

Probably not in that formal definition because there are usually multiple bridges. The question is how far they are apart and if building a new bridge would be worth the investment. Finding 'pinch points' would be useful but that can come from centrality I believe.

[mpadge]

Yeah, right ... thinking about pinch points made me realise that the algorithms linked above could be adapted to extract measures of change in network centrality as individual edges are dropped. Those changes won't necessarily be related to centrality as such, and are really what you want to quantify how much an edge represents a pinch point. And the algorithm could be adapted to track the effect of dropping a series of edges in one sweep of the path algorithm, so would be super-efficient.

It would be theoretically possible to analyse all edges at once, but that would require storing an entire N-by-N matrix in memory, which is generally not feasible. What should be possible would be:

1. Initial centrality calculation, and use that to prioritise some number M << N of edges (like 100, or 1,000)
2. Submit those edges to a second query to aggregate centrality values in the absence of each into a single N-by-M matrix.

The sum of squared differences of each matrix row to neutral centrality would then tell you the "pinch point" effect of each edge. I'll definitely implement that at some stage, but let me know if this'd be helpful in the nearer term, and i'll happily prioritise it. 🚀