概述
调和中心性(Harmonic Centrality)算法是接近中心性算法的变种。接近中心性衡量的是节点在其连通分量中到其它各点的平均最短距离,显然在不连通图中就无法体现节点在全图的中心性;调和中心性提出的“平均最短距离”则是对这些最短距离的倒数求和,这使它可以处理非连通图中会出现的无限值。调和中心性算法首先是由 M. Marchiori 和 V. Latora 于 2000 年提出的,然后由 A. Dekker 和 Y. Rochat 分别于 2005 年和 2009 年提出。
调和中心性的取值范围是 [0,1],数值越大中心性越大。
算法的相关资料如下:
- 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)
基本概念
最短距离
最短距离是指两个点之间的最短路径的边数。具体可参看章节《接近中心性》。
调和平均数
调和平均数(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
,这就是调和平均数,这才是真正的平均速度,它根据每段距离所花费的时间进行了调整。
调和中心性
节点的调和中心性定义为该点到图中其他所有点的最短距离的调和平均数的倒数:
其中,i
为待计算节点,j
为图中除 i
以外的所有节点,n-1
为 j
的个数,d(i,j)
为 i
到 j
的最短距离,当 i
、j
之间没有边相连时,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
。
由于需要计算全图从某个点出发的所有最短路径,调和中心性算法会消耗较多的计算资源。在进行调和中心性的计算时,可对点的数量大于 10,000 的图集进行采样计算,建议采样个数为以 10 为底的对数
log(点数量)
;可通过配置项决定是否采样。
特殊处理
孤点、不连通图
节点的调和中心性是考虑了全图节点——包括孤点与不同连通分量内的节点——的结果。
自环边
调和中心性计算的是节点之间的最短距离,自环边不构成最短路径,因此不参与计算。
有向边
在不规定边的方向时计算调和中心性,边的方向将被忽略。此时图中的所有节点都参与计算。
结果和统计值
以下面包含 8 个节点的图为例,针对所有节点运行调和中心性算法:
算法结果:忽略边的方向,计算每个点的调和中心性,根据算法执行方式,返回 _id
、centrality
两列或 _uuid
、centrality
两列
_uuid | _id | centrality |
---|---|---|
1 | LA | 0.5714286 |
2 | LB | 0.4285714 |
3 | LC | 0.4285714 |
4 | LD | 0.3571429 |
5 | LE | 0.3571429 |
6 | LF | 0.1428571 |
7 | LG | 0.1428571 |
8 | LH | 0.0000000 |
算法统计值:无
命令和参数配置
- 命令:
algo(harmonic_centrality)
params()
参数配置项如下:
名称 |
类型 |
默认值 |
规范 |
描述 |
---|---|---|---|---|
ids 或 uuids | []_id 或 []_uuid |
/ | / | 待计算节点的 ID 或 UUID,指定点后 sample_size 设置无效;忽略表示计算全部点,此时 sample_size 设置有效 |
direction | string | / | in/out,大小写不敏感 | 路径中边的方向;忽略表示忽略方向 |
sample_size | int | -1 | -1,-2 或 (0,节点总数] | 随机采样的点个数,-1 表示采样 log(<全图点数量>) 个点进行计算,-2 或忽略表示不采样,用所有点进行精确计算 |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
order | string | / | ASC 或 DESC,大小写不敏感 | 对返回结果进行排序,忽略表示不排序 |
示例:计算点 UUID = 1,2,3,4 的调和中心性
algo(harmonic_centrality).params({
uuids: [1,2,3,4]
}).stream() as centrality
return centrality
示例:采样计算全图点的出方向调和中心性,返回 5 条结果
algo(harmonic_centrality).params({
limit: 5,
direction: "out",
sample_size: -1
}) as out
return out
算法执行
任务回写
1. 文件回写
配置项 | 各列数据 |
---|---|
filename | _id ,centrality |
示例:计算所有点的调和中心性,将算法结果回写至名为 centrality 的文件
algo(harmonic_centrality).params().write({
file:{
filename: "centrality"
}
})
2. 属性回写
配置项 | 回写内容 | 类型 | 数据类型 |
---|---|---|---|
property | centrality |
点属性 | float |
示例:计算所有点的调和中心性,将调和中心性回写至名为 hc 的点属性
algo(harmonic_centrality).params().write({
db:{
property: "hc"
}
})
3. 统计回写
算法无统计值。
直接返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其调和中心性 | _uuid , centrality |
示例:计算所有点的调和中心性,将算法结果定义为别名 results 并返回中心性最大的三个结果
algo(harmonic_centrality).params({
order: "desc",
limit: 3
}) as results
return results
流式返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其调和中心性 | _uuid , centrality |
示例:计算所有点的调和中心性,将算法结果定义为别名 results,返回中心性为 0 的结果
algo(harmonic_centrality).params().stream() as results
where results.centrality == 0
return results
实时统计
算法无统计值。