networkx/networkx — pull request #6 by conradlee (2012-04-06 12:21:45+00:00)
Title: 712 global reaching centrality

This pull request implements the global reaching centrality measure (a measure of hierarchy), as described in [ticket 712](https://networkx.lanl.gov/trac/ticket/712) in the networkx developer zone.

It includes unit tests as well.

There is one bit of code that should probably be handled more elegantly. The global reaching centrality, as originally defined, assumes that high edge weights mean high connection strength. At the same time, in the function we need to find the shortest paths between all pairs of nodes, where the shortest paths are the ones with the highest total edge weight. The shortest path finding algorithms implemented in NetworkX assume that edge weight is equivalent to path length, so the semantics are the opposite as in the case of global reaching centrality. For this reason, in the case of weighted networks, for every edge I create an attribute called "grc_lengths" which is used by Dijkstra's algorithm. This is problematic if the user happened to have already set an edge attribute called "grc_lengths"---that attribute vale will be changed (and then removed in the cleanup that takes place at the end).

We could solve this problem by working off a copy of the graph, on which we're allowed to trample on the user's edge attributes.