Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am learning graph theory and some concept that I cannot figure it out. A vertex is central in $G$ if its greatest distance from any other vertex is as small as possible. Is there any algorithm to find central vertex in any given graph $G$? Thanks.

share|improve this question
    
At the risk of stating the obvious, of course there is an algorithm (assuming $G$ is finite). For each vertex $v$, find its distance to each other vertex; for each vertex $v$, look at the numbers you've worked out and see which one is largest; look at this list of largest numbers, and see which ones are smallest. Perhaps you wanted to ask what the most efficient algorithm is? –  Gerry Myerson Feb 24 '12 at 22:15

4 Answers 4

The question should be more specific. It depends what you know about the graph .

For a tree you can erase all degree 1 vertices then repeat on the new graph and stop when there are just one or two.

The set of centers is invariant under the automorphism group so for a vertex transitive graph every vertex is a center.

share|improve this answer

To state more directly what Joseph said, if we know the distance between any two vertices, it is straightforward to first find the eccentricity of $v$, i.e. the maximum distance from $v$ to another vertex. Having done this we simply mark the vertices of lowest eccentricity as being central.

To find the distance between every pair of vertices, one can apply the Floyd-Warshall algorithm for all-pairs shortest path, which runs in $O(n^3)$ time.

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

share|improve this answer

Mathematica has a function GraphCenter[] that computes the center of a graph (the set of vertices with minimum eccentricity--exactly your definition). You can find a description in the documentation here.
          GridGraph

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.