论文标题
图形的亲密核心界限
Bounds on the closeness centrality of a graph
论文作者
论文摘要
我们在（归一化的）紧密度中心性$ \ bar {\ mathsf {c}} _ c $连接的图和其产品$ \ bar {l} \ bar {\ mathsf {c}} _ c $带有这些图的平均距离$ \ \ bar {l} $。我们的主要结果介绍了基本范围$ 1 \ leq \ bar {l} \ bar {\ mathsf {c}} _ c <2 $。下界紧密，上限渐近地紧密。将下限与平均距离上的已知上限结合在一起，我们发现了十个新的下限图，以实现图的紧密度。我们还提供了$ \ bar {\ mathsf {c}} _ c $和$ \ bar {l} \ bar {\ Mathsf {c}} _ c $的明确表达。优雅而令人惊讶的是，渐近价值$ n \ bar {\ mathsf {c}} _ c \ big（p_n \ big）$和$ n \ bar {\ mathsf {c}}} _ c \ big（l_n \ big） $ \ bar {l} \ bar {\ mathsf {c}} _ c $对于这些图形家族都等于$π/3 $。我们认为，所有连接图的值$ \ bar {l} \ bar {\ Mathsf {c}} _ c $在间隔$ [1,2）$中密集。
We present new values and bounds on the (normalised) closeness centrality $\bar{\mathsf{C}}_C$ of connected graphs and on its product $\bar{l}\bar{\mathsf{C}}_C$ with the mean distance $\bar{l}$ of these graphs. Our main result presents the fundamental bounds $1\leq \bar{l}\bar{\mathsf{C}}_C<2$. The lower bound is tight and 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{\mathsf{C}}_C$ and $\bar{l}\bar{\mathsf{C}}_C$ for specific families of graphs. Elegantly and perhaps surprisingly, the asymptotic values $n\bar{\mathsf{C}}_C\big(P_n\big)$ and of $n\bar{\mathsf{C}}_C\big(L_n\big)$ both equal $π$, and the asymptotic limits of $\bar{l}\bar{\mathsf{C}}_C$ for these families of graphs are both equal to $π/3$. We conjecture that the set of values $\bar{l}\bar{\mathsf{C}}_C$ for all connected graphs is dense in the interval $[1,2)$.
