<p>We present new values and bounds on the (normalised) closeness centrality <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq1.gif" Format="GIF" Height="18" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(\bar{\textsf{C}}_C\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mover accent="true"> <mrow> <mi mathvariant="sans-serif">C</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <mi>C</mi> </msub> </math></EquationSource> </InlineEquation> of connected graphs and on its product <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">\(\bar{l}\bar{\textsf{C}}_C\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mrow> <mi>l</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <msub> <mover accent="true"> <mrow> <mi mathvariant="sans-serif">C</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <mi>C</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> with the mean distance <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="10" /> </InlineMediaObject> <EquationSource Format="TEX">\(\bar{l}\)</EquationSource> <EquationSource Format="MATHML"><math> <mover accent="true"> <mrow> <mi>l</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> </math></EquationSource> </InlineEquation> of these graphs. Our main result presents the fundamental bounds <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="89" /> </InlineMediaObject> <EquationSource Format="TEX">\(1\le \bar{l}\bar{\textsf{C}}_C&lt;2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mover accent="true"> <mrow> <mi>l</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <msub> <mover accent="true"> <mrow> <mi mathvariant="sans-serif">C</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <mi>C</mi> </msub> <mo>&lt;</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. 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 <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq1.gif" Format="GIF" Height="18" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(\bar{\textsf{C}}_C\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mover accent="true"> <mrow> <mi mathvariant="sans-serif">C</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <mi>C</mi> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">\(\bar{l}\bar{\textsf{C}}_C\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mrow> <mi>l</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <msub> <mover accent="true"> <mrow> <mi mathvariant="sans-serif">C</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <mi>C</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for specific families of graphs. Elegantly and perhaps surprisingly, the asymptotic values of <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq7.gif" Format="GIF" Height="18" Rendition="HTML" Resolution="72" Type="Linedraw" Width="33" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\bar{\textsf{C}}_C\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <msub> <mover accent="true"> <mrow> <mi mathvariant="sans-serif">C</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <mi>C</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for paths <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq8.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> and ladder graphs <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq9.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(L_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>L</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> are both equal to&#xa0;<InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq10.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(\pi \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>π</mi> </math></EquationSource> </InlineEquation>, and the asymptotic limits of <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">\(\bar{l}\bar{\textsf{C}}_C\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mrow> <mi>l</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <msub> <mover accent="true"> <mrow> <mi mathvariant="sans-serif">C</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <mi>C</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for these families of graphs are both equal to&#xa0;<InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq12.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">\(\pi /3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>π</mi> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>. We conjecture that the set of values <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1921_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">\(\bar{l}\bar{\textsf{C}}_C\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mrow> <mi>l</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <msub> <mover accent="true"> <mrow> <mi mathvariant="sans-serif">C</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> <mi>C</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for all connected graphs is dense in the interval [1,&#xa0;2).</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Bounds on the Closeness Centrality of a Graph

  • Thomas Britz,
  • Xin Hu,
  • Abdellah Islam,
  • Hopein C. Tang

摘要

We present new values and bounds on the (normalised) closeness centrality \(\bar{\textsf{C}}_C\) C ¯ C of connected graphs and on its product \(\bar{l}\bar{\textsf{C}}_C\) l ¯ C ¯ C with the mean distance \(\bar{l}\) l ¯ of these graphs. Our main result presents the fundamental bounds \(1\le \bar{l}\bar{\textsf{C}}_C<2\) 1 l ¯ C ¯ C < 2 . 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\) C ¯ C and \(\bar{l}\bar{\textsf{C}}_C\) l ¯ C ¯ C for specific families of graphs. Elegantly and perhaps surprisingly, the asymptotic values of \(n\bar{\textsf{C}}_C\) n C ¯ C for paths \(P_n\) P n and ladder graphs \(L_n\) L n are both equal to  \(\pi \) π , and the asymptotic limits of \(\bar{l}\bar{\textsf{C}}_C\) l ¯ C ¯ C for these families of graphs are both equal to  \(\pi /3\) π / 3 . We conjecture that the set of values \(\bar{l}\bar{\textsf{C}}_C\) l ¯ C ¯ C for all connected graphs is dense in the interval [1, 2).