most recent 30 from http://mathoverflow.net 2013-05-20T22:26:30Z http://mathoverflow.net/feeds/question/89376 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/89376/how-to-find-central-vertex-in-a-graph Mathsniper 2012-02-24T09:23:00Z 2012-02-26T22:35:24Z

<p>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.</p>

http://mathoverflow.net/questions/89376/how-to-find-central-vertex-in-a-graph/89377#89377 Balazs 2012-02-24T09:50:27Z 2012-02-24T09:50:27Z

<p>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: <a href="http://research.microsoft.com/en-us/people/weic/faw08_centrality.pdf" rel="nofollow">Ranking of Closeness Centrality for Large-Scale Social Networks</a>.</p>

http://mathoverflow.net/questions/89376/how-to-find-central-vertex-in-a-graph/89391#89391 Joseph O'Rourke 2012-02-24T13:07:50Z 2012-02-24T21:40:08Z

<p>Mathematica has a function <code>GraphCenter[]</code> that computes the center of a graph (the set of vertices with minimum eccentricity--exactly your definition). You can find a description in the <a href="http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphCenter.html" rel="nofollow">documentation here</a>. <br /> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/GraphCenter.jpg" alt="GridGraph" /> <br /></p>

http://mathoverflow.net/questions/89376/how-to-find-central-vertex-in-a-graph/89455#89455 Andrew D. King 2012-02-25T01:00:11Z 2012-02-25T01:00:11Z

<p>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.</p> <p>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.</p> <p><a href="http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm</a></p>

http://mathoverflow.net/questions/89376/how-to-find-central-vertex-in-a-graph/89610#89610 Aaron Meyerowitz 2012-02-26T22:35:24Z 2012-02-26T22:35:24Z

<p>The question should be more specific. It depends what you know about the graph . </p> <p>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.</p> <p>The set of centers is invariant under the automorphism group so for a vertex transitive graph every vertex is a center. </p>