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

82

｜

第

5

章

Jason

的得分最高，这是因为两组用户通过他实现交流。可以把

Jason

视为这两组用户之间

的

局部桥

，如图

5-10

所示。

图 5-10：Jason 的中间中心性可视化

在继续介绍之前，先删除

Jason

及其关系以重置图。

MATCH

(user:User {id: "Jason"})

DETACH

DELETE

user

5.4.5

　中间中心性算法变体

：

RA-Brandes

算法

回想一下，要在大型图上准确计算中间中心性得分，代价非常高。因此，可以选用一种运

行速度快得多但仍然可以提供有用（尽管不精确）信息的近似算法。

RA-Brandes

算法是近似计算中间中心性得分的著名算法。它只考虑节点的一个子集，而不

计算每对节点之间的最短路径。选择节点子集的两种常见策略如下。



随机方式

均匀、随机选取节点，选取概率确定。默认概率为

10

2

log ( )

e

N

。如果概率为

1

，则算法与

常规中间中心性算法一样，要加载全部节点。



度方式

随机选取节点，但自动排除那些度低于平均值的节点（只有具有大量关系的节点才有可

能被访问）。

要进一步优化，还可以限制最短路径算法的深度，使之提供全部最短路径的一个子集。