I’ve been revisiting some network analysis and am finding some unexpected relationships between edge betweenness and node betweenness (my graph has 458 nodes and 14433). The unexpected relationship is this: the edge in the graph with the greatest betweenness (316) connects one node with a betweenness of 673 out of 1491 and a node with 0 out of 1491. I would have expected the edge with the greatest betweenness would connect the node with the greatest betweenness (1491) to the connected node with the greatest betweenness (1081) relative to other connected nodes; however, that edge only measures 65 out of 316. It doesn’t seem possible that an edge with the max betweenness could connect to a node with betweenness of 0. The only explanation I can think of is that due to redundancy in the graph/network, betweenness is inflated to terminal nodes (leaves) when compared to non-terminal nodes. Has anyone seen anything like this before and is there some logical explanation I’m overlooking?
It doesn’t seem impossible to get such results. For example if you take a full graph, and then add one new node A and connect it only to node B (just some random node in the full graph). Then node B will have a huge betweenness, edge A → B will have a huge betweenness, but A will have 0 betweenness.
@GroteGnoom, thank you for that succinct explanation. So, if you were to rank edges by their importance to maintaning network connectivity overall, could you use betweenness in a way that would not prioritize the aforementioned connections to leaf nodes (as it would seem the loss of such an edge is less impactful to the overall network)? Would you use some other metric that combines centrality measures (say, that considers both node and edge betweenness)? Perhaps betweenness of only those edges retained within the MST?
I am really not an expert in this field, but are you sure edge betweenness isn’t a reasonable measure? In my example A → B really seems like the most important edge, because if you cut it, everyone is cut off from A, while lots of other edges can be cut with a far smaller influence.
If you have two full-graph communities with a single link in between that link should have a higher edge betweenness than a leaf node added to one of those communities. This also seems like a reasonable result: leafs don’t always win.
Still, there could be some way better measures for your use case out there.