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

98

｜

第

6

章

三角形数 = 0

聚类系数 = 0

三角形数 = 2

聚类系数 = 0.2

三角形数 = 6

聚类系数 = 0.6

三角形数 = 10

聚类系数 = 1

CC u()

()

()

=

−

02

55 1

CC u()

()

()

=

−

22

55 1

CC u()

()

()

=

−

62

55 1

CC u()

()

()

=

−

10 2

55 1

图 6-3：节点 U 的三角形计数和聚类系数

注意，图

6-3

中的节点

U

具有

5

个关系，这使得聚类系数总是等于三角形数量的

10%

。当

改变关系数量时，情况就不同了。如果将图

6-3

中的第

2

个例子改为节点

U

只有

4

个关系

（同样有两个三角形），那么系数为

0.33

。

求取节点的聚类系数可采用如下公式：

2

()

( 1)

u

uu

R

CC u

kk

=

−

其中：

•

u

为节点；

•

R

u

是通过

u

邻节点的关系数（可借助经过

u

的三角形数得到）；

•

k

u

为

u

的度。

6.2.2

　全局聚类系数

全局聚类系数是局部聚类系数的归一化和。

聚类系数为查找像团这样明显的群组提供了一种有效方法。在团中，每个节点都与其他各

节点有关系，不过也可以指定阈值来设置级别（例如节点

40%

连通）。

6.2.3

　何时使用三角形计数和聚类系数

当需要判断群组的稳定性时，可使用三角形计数算法，也可在计算其他网络指标（如聚类

系数）时使用。三角形计数算法在社交网络分析中很流行，主要用于发现社团。

聚类系数可以反映随机选定节点的连通概率。还可以用聚类系数来快速评估特定群组或整

个网络的内聚力。将这两种算法结合使用可估计弹性和探查网络结构。