聚類係數
聚類係數
聚集係數是表示一個圖形中節點聚集程度的係數，證據顯示，在現實的網路中，尤其是在特定的網路中，由於相對高密度連接點的關係，節點總是趨向於建立一組嚴密的組織關係。在現實世界的網路，這種可能性往往比兩個節點之間隨機設立了一個連接的平均概率更大。這種相互關係可以利用聚類係數進行量化表示。
按照圖形理論，聚集係數是表示一個圖形中節點聚集程度的係數。
在很多網路中，如果節點v1連接於節點v2，節點v2連接於節點v3，那麼節點v3很可能與v1相連接。這種現象體現了部分節點間存在的密集連接性質。例如，在無向網路中，可以用聚類係數（）來表示v2的聚類係數：
其中：k表示節點v2的所有相鄰的節點的個數，即節點v2的鄰居。
n表示節點v2的所有相鄰節點之間相互連接的邊的個數。
全局集聚係數是基於結點三元組的。一個三元組是其中有兩條（開三元組）或三條（閉三元組）無向邊連接的三個結點。三元組指由兩條邊連接的三個節點，有時也稱為2-星，2-star。全局集聚係數是所有三元組（包括開和閉的）中封閉三元組的數目。
圖中一個結點的局部集聚係數表示了它的相鄰結點形成一個團（完全圖）的緊密程度。Duncan J. Watts和Steven Strogatz在1998年引入了度量一個圖是否是小世界網路的方法。
定義
: 圖G包含一系列結點V和連接它們的邊E.
eij : 連接結點i與結點j的邊.
的第i個相鄰結點.
相鄰結點的數量.
結點vi的局部集聚係數Ci是它的相鄰結點之間的連接數與它們所有可能存在連接的數量的比值。對於一個有向圖，是不同的，因而對於每個鄰結點 Ni在鄰結點之間可能存在有 條邊（ki 是結點的出入度之和）。
整個網路的集聚係數由Watts和Strogatz定義為所有結點n的局部集聚係數的均值：
如果一個圖的平均集聚係數顯著高於相同結點集生成的隨機圖，而且平均最短距離與相應隨機生成的隨機圖相近，那麼這個圖被認為是小世界的。
有更高平均集聚係數的網路被發現有著模塊結構，同時在不同結點中還有更小的平均距離。
