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

社团发现算法

｜

101

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

library coefficient

ipykernel 1.0

jupyter 0.3333333333333333

jpy-console 0.3333333333333333

six 0.3333333333333333

python-dateutil 0.3333333333333333

matplotlib 0.16666666666666666

ipykernel

的得分为

1.0

，这意味着它的所有邻节点都彼此相邻。图

6-4

清楚地展现了这一

点。这表明，直接围绕

ipykernel

形成的社团非常有内聚力。

该代码示例过滤了系数为

0

的节点，但是系数较小的节点可能也会有用。得分低可能标志

着节点为

结构洞

，即与多个社团中的节点（相互之间没有连接）都有良好连接的节点。这

也是第

5

章讨论的寻找

潜在

桥的方法。

6.3

　强连通分量算法

强连通分量算法

（

strongly connected components algorithm

，

SCC algorithm

）是最早的图算

法之一。

SCC

在一个有向图中查找连通的节点集，其中每个节点都与同一集合中其他任何

节点双向可达。该算法运行时，操作规模与节点数成正比。图

6-5

显示，

SCC

群组中的节

点并不需要直接相邻，但是在集合中的所有节点之间必须存在有向路径。

强连通分量算法

集合中的所有节点都可以双向到达其

他节点，但不必直接到达

图中的两个强连通分量以阴影表示：

{A, B}和{C, D, E}

注意，在{C, D, E}中，每个节点都可 ...