在图论中,集聚系数(也称群聚系数、集群系数)是用来描述一个图中的顶点之间结集成团的程度的系数。具体来说,是一个点的
邻接点之间相互连接的程度。例如生活
社交网络中,你的朋友之间相互认识的程度。有证据表明,在各类反映
真实世界的
网络结构,特别是社交网络结构中,各个结点之间倾向于形成密度相对较高的网群。也就是说,相对于在两个节点之间随机连接而得到的网络,真实世界网络的集聚系数更高。
集聚系数主要是描述图(或者称为网络)的特性。一个图G是由一些顶点V和顶点与顶点之间的一些连线(称为边)E构成。两个相连的顶点也称为
邻接点。比如在一群人中,将每个人用一个点表示,如果两人之间认识,就将对应的两点连起来。这样就构成了一个图。有的图是有方向的,比如在同样一群人中,如果一人甲欠另一人乙的钱,就连一条从 甲至乙的线,这样就构成了一个
有向图。
整体集聚系数的定义建立在闭三点组(邻近三点组)之上。假设图中有一部分点是两两相连的,那么可以找出很多个“
三角形”,其对应的三点两两相连,称为闭三点组。除此以外还有开三点组,也就是之间连有两条边的三点(缺一条边的三角形)。这两种三点组构成了所有的连通三点组。整体集聚系数定义为一个图中所有闭三点组的数量与所有连通三点组(无论开还是闭)的总量之比(也有定义为这个值的三倍,使得在
完全图中的整体集聚系数等于1)。最早尝试测量这个系数是在1949年罗伯特·邓肯·路斯和阿尔伯特·D·佩里合作的一篇论文中。