调和中心性

概述

调和中心性（Harmonic Centrality）是接近中心性的变种。调和中心性提出的平均最短距离能够处理非连通图中会出现的无限值。调和中心性算法首先是由M. Marchiori和V. Latora于2000年提出的，然后由A. Dekker和Y. Rochat分别于2005年和2009年提出：

• M. Marchiori, V. Latora, Harmony in the Small-World (2000)
• A. Dekker, Conceptual Distance in Social Network Analysis (2005)
• Y. Rochat, Closeness Centrality Extended to Unconnected Graphs: The Harmonic Centrality Index (2009)

调和中心性的取值范围是0到1，节点的分值越大，距离其他节点越近。

基本概念

最短距离

两个点之间的最短距离是指它们之间最短路径的边数。具体可参看接近中心性。

调和平均数

调和平均数（Harmonic Mean）是平均数的一种，它是变量倒数的算术平均数的倒数。算数平均数A和调和平均数H的计算公式如下：

调和平均数应用的经典场景是以不同的速度通过相同的距离时，求平均速度。假设有一个往返行程，去程速度为30 km/h，回程速度为10 km/h，整个行程的平均速度是多少？

这种情况下，直接使用算数平均数A = (30+10)/2 = 20 km/h计算不太合理。由于去程行驶时间少，回程行驶时间多，整个行程大部分时间的速度是10 km/h，因而平均速度应该更接近于10 km/h 才对。

假设单程距离为1，考虑行驶时间而计算的平均值为2/(1/30+1/10) = 15 km/h，这就是调和平均数，它根据每段距离所花费的时间进行了调整。

调和中心性

在本算法中，节点的调和中心性分值等于该点与其他各节点的最短距离调和平均值的倒数。计算公式为：

其中，x为待计算的目标节点，y为图中除 x以外的所有节点，k-1为y的个数，d(x,y)为x到y的最短距离，当x与y不连通时，d(i,j) = +∞，则有1/d(i,j) = 0。

上图中点a的调和中心性为(1 + 1/2 + 1/+∞ + 1/+∞) / 4 = 0.375，点d的调和中心性为(1/+∞ + 1/+∞ + 1/+∞ + 1) / 4 = 0.25。

调和中心性算法会消耗很多计算资源。在一个有V个节点的图中，建议当V>10000 时通过采样进行近似计算，推荐的采样个数是节点数以10为底的对数（log(V)）。

每次执行算法时，只进行一次采样，每个节点的中心性分值是基于该节点到所有样本节点的最短距离计算的。

特殊说明

• 孤点的调和中心性分值为0。

语法

• 命令：algo(harmonic_centrality)
• 参数：

示例

示例图如下：

文件回写

algo(harmonic_centrality).params().write({
  file:{ 
    filename: 'centrality'
  }
})

结果：文件centrality

LH,0
LG,0.142857
LF,0.142857
LE,0.357143
LD,0.357143
LC,0.428571
LB,0.428571
LA,0.571429

属性回写

algo(harmonic_centrality).params().write({
  db:{ 
    property: 'hc'
  }
})

结果：每个节点的中心性分值回写至名为hc的点属性下

直接返回

algo(harmonic_centrality).params({
  direction: 'out',
  order: 'desc',
  limit: 3
}) as hc
return hc

结果：hc

流式返回

algo(harmonic_centrality).params({
  direction: 'in'
}).stream() as hc
where hc.centrality == 0
return hc

结果：hc