图论中的聚类系数(Clustering coefficient)简单介绍

这篇具有很好参考价值的文章主要介绍了图论中的聚类系数(Clustering coefficient)简单介绍。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

在GraphSage论文的理论分析部分，涉及到一个概念叫做“Clustering coefficient”，直译过来就是聚类系数，解释为“节点的一跳邻域内封闭的三角形的比例”，本文对其做一个简单的介绍。本文参考了 Wiki百科-Clustering coefficient。

更：关于GraphSage论文详解，请参见博文《GraphSage-《Inductive Representation Learning on Large Graphs》论文详解》

在图论中，聚类系数是图中节点倾向于聚类在一起的程度的度量。相关论文表明¹²，在大多数现实世界的网络中，尤其是社交网络中，节点倾向于创建紧密结合的群体，其特征是联系密度相对较高；这种可能性往往大于两个节点之间随机建立联系的平均概率。

聚类系数主要有两种度量方式：局部和全局。

一个节点的局部聚类系数量化了它的邻居节点离成为团(clique，即每两个不同的顶点都是相邻的。参见wiki百科-clique)有多近，简单来说就是，节点的一跳邻域内封闭的三角形的比例。

举个例子说明：
图论中的聚类系数(Clustering coefficient)简单介绍

图1 无向图上的局部聚类系数计算示例

图中的灰色线表示节点A与邻居的连接，黑实线是邻居之间的连接，红色表示图1(2)和(3)相比于图1(1)去掉的连接。
节点 A 的局部聚类系数计算为：其邻居之间实际实现的连接与所有可能连接的数量的比例，或者为节点A的一跳邻居内封闭的三角形的比例。

邻居之间实际实现的连接与所有可能连接的数量的比例： 如图1所示，A的邻居为(P1,P2,P3)，P1,P2,P3之间最多可以有3个连接，图1中的(1)(2)(3)的P1,P2,P3之间分别有3个,1个和0个连接，所以聚类系数 $C$ 分别为 1,1/3和0。
邻居内封闭的三角形的比例： 如图1所示，A的邻居为(P1,P2,P3)与A最多形成3个三角形： $\Delta AP_1P_2$ , $\Delta AP_2P_3$ , $\Delta P_1P_2P_3$ ，图1中的(1)(2)(3)符合条件的三角形分别有3个,1个和0个，所以聚类系数 $C$ 分别为 1,1/3和0。

全局聚类系数是封闭三元组（或3个三角形）在三元组（开放和封闭）总数上的数量。

这部分待更新…

P. W. Holland & S. Leinhardt (1971). “Transitivity in structural models of small groups”. Comparative Group Studies. 2 (2): 107–124. doi:10.1177/104649647100200201. S2CID 145544488 ↩︎
D. J. Watts & Steven Strogatz (June 1998). “Collective dynamics of ‘small-world’ networks”. Nature. 393 (6684): 440–442. Bibcode:1998Natur.393…440W ↩︎文章来源地址https://www.toymoban.com/news/detail-406949.html

到了这里，关于图论中的聚类系数(Clustering coefficient)简单介绍的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！