Graph center
{{Short description|Set of all vertices of minimum eccentricity}}
{{Use American English|date=March 2021}}
{{Use mdy dates|date=March 2021}}
The center (or Jordan centerWasserman, Stanley, and Faust, Katherine (1994), Social Network Analysis: Methods and Applications, page 185. Cambridge: Cambridge University Press. {{ISBN|0-521-38269-6}}) of a graph is the set of all vertices of minimum eccentricity,McHugh, James A., [http://www.cs.njit.edu/mchugh/psswrd/web-course-materials/graph-theory/alg-graph-theory-text-html/chap-1-text-v3.html Algorithmic Graph Theory] {{Webarchive|url=https://web.archive.org/web/20100801092700/http://www.cs.njit.edu/mchugh/psswrd/web-course-materials/graph-theory/alg-graph-theory-text-html/chap-1-text-v3.html |date=2010-08-01 }} that is, the set of all vertices u where the greatest distance d(u,v) to other vertices v is minimal. Equivalently, it is the set of vertices with eccentricity equal to the graph's radius.{{MathWorld | urlname=GraphCenter| title = Graph center}} Thus vertices in the center (central points) minimize the maximal distance from other points in the graph.
This is also known as the vertex 1-center problem and can be extended to the vertex k-center problem.
Finding the center of a graph is useful in facility location problems where the goal is to minimize the worst-case distance to the facility. For example, placing a hospital at a central point reduces the longest distance the ambulance has to travel.
The center can be found using the Floyd–Warshall algorithm.Floyd, Robert W. (June 1962). "Algorithm 97: Shortest Path". Communications of the ACM. 5 (6): 345 https://doi.org/10.1145/367766.368168Warshall, Stephen (January 1962). "A theorem on Boolean matrices". Journal of the ACM. 9 (1): 11–12 https://doi.org/10.1145/321105.321107 Another algorithm has been proposed based on matrix calculus.{{Cite web|url=https://hal.archives-ouvertes.fr/hal-02304090|title=A new algorithm for graph center computation and graph partitioning according to the distance to the center|date=October 2019}}
The concept of the center of a graph is related to the closeness centrality measure in social network analysis, which is the reciprocal of the mean of the distances d(A,B).