集聚係數

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

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

基礎概念

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

整體集聚係數

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

假設有圖$G=(V,E)$，其中$V=\left\{v_{1},v_{2},\cdots ,v_{n}\right\}$表示頂點的集合，$E=\left\{e_{ij}:(i,j)\in S\subset \left[1,\cdots ,n\right]^{2}\right\}$表示邊的集合（$e_{ij}$ 表示連接頂點 $v_{i}$ 和 $v_{j}$ 的邊）。

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

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

L(i) 里的邊的數量就是頂點 $v_{i}$ 的度，記作 $k_{i}$ ：$k_{i}=|L(i)|$。

如果用 $C_{total}(G)$ 表示整體集聚係數，用 $G_{\triangle }$ 表示圖中閉三點組的個數，$G_{\land }$ 表示其中開三點組的個數，那麼：

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

使用 $k_{i}$ 來表示的話，也可以寫成：

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

局部集聚係數

局部集聚係數：藍點有三個鄰接點（白點）。如果三個白點都相互連接（上圖），那麼藍點的集聚係數是3÷3=1；如果只有兩點之間相連（中圖，只有一條邊），那麼集聚係數是$\scriptstyle {\frac {1}{3}}$；如果沒有兩點是相連的，那麼集聚係數就是0。

對圖中具體的某一個點，它的局部集聚係數 $C(i)$ 表示與它相連的點抱成團（完全子圖）的程度。鄧肯·J·瓦茲與斯蒂芬·斯特羅加茨在1998年發表的一篇論文中首次引入了這個概念，用以判別一個圖是否是小世界網絡。

圖中的一個頂點 $v_{i}$ 的局部集聚係數 $C(i)$ 等於所有與它相連的頂點之間所連的邊的數量，除以這些頂點之間可以連出的最大邊數。一般來說，對於無向圖，這個最大邊數等於 $\scriptstyle {\frac {k_{i}(k_{i}-1)}{2}}$；對於有向圖，由於每兩個頂點之間可以連兩條邊（不同方向），最大邊數等於 $k_{i}(k_{i}-1)$。這時候的 $k_{i}$ 表示的是指向頂點 $v_{i}$ 的邊與從頂點 $v_{i}$ 指出去的邊的總數。同時，對於有向圖，要注意邊 $e_{ij}$ 與邊 $e_{ji}$ 是不一樣的。

用數學公式表達的話，無向圖中一頂點 $v_{i}$ 的局部集聚係數是：

$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_{ij}$ 和邊 $e_{ji}$ 指的是同一條邊。有向圖中一頂點 $v_{i}$ 的局部集聚係數是：

$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$ 中，如果設一個頂點 $v_{i}\in V$ 的相連閉三角數為$\lambda _{G}(v_{i})$，也就是 $G$ 中所有的包括了 $v_{i}$ 的閉三點組（三點中連有三條邊）的數目；再設 $v_{i}$ 的相連開三角數為 $\tau _{G}(v_{i})$，也就是 $G$ 中所有的包括了 $v_{i}$ ，並且滿足兩條邊都與 $v_{i}$ 相連的開三點組（三點中恰好連有兩條邊）。這時，頂點 $v_{i}$ 的局部集聚係數也可以表示為：

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

很容易證明兩種表示方法是等價的。實際上，計算 $\lambda _{G}(v_{i})$ 時候的每一個閉三點組，除 $v_{i}$ 外的另外兩點都是 $v_{i}$ 的鄰接點，並且他們相連。計算 $\tau _{G}(v_{i})$ 時候的每一個開三點組，除 $v_{i}$ 外的另外兩點也都是 $v_{i}$ 的鄰接點，並且他們不相連。所以：

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

可以看出，一個頂點 $v_{i}$ 的局部集聚係數 $C(i)$ 總是在0與1之間。 $C(i)$ 越接近1，表示 $v_{i}$ 的「鄰居」們越是「抱成一團」，接近完全圖。$C(i)$ 越接近0，說明它的鄰居們「老死不相往來」，整個結構接近樹狀。

平均集聚係數

知道了一個圖裡的每一個頂點的局部集聚係數後，可以計算整個圖的平均集聚係數。這個概念也是瓦茲和斯特羅加茲在1998年的論文中引入的，具體來說就是所有頂點的局部集聚係數的算術平均數：

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

平均集聚係數與整體集聚係數都是衡量一個圖在整體上的集聚程度。事實上，兩者的區別在於：

${\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_{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)}}$

一個圖（或稱為網絡）被叫做小世界網絡，如果它的平均集聚係數遠大於一個在同樣的頂點集合上構造的隨機圖的平均集聚係數，並且它的平均最短路徑長度和這種隨機圖基本相同。

在更為廣泛的加權網絡和二部圖中，也可以引進類似於集聚係數的概念。

參見

• 正則圖
• ER隨機圖