平均クラスタ係数

$G=(V,E)$について考える。

$N=|V|$

$M=|E|$

隣接行列

隣接行列$A$の要素$a_{i,j}$は、$i$番目のノードと$j$番目のノードが隣接している場合、$a_{i,j}=1$、そうでない場合には$a_{i,j}=0$を取る行列である。

無向グラフの場合、枝$(i,j), (j,i)\in E$を区別しないので、隣接行列は対称行列となる。

• ネットワークの性質を解析的に議論する際には、隣接行列が有用である。

• 一方、数値的に解析する場合には、隣接していないノード対を表すゼロの数の割合が非常に高いため、現実のグラフを表現した際に、行列の成分全体の1%ほどしか非ゼロ成分が存在しない場合がある。このような非ゼロ成分の少ない行列を扱うために計算機のメモリを無駄にに消費してしまう。この場合は、行列のデータ構造を工夫するなどして効率よく計算していく必要がある。

ノードの次数

$i$番目のノードに繋がっているエッジの本数をノード$i$の次数といい、$k_i$で表す。次数$k_i$は隣接行列$A$の要素$a_{i,j}$を用いて

$$k_i = \sum_{j=1}^Na_{ij}$$

と表すことができる。例えば、単純グラフの場合はノード $i$に隣接するノード数と次数が一致する。

• 次数は、ネットワークが持つ情報を全て含む隣接行列をトレースアウトして得られる特徴量のなかで最も単純な量である。

• ネットワーク構造を議論する際には、極めて重要となる基本的な量である。

代表的なグラフの次数に関する性質

• 全ノードの次数が$N-1$であるネットワークは完全グラフである。

• 全ての次数が$k$であるネットワークが$k-$正則グラフである。

握手の定理とは、グラフのノード全体の次数と枝の本数に関する関係式である。

$$\sum_{i=1}^Nk_i=2M$$

$$2M=\sum_{i,j=1}^Na_{i,j}={\rm Tr}A^2$$

この等式は、多重エッジや自己ループを含むようなグラフに対しても成立する。握手の定理から次の補題が従う。

[補題] 任意のネットワークにおいて奇数次数のノードは偶数個ある。

証明：

$S_{odd}, S_{even}$をそれぞれ次数が奇数, 偶数であるノードの集合とする。 $S_{odd}\cup S_{even}=V$であるから、握手の定理より

$$2M=\sum_{i\in S_{odd}} k_i + \sum_{i \in S_{even}} k_i$$

左辺に注目すると、Mが整数であることから2Mは偶数である。一方、右辺に着目すると第二項は次数が偶数のノードの次数の和であるから、偶数である。よって上記の等式が成り立つためには、第一項が偶数である必要がある。今、第一項は次数が奇数のノードの和であるから、上記の等式が成り立つためには、総和の項数が偶数である必要がある。逆に、総和の項数が偶数であれば、上記の等式が成り立つ。

よって任意のネットワークにおいて、奇数次数のノードは偶数個あることがわかる。

グラフの平均次数

次数を全ノードで平均した平均次数$\langle k\rangle$は、ネットワーク全体の大域的性質を表す量の１つである。全ノードの次数の平均値が平均次数なので

$$\begin{align*} \langle k \rangle&=\frac{1}{N} \sum_{i=1}^Nk_i \\ &=\frac{2M}{N} \end{align*}$$

と表される。後半の式変更には握手の定理を用いた。

• 全ての無向グラフにおいて$\langle k\rangle \leq N-1$であり、等号成立条件は完全グラフの場合に限る。

• $\langle k \rangle$がNと同程度の大きさであるようなグラフは、エッジの密度が高い。

• 逆に平均次数がNから小さいグラフはエッジの密度の低い疎なグラフであると言える。

• 平均次数はグラフのエッジの「密度」を反映した量であると言える。

エッジ密度とクラスター係数

グラフ内のノードがどれほど密に繋がっているかは、グラフを特徴づける重要な要素である。

同じ$N$個のノードからなるネットワークでも、完全グラフと木とでは、エッジの密度に大きな違いがある。当然、完全グラフが最もエッジの密度が高く、逆に孤立したノード集合からなるグラフが最もエッジの密度が低い。このように今考えているグラフ$G$の枝の本数と、$G$のノードから生成される完全グラフの枝数$\frac{1}{2}N(N-1)$に対する割合でグラフのエッジ密度$\rho$を定義する。$\rho$は

$$\rho=\frac{2M}{N(N-1)}=\frac{\langle k \rangle}{N-1}$$

と表される。上記のエッジ密度の定義は、グラフ全体に対して定義されているが、同様にグラフの部分グラフに対しても同様に定義し、それを局所的エッジ密度と呼ぶこととする。

あるノード$i$の$l$近傍部分グラフ$G_i(l)$を考える。ここで、$l$近傍部分グラフとはノード$i$から$l$ホップで辿れるノードとエッジに関する部分グラフである。近傍部分グラフ$G_i(l)$のノード数と枝数をそれぞれ$n_i(l), m_i(l)$とすると、近接部分グラフの局所的エッジ密度$\rho_i(l)$は

$$\rho_i(l)=\frac{2 m_i(l)}{n_i(l)(n_i(l)-1)}$$

と表される。この指標により、近接部分グラフがクリークであればそのエッジ密度が１であるので、近接部分グラフのクリーク性の程度を表しているものと考えられる。

局所的エッジ密度として、特に重要なのは、最も局所性の高い$l=1$における$\rho_i(l=1)$である。近接部分グラフ$G_i(1)$について、ノード数とエッジ数はそれぞれ$n_i(1)=k_i, m_i(1)=m_i+k_i$となる。ただし、$m_i$は、ノード$i$の隣接ノード間を結ぶエッジの数である。$m_i$について、ノード$i$の近接部分グラフ$G_i(1)$がクリークであるとき、$G_i(1)$からノード$i$が接続している$k_i$本のエッジを取り除いた部分グラフ$g_i$もクリークとなる。よって、ノード$i$の周りのエッジの密度$C_i$を$g_i$の枝数$m_i$と点数$k_i$を用いて次のように定義する。

$$C_i=\frac{2m_i}{k_i(k_i-1)}$$

$C_i$をノード$i$のクラスター係数と呼ぶ。クラスター係数はネットワーク科学において重要な役割を果たす。定義より、$m_i$はノード$i$を頂点とする三角形の個数と一致するので、クラスタ係数はノード$i$を頂点とする三角形の割合とも捉えることができる。

各ノードのクラスタ係数の平均値を平均クラスタ係数といい、$C$と表す。

$$C=\frac{1}{N}\sum_{i=1}^NC_i$$

$C=1$となる場合は、完全グラフの場合のみに限る。

• クラスター係数は三角形（3次のサイクル）の数の割合である。

• エッジ密度が$0$に近い場合でも平均クラスタ係数が$1$に近い値を取ることがある。

• クラスター係数は無向グラフに対する特徴量であり、有向グラフには定義されない。

• 上記のクラスタ係数は3次のサイクルの割合と定義されていたが、4次のバージョンも存在し、サイクル係数と呼ばれる。

※近接部分グラフの密度だけでは不十分なのか？