Welcome to MathOverflow

Question

3

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.

flag	asked Feb 24 2012 at 9:23 Mathsniper 39●3

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 2012 at 22:15

Joseph O'Rourke · Answer 1 · 2012-02-24 21:40:08Z UTC

3

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

edited Feb 24 2012 at 21:40

answered Feb 24 2012 at 13:07

Joseph O'Rourke
43.3k●1●49●214

Andrew D. King · Answer 2 · 2012-02-25 01:00:11Z UTC

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

Balazs · Answer 3 · 2012-02-24 09:50:27Z UTC

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.

Aaron Meyerowitz · Answer 4 · 2012-02-26 22:35:24Z UTC

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.

How to find central vertex in a graph?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

4 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.