数据分析之图算法: 基于Spark和Neo4j

中心性算法

｜

77

5.3.5

　接近中心性算法变体

：

调和中心性算法

调和中心性（

Harmonic Centrality

，也称

Valued Centrality

）算法是接近中心性算法的一种

变体，是为了解决非连通图的固有问题而发明的。在“

Harmony in a Small World

”这篇论

文中，

Massimo Marchiori

和

Vito Latora

将此概念作为平均最短路径的实际表示形式。

在计算每个节点的亲密度分值时，并不是累加一个节点到其他各节点的距离，而是将这些

距离的倒数相加，这意味着∞值变得无关紧要了。

原始的节点调和中心性计算公式如下：

1

1

1

()

(,)

n

v

Hu

duv

−

=

=

∑

其中：

•

u

是节点；

•

n

是图中的节点数；

•

d

(

u

,

v

)

是另一节点

v

到

u

的最短距离。

对于接近中心性，也可以用以下公式计算归一化调和中心性得分：

1

1

1

(,)

()

1

n

v

norm

duv

H

u

n

−

=

=

−

∑

在该公式中，∞值得到妥善处理。

使用

Neo4j

实现调和中心性算法

下述查询执行调和中心性算法：

CALL algo.closeness.harmonic.stream("User", "FOLLOWS")

YIELD nodeId, centrality

RETURN

algo.getNodeById(nodeId).id

AS

user, centrality

ORDER BY

centrality

DESC

运行该程序，结果如下所示：

user centrality

Alice 0.625

Doug 0.625