ここでは頂点がすべて連結した無向グラフを扱う。

歴史

1998 D. J. Watts, Steven Strogatz "Collective dynamics of 'small-world' networks". Nature 393: 440–442. doi:10.1038/30918.

クラスター係数と平均頂点間距離

Link Analysisではグラフにおける各頂点の尺度としてcentralityとprestigeを紹介した。ここではネットワーク全体についての尺度としてクラスター係数 $C$ と平均頂点間距離 $L$ を紹介する。

クラスター係数は隣接する頂点間の辺の密度の平均値にあたる。まず各頂点 $i$ におけるクラスター係数を以下のように定義する。辺の長さはすべて1とする $|e|=1$ 。

$\textstyle C_i=\frac{2}{deg(i)(deg(i)-1)} \sum_{j,k \in neighbor(i)} |e_{jk}|$

グラフ全体のクラスター係数はその平均値になる。

$\textstyle C =\frac{1}{n} \sum^{n}_{i=1}C_i$

平均頂点間距離はその字のごとく全頂点間の最短路の平均値にあたる。ここでは頂点 $i, j$ 間の最短経路を $p_{ij}$ と書く。

$\textstyle L=\frac{1}{n} \sum_{i,j\in G}|p_{ij}|$

平面の場合は三角格子、正方格子が考えられる。特に、 $d$ 次元空間において辺の長さが単位距離の格子をZ^dと書く。

例. Z²において、 $deg(i)=2d$

クラスター係数は定義のままだと0になって都合が悪いので、最短距離が $a$ 以下の点には全て辺を持つZ'^dを考えよう。

例. Z'^dのクラスター係数は

2/(2d)(2d-1) . 2 d