在图论 中，集聚系数 （也称群聚系数 、集群系数 ）是用来描述一个图 中的顶点 之间结集成团的程度的系数。具体来说，是一个点的邻接点之间相互连接的程度。例如生活社交网络中，你的朋友之间相互认识的程度[ 1] 社交网络 结构中，各个结点之间倾向于形成密度相对较高的网群[ 2] [ 3]
集聚系数分为整体与局部两种。整体集聚系数可以给出一个图中整体的集聚程度的评估，而局部集聚系数则可以测量图中每一个结点附近的集聚程度。
集聚系数主要是描述图（或者称为网络）的特性。一个图 G 是由一些顶点 V 和顶点与顶点之间的一些连线（称为边）E 构成。两个相连的顶点也称为邻接点。比如在一群人中，将每个人用一个点表示，如果两人之间认识，就将对应的两点连起来。这样就构成了一个图。有的图是有方向的，比如在同样一群人中，如果一人甲欠另一人乙的钱，就连一条从
甲至乙的线，这样就构成了一个有向图 。
整体集聚系数的定义建立在闭三点组（邻近三点组）之上。假设图中有一部分点是两两相连的，那么可以找出很多个“三角形”，其对应的三点两两相连，称为闭三点组。除此以外还有开三点组，也就是之间连有两条边的三点（缺一条边的三角形）。这两种三点组构成了所有的连通 三点组。整体集聚系数定义为一个图中所有闭三点组的数量与所有连通三点组（无论开还是闭）的总量之比（也有定义为这个值的三倍，使得在完全图 中的整体集聚系数等于1）。最早尝试测量这个系数是在1949年罗伯特·邓肯·路斯 和阿尔伯特·D·佩里 合作的一篇论文中[ 4]
假设有图
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
V
=
{
v
1
,
v
2
,
⋯
,
v
n
}
{\displaystyle V=\left\{v_{1},v_{2},\cdots ,v_{n}\right\}}
顶点 的集合，
E
=
{
e
i
j
:
(
i
,
j
)
∈
S
⊂
[
1
,
⋯
,
n
]
2
}
{\displaystyle E=\left\{e_{ij}:(i,j)\in S\subset \left[1,\cdots ,n\right]^{2}\right\}}
e
i
j
{\displaystyle e_{ij}}
v
i
{\displaystyle v_{i}}
v
j
{\displaystyle v_{j}}
每一个顶点 连接的顶点有多有少，用 L (i ) 表示与顶点
v
i
{\displaystyle v_{i}}
L
(
i
)
=
{
v
j
:
e
i
j
∈
E
∧
e
j
i
∈
E
}
{\displaystyle L(i)=\left\{v_{j}:e_{ij}\in E\land e_{ji}\in E\right\}}
L (i ) 里的边的数量就是顶点
v
i
{\displaystyle v_{i}}
k
i
{\displaystyle k_{i}}
k
i
=
|
L
(
i
)
|
{\displaystyle k_{i}=|L(i)|}
如果用
C
t
o
t
a
l
(
G
)
{\displaystyle C_{total}(G)}
G
△
{\displaystyle G_{\triangle }}
G
∧
{\displaystyle G_{\land }}
C
t
o
t
a
l
(
G
)
=
3
×
G
△
3
×
G
△
+
G
∧
{\displaystyle C_{total}(G)={\frac {3\times G_{\triangle }}{3\times G_{\triangle }+G_{\land }}}}
使用
k
i
{\displaystyle k_{i}}
C
t
o
t
a
l
(
G
)
=
3
×
G
△
∑
i
=
1
n
(
k
i
2
)
{\displaystyle C_{total}(G)={\frac {3\times G_{\triangle }}{\sum _{i=1}^{n}{\binom {k_{i}}{2}}}}}
[ 5]
局部集聚系数：蓝点有三个邻接点（白点）。如果三个白点都相互连接（上图），那么蓝点的集聚系数是3÷3=1；如果只有两点之间相连（中图，只有一条边），那么集聚系数是
1
3
{\displaystyle \scriptstyle {\frac {1}{3}}}
对图中具体的某一个点，它的局部集聚系数
C
(
i
)
{\displaystyle C(i)}
团 （完全子图 ）的程度。邓肯·J·瓦兹 斯蒂芬·斯特罗加茨 在1998年发表的一篇论文中首次引入了这个概念，用以判别一个图是否是小世界网络 [ 3]
图中的一个顶点
v
i
{\displaystyle v_{i}}
C
(
i
)
{\displaystyle C(i)}
[ 6]
k
i
(
k
i
−
1
)
2
{\displaystyle \scriptstyle {\frac {k_{i}(k_{i}-1)}{2}}}
k
i
(
k
i
−
1
)
{\displaystyle k_{i}(k_{i}-1)}
k
i
{\displaystyle k_{i}}
v
i
{\displaystyle v_{i}}
v
i
{\displaystyle v_{i}}
e
i
j
{\displaystyle e_{ij}}
e
j
i
{\displaystyle e_{ji}}
用数学公式表达的话，无向图中一顶点
v
i
{\displaystyle v_{i}}
C
(
i
)
=
2
|
{
e
j
k
:
v
j
,
v
k
∈
L
(
i
)
,
e
j
k
∈
E
}
|
k
i
(
k
i
−
1
)
.
{\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)}}.}
因为边
e
i
j
{\displaystyle e_{ij}}
e
j
i
{\displaystyle e_{ji}}
顶点
v
i
{\displaystyle v_{i}}
C
(
i
)
=
|
{
e
j
k
:
v
j
,
v
k
∈
L
(
i
)
,
e
j
k
∈
E
}
|
k
i
(
k
i
−
1
)
.
{\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)}}.}
在无向图
G
{\displaystyle G}
v
i
∈
V
{\displaystyle v_{i}\in V}
λ
G
(
v
i
)
{\displaystyle \lambda _{G}(v_{i})}
G
{\displaystyle G}
v
i
{\displaystyle v_{i}}
v
i
{\displaystyle v_{i}}
τ
G
(
v
i
)
{\displaystyle \tau _{G}(v_{i})}
G
{\displaystyle G}
v
i
{\displaystyle v_{i}}
v
i
{\displaystyle v_{i}}
v
i
{\displaystyle v_{i}}
C
(
i
)
=
λ
G
(
v
i
)
τ
G
(
v
i
)
+
λ
G
(
v
i
)
.
{\displaystyle C(i)={\frac {\lambda _{G}(v_{i})}{\tau _{G}(v_{i})+\lambda _{G}(v_{i})}}.}
很容易证明两种表示方法是等价的。实际上，计算
λ
G
(
v
i
)
{\displaystyle \lambda _{G}(v_{i})}
v
i
{\displaystyle v_{i}}
v
i
{\displaystyle v_{i}}
τ
G
(
v
i
)
{\displaystyle \tau _{G}(v_{i})}
v
i
{\displaystyle v_{i}}
v
i
{\displaystyle v_{i}}
τ
G
(
v
i
)
+
λ
G
(
v
i
)
=
C
(
k
i
,
2
)
=
1
2
k
i
(
k
i
−
1
)
.
{\displaystyle \tau _{G}(v_{i})+\lambda _{G}(v_{i})=C({k_{i}},2)={\frac {1}{2}}k_{i}(k_{i}-1).}
可以看出，一个顶点
v
i
{\displaystyle v_{i}}
C
(
i
)
{\displaystyle C(i)}
C
(
i
)
{\displaystyle C(i)}
v
i
{\displaystyle v_{i}}
C
(
i
)
{\displaystyle C(i)}
树状 。
知道了一个图里的每一个顶点 的局部集聚系数后，可以计算整个图的平均集聚系数。这个概念也是瓦兹和斯特罗加兹在1998年的论文中引入的[ 3] 算术平均数 ：
C
¯
=
1
n
∑
i
=
1
n
C
(
i
)
.
{\displaystyle {\bar {C}}={\frac {1}{n}}\sum _{i=1}^{n}C(i).}
平均集聚系数与整体集聚系数都是衡量一个图在整体上的集聚程度。事实上，两者的区别在于：
C
¯
=
1
n
∑
i
=
1
n
C
(
i
)
=
1
n
∑
i
=
1
n
λ
G
(
v
i
)
τ
G
(
v
i
)
+
λ
G
(
v
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})}}}
而
C
t
o
t
a
l
(
G
)
=
∑
i
=
1
n
λ
G
(
v
i
)
∑
i
=
1
n
(
τ
G
(
v
i
)
+
λ
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]
王冰、修志龙、唐焕文. 基于复杂网络理论的代谢网络结构研究进展 (PDF) . 《中国生物工程杂志》. 2005, 25–3 (No.6): 10–14 [2011-04-20 ] . （原始内容 (PDF) 存档于2018-10-01）. P. W. Holland and S. Leinhardt. Transitivity in structural models of small groups . Comparative Group Studies. 1971, 2 : 107–124.
章忠志、荣莉莉、周涛. 一类无标度合作网络的演化模型 (PDF) . 《系统工程理论与实践》. 2005年11月, 11 : 55–60 [2011-04-20 ] . （原始内容存档 (PDF) 于2018-09-29）. 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 
![{\displaystyle E=\left\{e_{ij}:(i,j)\in S\subset \left[1,\cdots ,n\right]^{2}\right\}}](http://wikimedia.org/api/rest_v1/media/math/render/svg/02cf8bf1faeb47068ffbff1e9f9f028f1e16bc3d)
