聚类系数

图论中，聚集系数用于衡量节点聚集的程度。 有证据表明，大多数现实世界的网络中，特别是在社交网络中，节点倾向于创建相对紧密联系的群体; 这种可能性往往大于在两个节点之间随机建立关系的平均概率(Holland 和 Leinhardt，1971; Watts 和 Strogatz，1998 )。

全局聚集系数

全局集聚系数以节点三重性（triplets）为基础。 一个三元组是由两个(开三元组)或三个(闭三元组)无向联系相连接的三个节点。 因此，一个三角形图包括三个闭合的三联体，每个节点中心为一个(注意，这意味着三角形中的三联体来自节点的重叠选择)。 全局集聚系数是三联体总数除以闭合三联体(或3 x 三角形)的个数。 Luce和Perry(1949年)第一次尝试对其进行测量。 这个度量概括了整个网络(全局)中的集群，并可应用于无向和有向网络(通常称为传递性，见 Wasserman 和 Faust，1994，第243页。 全局集聚系数的定义是:

[math]\displaystyle{ C = \frac{\mbox{number of closed triplets}}{\mbox{number of all triplets (open and closed)}} }[/math].

闭合三联体的数目在文献中也被称为3×三角形，所以:

[math]\displaystyle{ C = \frac{3\times (\mbox{number of triangles)}}{\mbox{number of all triplets}} }[/math].

Opsahl 和 Panzarasa (2009)提出了加权网络的一般化，和一种双模式网络(包括二进制和加权)。

局部聚集系数

图中某顶点(节点)的局部集聚系数量化了其邻居节点相互聚集构成团(完全图)的程度。邓肯·沃茨 Duncan J. Watts和史蒂文·斯特罗加兹 Steven Strogatz在1998年引入该测量方法来确定一个图是否构成小世界网络。

一个图 G=(V,E)，形式上由一组节点和节点之间的连边组成。 边连接节点。一个节点[math]\displaystyle{ v_{i} }[/math] 的邻域[math]\displaystyle{ N_{i} }[/math]被定义为其紧邻的节点，具体如下:

[math]\displaystyle{ N_{i}=\{v_{j}:e_{ij}\in E\lor e_{ji}\in E\}. }[/math]

我们将 [math]\displaystyle{ k_{i} }[/math]定义为节点的个数，|[math]\displaystyle{ N_{i} }[/math]| 为邻域，[math]\displaystyle{ N_{i} }[/math]为邻域节点数目。

一个节点[math]\displaystyle{ v_{i} }[/math]的局部集聚系数[math]\displaystyle{ C_{i} }[/math]由邻域内节点之间的连边除以它们之间可能存在的连边数量的比例给出。 对于有向图，[math]\displaystyle{ e_{ij} }[/math]不同于[math]\displaystyle{ e_{ji} }[/math] ，因此对于每个邻域[math]\displaystyle{ N_{i} }[/math] ，邻域内的节点之间可能存在[math]\displaystyle{ k_{i}(k_{i}-1) }[/math]链([math]\displaystyle{ k_{i} }[/math]是一个顶点的邻域数)。 因此，有向图的局部集聚系数为

[math]\displaystyle{ C_i = \frac{|\{e_{jk}: v_j,v_k \in N_i, e_{jk} \in E\}|}{k_i(k_i-1)}. }[/math]

无向图的[math]\displaystyle{ e_{ij} }[/math]和[math]\displaystyle{ e_{ji} }[/math]被认为具有相同的性质。 因此，如果一个顶点有[math]\displaystyle{ v_{i} }[/math]邻域， [math]\displaystyle{ k_i }[/math]边可以存在于邻域内的顶点之间。因此，无向图的局部集聚系数可以定义为

[math]\displaystyle{ C_i = \frac{2|\{e_{jk}: v_j,v_k \in N_i, e_{jk} \in E\}|}{k_i(k_i-1)}. }[/math]

设[math]\displaystyle{ \lambda_G{(v)} }[/math]是无向图[math]\displaystyle{ G }[/math]上的三角形个数[math]\displaystyle{ v \in V(G) }[/math]。 也就是说，[math]\displaystyle{ \lambda_G{(v)} }[/math]是 [math]\displaystyle{ G }[/math]的3条边和3个节点的子图的个数，其中一个是[math]\displaystyle{ v }[/math]。 设[math]\displaystyle{ \tau_G{(v)} }[/math]是[math]\displaystyle{ v \in V(G) }[/math]上的三倍数。 即，[math]\displaystyle{ \tau_G{(v)} }[/math]具有2条边和3个顶点的子图(不一定是诱导的)的个数，其中一条边与两条边相关。 那么我们也可以将集聚系数定义为

[math]\displaystyle{ C_{i} = \frac{\lambda_G{(v)}}{\tau_G{(v)}}. }[/math]

易证明前面的两个定义是相同的，因为

[math]\displaystyle{ \tau_G(v) = C({k_i},2) = \frac{1}{2}k_i(k_i-1). }[/math]

如果所连接的每个邻居也连接到邻近的每个其他节点[math]\displaystyle{ v_{i} }[/math]，则这些测量值为1; 如果没有任何节点[math]\displaystyle{ v_{i} }[/math]连接到所连接的任何其他节点[math]\displaystyle{ v_{i} }[/math]，则这些测量值为0。

网络整体聚类水平

作为全局聚类集聚系数的代替，Watts 和 Strogatz 将所有顶点局部聚类系数的平均值作为网络整体聚类水平[math]\displaystyle{ n }[/math] :

[math]\displaystyle{ \bar{C} = \frac{1}{n}\sum_{i=1}^{n} C_i. }[/math]

值得注意的是，该度量将更多权重放在低度节点上，而传递性比率将更多权重放在高度节点上。 事实上，每个局部聚类分数由[math]\displaystyle{ k_{i}(k_{i}-1) }[/math]的加权平均数模型与全局聚类集聚系数模型是相同的。 如果图有一个小的平均最短路径长度与网络中节点数量的自然对数[math]\displaystyle{ \ ln{{N}} }[/math]一起延展，那么这个图被认为是小世界。 例如，随机图是小世界图，而格子图不是，无标度图通常被认为是超小世界图，因为它们的平均最短路径长度随[math]\displaystyle{ \ln{\ln{N}} }[/math]延展。Barrat 等人提出了广义的加权网络(2004) ，，Latapy 等人(2008)和 Opsahl (2009).<>重新定义了二部图(也称为双模网络)

Fagiolo (2007) , Clemente 和Grassi (2018) 提出了另一种加权有向图网络的推广概念。默认情况下，这个公式不适用于具有孤立顶点的图; 参见 Kaiser (2008)和 Barmpoutis 等 . 具有最大可能平均集聚系数的网络被发现具有模块结构，且不同节点之间存在尽可能小的平均距离。

编者推荐

---

本中文词条由Gravity PHY参与编译，苏格兰审校，薄荷编辑，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。