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

78

｜

第

5

章

该算法的结果与原始接近中心性算法有所不同，但与改进的

Wasserman & Faust

算法的结

果相似。当处理具有多个连通分量的图时，可以使用这两种算法。

5.4

　中间中心性算法

在某些系统中，最关键的要素并不是拥有绝对权威或最高地位的要素。有时是中间人将各

个群体联系起来，或者说，中间人对资源或信息流的控制权最大。中间中心性算法检测节

点对图中信息流或资源的影响程度，通常用于查找将图的一部分与另一部分桥接的节点。

中间中心性算法计算连通图中每对节点之间的最短（加权）路径。每个节点的分值根据通

过该节点的最短路径数量确定。通过节点的最短路径数量越多，其得分就越高。

1977

年，

Linton C. Freeman

在其论文“

A Set of Measures of Centrality Based on Betweenness

”

中提出中间中心性，并将其称为“关于中心性的

3

个截然不同的直观概念”之一。

5.4.1

　桥与控制点

网络中的桥可以是节点或关系。在非常简单的图中，可以通过查找节点或关系来寻找桥。

如果删除某一节点或关系将导致图的某个部分不连通，那么该节点或关系就是桥。然而，

这种方法在典型的图中并不实用，我们采用中间中心性算法。还可以将群组视为节点，借

此度量簇的中间中心性。

如果一个节点位于另外两个节点之间的每一条最短路径上，则该节点是这两个节点的

中枢

节点

，如图

5-7

所示。

添加

关系

添加

关系

A和B的中枢节点

以深色表示

图 5-7：中枢节点位于两个节点之间的每条最短路径上。创建更多最短路径可以减少中枢节点的数量， ...