集聚系数

在图论中，集聚系数（也称群聚系数、集群系数）是用来描述一个图中的顶点之间结集成团的程度的系数。具体来说，是一个点的邻接点之间相互连接的程度。例如生活社交网络中，你的朋友之间相互认识的程度^[1]。有证据表明，在各类反映真实世界的网络结构，特别是社交网络结构中，各个结点之间倾向于形成密度相对较高的网群^[2][3]。也就是说，相对于在两个节点之间随机连接而得到的网络，真实世界网络的集聚系数更高。

集聚系数分为整体与局部两种。整体集聚系数可以给出一个图中整体的集聚程度的评估，而局部集聚系数则可以测量图中每一个结点附近的集聚程度。

基础概念

集聚系数主要是描述图（或者称为网络）的特性。一个图 G 是由一些顶点 V 和顶点与顶点之间的一些连线（称为边）E 构成。两个相连的顶点也称为邻接点。比如在一群人中，将每个人用一个点表示，如果两人之间认识，就将对应的两点连起来。这样就构成了一个图。有的图是有方向的，比如在同样一群人中，如果一人甲欠另一人乙的钱，就连一条从 甲至乙的线，这样就构成了一个有向图。

整体集聚系数

整体集聚系数的定义建立在闭三点组（邻近三点组）之上。假设图中有一部分点是两两相连的，那么可以找出很多个“三角形”，其对应的三点两两相连，称为闭三点组。除此以外还有开三点组，也就是之间连有两条边的三点（缺一条边的三角形）。这两种三点组构成了所有的连通三点组。整体集聚系数定义为一个图中所有闭三点组的数量与所有连通三点组（无论开还是闭）的总量之比（也有定义为这个值的三倍，使得在完全图中的整体集聚系数等于1）。最早尝试测量这个系数是在1949年罗伯特·邓肯·路斯和阿尔伯特·D·佩里合作的一篇论文中^[4]。

假设有图${\displaystyle G=(V,E)}$，其中${\displaystyle V=\left\{v_{1},v_{2},\cdots ,v_{n}\right\}}$表示顶点的集合，${\displaystyle E=\left\{e_{ij}:(i,j)\in S\subset \left[1,\cdots ,n\right]^{2}\right\}}$表示边的集合（${\displaystyle e_{ij}}$ 表示连接顶点 ${\displaystyle v_{i}}$ 和 ${\displaystyle v_{j}}$ 的边）。

每一个顶点连接的顶点有多有少，用 L(i) 表示与顶点 ${\displaystyle v_{i}}$ 相连的边的集合：

${\displaystyle L(i)=\left\{v_{j}:e_{ij}\in E\land e_{ji}\in E\right\}}$

L(i) 里的边的数量就是顶点 ${\displaystyle v_{i}}$ 的度，记作 ${\displaystyle k_{i}}$ ：${\displaystyle k_{i}=|L(i)|}$。

如果用 ${\displaystyle C_{total}(G)}$ 表示整体集聚系数，用 ${\displaystyle G_{\triangle }}$ 表示图中闭三点组的个数，${\displaystyle G_{\land }}$ 表示其中开三点组的个数，那么：

${\displaystyle C_{total}(G)={\frac {3\times G_{\triangle }}{3\times G_{\triangle }+G_{\land }}}}$

使用 ${\displaystyle k_{i}}$ 来表示的话，也可以写成：

${\displaystyle C_{total}(G)={\frac {3\times G_{\triangle }}{\sum _{i=1}^{n}{\binom {k_{i}}{2}}}}}$^[5]

局部集聚系数

局部集聚系数：蓝点有三个邻接点（白点）。如果三个白点都相互连接（上图），那么蓝点的集聚系数是3÷3=1；如果只有两点之间相连（中图，只有一条边），那么集聚系数是${\displaystyle \scriptstyle {\frac {1}{3}}}$；如果没有两点是相连的，那么集聚系数就是0。

对图中具体的某一个点，它的局部集聚系数 ${\displaystyle C(i)}$ 表示与它相连的点抱成团（完全子图）的程度。邓肯·J·瓦兹（英语：Duncan J. Watts）与斯蒂芬·斯特罗加茨在1998年发表的一篇论文中首次引入了这个概念，用以判别一个图是否是小世界网络^[3]。

图中的一个顶点 ${\displaystyle v_{i}}$ 的局部集聚系数 ${\displaystyle C(i)}$ 等于所有与它相连的顶点之间所连的边的数量，除以这些顶点之间可以连出的最大边数^[6]。一般来说，对于无向图，这个最大边数等于 ${\displaystyle \scriptstyle {\frac {k_{i}(k_{i}-1)}{2}}}$；对于有向图，由于每两个顶点之间可以连两条边（不同方向），最大边数等于 ${\displaystyle k_{i}(k_{i}-1)}$。这时候的 ${\displaystyle k_{i}}$ 表示的是指向顶点 ${\displaystyle v_{i}}$ 的边与从顶点 ${\displaystyle v_{i}}$ 指出去的边的总数。同时，对于有向图，要注意边 ${\displaystyle e_{ij}}$ 与边 ${\displaystyle e_{ji}}$ 是不一样的。

用数学公式表达的话，无向图中一顶点 ${\displaystyle v_{i}}$ 的局部集聚系数是：

${\displaystyle C(i)={\frac {2{\Big |}{\Big \{}e_{jk}:v_{j},v_{k}\in L(i),e_{jk}\in E{\Big \}}{\Big |}}{k_{i}(k_{i}-1)}}.}$

因为边 ${\displaystyle e_{ij}}$ 和边 ${\displaystyle e_{ji}}$ 指的是同一条边。有向图中一顶点 ${\displaystyle v_{i}}$ 的局部集聚系数是：

${\displaystyle C(i)={\frac {{\Big |}{\Big \{}e_{jk}:v_{j},v_{k}\in L(i),e_{jk}\in E{\Big \}}{\Big |}}{k_{i}(k_{i}-1)}}.}$

在无向图 ${\displaystyle G}$ 中，如果设一个顶点 ${\displaystyle v_{i}\in V}$ 的相连闭三角数为${\displaystyle \lambda _{G}(v_{i})}$，也就是 ${\displaystyle G}$ 中所有的包括了 ${\displaystyle v_{i}}$ 的闭三点组（三点中连有三条边）的数目；再设 ${\displaystyle v_{i}}$ 的相连开三角数为 ${\displaystyle \tau _{G}(v_{i})}$，也就是 ${\displaystyle G}$ 中所有的包括了 ${\displaystyle v_{i}}$ ，并且满足两条边都与 ${\displaystyle v_{i}}$ 相连的开三点组（三点中恰好连有两条边）。这时，顶点 ${\displaystyle v_{i}}$ 的局部集聚系数也可以表示为：

${\displaystyle C(i)={\frac {\lambda _{G}(v_{i})}{\tau _{G}(v_{i})+\lambda _{G}(v_{i})}}.}$

很容易证明两种表示方法是等价的。实际上，计算 ${\displaystyle \lambda _{G}(v_{i})}$ 时候的每一个闭三点组，除 ${\displaystyle v_{i}}$ 外的另外两点都是 ${\displaystyle v_{i}}$ 的邻接点，并且他们相连。计算 ${\displaystyle \tau _{G}(v_{i})}$ 时候的每一个开三点组，除 ${\displaystyle v_{i}}$ 外的另外两点也都是 ${\displaystyle v_{i}}$ 的邻接点，并且他们不相连。所以：

${\displaystyle \tau _{G}(v_{i})+\lambda _{G}(v_{i})=C({k_{i}},2)={\frac {1}{2}}k_{i}(k_{i}-1).}$

可以看出，一个顶点 ${\displaystyle v_{i}}$ 的局部集聚系数 ${\displaystyle C(i)}$ 总是在0与1之间。 ${\displaystyle C(i)}$ 越接近1，表示 ${\displaystyle v_{i}}$ 的“邻居”们越是“抱成一团”，接近完全图。${\displaystyle C(i)}$ 越接近0，说明它的邻居们“老死不相往来”，整个结构接近树状。

平均集聚系数

知道了一个图里的每一个顶点的局部集聚系数后，可以计算整个图的平均集聚系数。这个概念也是瓦兹和斯特罗加兹在1998年的论文中引入的^[3]，具体来说就是所有顶点的局部集聚系数的算术平均数：

${\displaystyle {\bar {C}}={\frac {1}{n}}\sum _{i=1}^{n}C(i).}$

平均集聚系数与整体集聚系数都是衡量一个图在整体上的集聚程度。事实上，两者的区别在于：

${\displaystyle {\bar {C}}={\frac {1}{n}}\sum _{i=1}^{n}C(i)={\frac {1}{n}}\sum _{i=1}^{n}{\frac {\lambda _{G}(v_{i})}{\tau _{G}(v_{i})+\lambda _{G}(v_{i})}}}$

而${\displaystyle C_{total}(G)={\frac {\sum _{i=1}^{n}\lambda _{G}(v_{i})}{\sum _{i=1}^{n}\left(\tau _{G}(v_{i})+\lambda _{G}(v_{i})\right)}}}$

一个图（或称为网络）被叫做小世界网络，如果它的平均集聚系数远大于一个在同样的顶点集合上构造的随机图的平均集聚系数，并且它的平均最短路径长度和这种随机图基本相同。

在更为广泛的加权网络^[7]和二部图^[8]中，也可以引进类似于集聚系数的概念。

参见

• 正则图
• ER随机图

参考来源

1. 王冰、修志龙、唐焕文. 基于复杂网络理论的代谢网络结构研究进展 (PDF). 《中国生物工程杂志》. 2005, 25–3 (No.6): 10–14 [2011-04-20]. （原始内容 (PDF)存档于2018-10-01）.
2. P. W. Holland and S. Leinhardt. Transitivity in structural models of small groups. Comparative Group Studies. 1971, 2: 107–124.
3. D. J. Watts and Steven Strogatz. Collective dynamics of 'small-world' networks (PDF). Nature. June 1998, 393 (6684): 440–442 [2011-04-20]. PMID 9623998. doi:10.1038/30918. （原始内容存档 (PDF)于2012-01-05）.
4. R. D. Luce and A. D. Perry. A method of matrix analysis of group structure. Psychometrika. 1949, 14 (1): 95–116. PMID 18152948. doi:10.1007/BF02289146.
5. N. Eggemann and S.D. Noble. The clustering coefficient of a scale-free random graph (PDF). Discrete Applied Mathematics. 2009-11-03, 159 (10): 953–965 [2011-04-20]. doi:10.1016/j.dam.2011.02.003. （原始内容存档 (PDF)于2017-08-13）.
6. 章忠志、荣莉莉、周涛. 一类无标度合作网络的演化模型 (PDF). 《系统工程理论与实践》. 2005年11月, 11: 55–60 [2011-04-20]. （原始内容存档 (PDF)于2018-09-29）.
7. A. Barrat and M. Barthelemy and R. Pastor-Satorras and A. Vespignani. The architecture of complex weighted networks. Proceedings of the National Academy of Sciences. 2004, 101 (11): 3747–3752. PMC 374315 . PMID 15007165. doi:10.1073/pnas.0400087101.
8. M. Latapy and C. Magnien and N. Del Vecchio. Basic Notions for the Analysis of Large Two-mode Networks. Social Networks. 2008, 30 (1): 31–48. doi:10.1016/j.socnet.2007.04.006.