聚集係數

在圖論中，集聚係數（也稱群聚係數、集群係數）是用來描述一個圖中的頂點之間結集成團的程度的係數。具體來說，是一個點的鄰接點之間相互連線的程度。例如生活社交網路中，你的朋友之間相互認識的程度。有證據表明，在各類反映真實世界的網路結構，特別是社交網路結構中，各個結點之間傾向於形成密度相對較高的網群。也就是說，相對於在兩個節點之間隨機連線而得到的網路，真實世界網路的集聚係數更高。

集聚係數分為整體與局部兩種。整體集聚係數可以給出一個圖中整體的集聚程度的評估，而局部集聚係數則可以測量圖中每一個結點附近的集聚程度。

基本介紹

• 中文名：聚集係數
• 外文名：Clustering coefficient
• 別稱：集群係數

基礎概念

集聚係數主要是描述圖（或者稱為網路）的特性。一個圖G是由一些頂點V和頂點與頂點之間的一些連線（稱為邊）E構成。兩個相連的頂點也稱為鄰接點。比如在一群人中，將每個人用一個點表示，如果兩人之間認識，就將對應的兩點連起來。這樣就構成了一個圖。有的圖是有方向的，比如在同樣一群人中，如果一人甲欠另一人乙的錢，就連一條從 甲至乙的線，這樣就構成了一個有向圖。

整體集聚係數

整體集聚係數的定義建立在閉三點組（鄰近三點組）之上。假設圖中有一部分點是兩兩相連的，那么可以找出很多個“三角形”，其對應的三點兩兩相連，稱為閉三點組。除此以外還有開三點組，也就是之間連有兩條邊的三點（缺一條邊的三角形）。這兩種三點組構成了所有的連通三點組。整體集聚係數定義為一個圖中所有閉三點組的數量與所有連通三點組（無論開還是閉）的總量之比（也有定義為這個值的三倍，使得在完全圖中的整體集聚係數等於1）。最早嘗試測量這個係數是在1949年羅伯特·鄧肯·路斯和阿爾伯特·D·佩里合作的一篇論文中。

假設有圖 ，其中 表示頂點的集合， 表示邊的集合（ 表示連線頂點 和 的邊）。

每一個頂點連線的頂點有多有少，用L(i) 表示與頂點 相連的邊的集合：

L(i) 里的邊的數量就是頂點 的度，記作 ： 。

如果用 表示整體集聚係數，用 表示圖中閉三點組的個數， 表示其中開三點組的個數，那么：

使用 來表示的話，也可以寫成：

參見

• 正則圖