图的性质

聚类系数

$$C_i=\frac{E_i}{T_i}$$

$E_i$表示节点$i$的邻居实际存在的边的数量，$T_i$表示节点$i$的邻居可能（最多）存在的边的数量

理论溯源

聚类系数这一概念首先源于论文“Collective dynamics of ‘small-world’ networks”，主要介绍了“小世界网络”现象以及它在各种自组织系统中的应用。作者通过对网络结构的调整，发现这样的网络可以同时具有高度聚集性和短特征路径长度的特征，而这种特点在传统的规则网络或随机网络中不易出现。

小世界网络：通常将网络拓扑连接假定为完全规则或完全随机，但现实世界中的很多网络连接介于这两个极端之间，作者探索了调整这个中间度，得到的简单网络模型，这些网络具有高度聚类特征、也具有特征路径长度较小的特征。

以下是原文中关于聚类系数的定义

Suppose that a vertex v has $k_v$ neighbours；then at most $k_v(k_v-1)$ edges can exist between them (this occurs when every neighbour of v is connected to every other neighbour of v).

Let $C_v$ denote the fraction of these allowable edges that actually exist

$C_v$ reflects the extent to which friends of v are also friends of each other; and thus C measures the cliquishness（小圈子） of a typical friendship circle

其含义是，在某一个节点一跳领域内封闭三角形的比例【图片来源-参考文章1】

参考文章

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