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

68

｜

第

5

章

LOAD CSV

WITH

HEADERS FROM uri

AS

row

MATCH

(source:User {id: row.src})

MATCH

(destination:User {id: row.dst})

MERGE (source)-[:FOLLOWS]->(destination)

图已经加载完毕，接下来介绍算法。

5.2

　度中心性算法

度中心性算法是本书中最简单的算法。它计算节点的输入关系数和输出关系数，用于在图

中查找受欢迎的节点。该算法是

1979

年由

Linton C. Freeman

在其论文“

Centrality in Social

Networks: Conceptual Clarification

”中提出的。

5.2.1

　可达性

了解节点的可达性是一种相当重要的度量方法。节点的

度

是其拥有的直接关系数，可按入

度和出度两种指标计算。可以将其视为节点的直接可达度，例如在一个活跃的社交网络

中，度较高的人会有很多直接联系人，更有可能在该网络中传播流感病毒。

网络的

平均度

就是关系总数除以节点总数得到的值，这个值可能会被度较高的节点严重扭

曲。

度分布

是指随机选择的节点拥有特定关系数的概率。

图

5-3

展示了某在线论坛各主题之间实际连接分布的差异。如果简单地取平均值，就会以

为大多数主题有

10

个连接，而实际上大多数主题只有两个连接。

连接数量（度）

大多数主题有两个连接

但是平均度为10

图 5-3：Jacob Silterrapa 绘制的度分布图给出了一个示例，说明平均值往往不能反映网络的实际分 ...