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

64

第 5 章

中心性算法

中心性算法用于理解图中特定节点的作用及其对网络的影响。这些算法很有用，因为它们

可以识别最重要的节点，帮助我们了解群组动态，例如可信度、可访问性、事物的传播速

度以及群组之间的“桥梁”等。尽管其中许多算法是为社交网络分析而发明的，但在其他

很多行业和领域中也有应用。

本章将介绍以下算法。

•

度中心性算法，可作为连通度的基准指标。

•

接近中心性算法，用于度量节点在群组中的中心程度，包括两种针对不连通群组的变体。

•

中间中心性算法

1

，用于寻找控制点，包括一种近似的替代方法。

• PageRank

算法，用于了解总体影响，包括流行的个性化选项。

度量内容不同，中心性算法产生的结果也会显著不同。如果结果不理想，就

应检查所用算法是否与其设计初衷一致。

本章将解释这些算法的工作原理，并给出

Spark

示例及

Neo4j

示例。如果算法在其中一个

平台上不可用或者差异不明显，则仅提供一个平台的示例。

图

5-1

展示了中心性算法所针对的各种问题之间的区别，表

5-1

是每种算法及其示范用例

的速查表。

注

1

：

Betweenness Centrality

，也译作中介中心性算法。——译者注

中心性算法

｜

65

度中心性算法

节点的连接数量有多少？

节点A的度最高

接近中心性算法

在图或子图中，哪个节点

更容易到达其他各节点？ ...