Bounds on the Closeness Centrality of a Graph

Abstract We present new values and bounds on the (normalised) closeness centrality $$\bar{\textsf{C}}_C$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mover> <mml:mrow> <mml:mi>C</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> <mml:mi>C</mml:mi> </mml:msub> </mml:math> of connected graphs and on its product $$\bar{l}\bar{\textsf{C}}_C$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mrow> <mml:mi>l</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> <mml:msub> <mml:mover> <mml:mrow> <mml:mi>C</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> <mml:mi>C</mml:mi> </mml:msub> </mml:mrow> </mml:math> with the mean distance $$\bar{l}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover> <mml:mrow> <mml:mi>l</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> </mml:math> of these graphs. Our main result presents the fundamental bounds $$1\le \bar{l}\bar{\textsf{C}}_C&lt;2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>≤</mml:mo> <mml:mover> <mml:mrow> <mml:mi>l</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> <mml:msub> <mml:mover> <mml:mrow> <mml:mi>C</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> <mml:mi>C</mml:mi> </mml:msub> <mml:mo>&lt;</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> . We prove that the lower bound is tight and that the upper bound is asymptotically tight. Combining the lower bound with known upper bounds on the mean distance, we find ten new lower bounds for the closeness centrality of graphs. We also present explicit expressions for $$\bar{\textsf{C}}_C$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mover> <mml:mrow> <mml:mi>C</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> <mml:mi>C</mml:mi> </mml:msub> </mml:math> and $$\bar{l}\bar{\textsf{C}}_C$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mrow> <mml:mi>l</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> <mml:msub> <mml:mover> <mml:mrow> <mml:mi>C</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> <mml:mi>C</mml:mi> </mml:msub> </mml:mrow> </mml:math> for specific families of graphs. Elegantly and perhaps surprisingly, the asymptotic values of $$n\bar{\textsf{C}}_C$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:msub> <mml:mover> <mml:mrow> <mml:mi>C</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> <mml:mi>C</mml:mi> </mml:msub> </mml:mrow> </mml:math> for paths $$P_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> and ladder graphs $$L_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>L</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> are both equal to $$\pi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>π</mml:mi> </mml:math> , and the asymptotic limits of $$\bar{l}\bar{\textsf{C}}_C$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mrow> <mml:mi>l</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> <mml:msub> <mml:mover> <mml:mrow> <mml:mi>C</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow> </mml:mover> <mml:mi>C</mml:mi> </mml:msub> </mml:mrow> </mml:math> for these families of graphs are both equal to $$\pi /3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>π</mml:mi> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> . We conjecture that the set of values $$\bar{l}\bar{\textsf{C}}_C$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mrow> <mml:mi>l</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>¯</mml:mo> </mml:mrow>