聚集系数

基础概念

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

整体集聚系数

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

假设有图，其中 表示顶点的集合， 表示边的集合（表示连接顶点和的边）。

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

L(i) 里的边的数量就是顶点的度，记作： 。

如果用表示整体集聚系数，用表示图中闭三点组的个数， 表示其中开三点组的个数，那么：使用来表示的话，也可以写成：

参见

• 正则图