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.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ 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? $\endgroup$– Gerry MyersonCommented Feb 24, 2012 at 22:15
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
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.
https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
answered Feb 25, 2012 at 1:00
$\begingroup$
$\endgroup$
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.
answered Feb 24, 2012 at 13:07
$\begingroup$
$\endgroup$
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.
answered Feb 26, 2012 at 22:35
$\begingroup$
$\endgroup$
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).
$\begingroup$
$\endgroup$
Depends on what means central. There are a lot of centrality measures heuristically inspired in different centrality/importance/relevant meanings.
I recommend the following paper: https://www.nature.com/articles/srep17095?WT.ec_id=SREP-639-20151201&spMailingID=50145293&spUserID=MzcwNDE0MDA3NzMS1&spJobID=820120429&spReportId=ODIwMTIwNDI5S0
answered Dec 28, 2018 at 13:58