Return to Revisions

I am not sure your definition of centrality is the most useful one; in what's called "network science", the study of large-scale graphs, I think some measure of centrality which takes an average rather than a maximum will be more useful. Think for example about a graph which has a vertex $v$, edges $v- v_i$ to lots of vertices $v_1, ...,v_N$, and also contains a chain of length say three, $v - w_1 - w_2 - w_3$. According to your definition, $w_1$ is the center of this graph, but I would say it's $v$. The average distance leads to what's called "closeness centrality". There is also "betweenness centrality", based on the number of shortest paths in the graph that pass through the node divided by the total number of shortest paths; this is trying to measure how useful $v$ is to the rest of the graph. Googling these two phrases will bring up lots of algorithms and further references. Here is a random recent one that seems to have a useful intro: Ranking of Closeness Centrality for Large-Scale Social Networks (Wayback Machine).