« ちょっとした覚書：Rの環境を操作する関数 | メイン | 読了：Clauset, Newman, Moore (2004) すごく大きなネットワークにおけるコミュニティ検出 »
2019年11月13日 (水)
ここんところこういう覚え書きばかりで、自分でも嫌になっちゃうんだけど...
無向グラフにおいて、ノードiとj, jとkの間にエッジがあるときに、iとkの間にもエッジがあることを推移的であるという。有向グラフでは、iからj, jからkへのエッジがあるときに、iからkへのエッジもあることを推移的であるという。
あるグラフにおいて、推移的であるかもしれない2つのノード(上でいうiとk)が実際に推移的である割合を推移性 transitivity という。えーと、Newman, Watts & Strogatz(2002)が提案したのだそうだ。
Rのigraphパッケージでいうと、transivity(g, type ="global") で無向グラフの推移性を求めることができる。なお、transitivity()は有向グラフも無向グラフとして扱うようだ。エッジの向きを考慮したいんなら自分で求めろ、ってことでしょうか。
あるノードからみて、それと隣接するノードからなるサブグラフを考え、その密度(つまり、ありうるエッジの数に占める実際のエッジの数の割合)を求める。これをそのノードのクラスタ係数 clustering coefficient と呼ぶ。igraphパッケージではtransivity(g, type = "local")で求めることができる。
あるグラフについてノードのクラスタ係数を平均した値を、グラフのクラスタ係数という。igraphパッケージではtransivity(g, type = "average")で求めることができる。
このクラスタ係数というのはWatts & Strogatz (1998)が提案したのだそうだ。どっちもワッツさんたちである。なんだかなあ。
推移性とグラフのクラスタ係数はよく似ているんだけど、ちょっと異なる。
いったいどう異なるのか。なにがなんだかわかんなくなってイライラしてきたので、仕事を中断してメモを取った。
準備。
無向単純グラフ$G = (V,E)$について考える。つまり、エッジに向きはないし、自己ループもないし、2ノード間には辺があるかないかのどっちかで、エッジに重みなどというややこしいものはない。
ノード$v$に隣接するノード数を次数$d(v)$とする。
$G$の3つのノードからなる完全サブグラフを三角形と呼ぶ。ノード$v$を含む三角形の数を$\delta(v)$とする。グラフ全体について考える場合、ひとつ三角形が増えるだけで$\delta(v)$の合計は3増えるから、グラフ全体の指標としては
$\delta(G) = \frac{1}{3} \sum_{v \in V} \delta(v)$
がふさわしい。
ノード$v$を中間に持つ長さ2のパスを$v$のトリプルと呼ぶ。その数を$\tau(v)$とすると、$n$個から$k$個を取り出す組み合わせを$combn(n, k)$と書くならば$\tau(v) = combn(d(v), 2)$だ。合計すると
$\tau(G) = \sum_{v \in V} \tau(v)$
本題に戻ろう。
推移性とはなにか。それはトリプルの総数に占める三角形の総数だから、
$\displaystyle T(G) = \frac{3\delta(G)}{\tau(G)}$
である。
グラフのクラスタ係数とはなにか。
次数$d(v) \geq 2$のノードについて、ノードのクラスタ係数$c(v)$とは、トリプルの数に占める三角形の数、つまり$c(v) = \delta(v)/\tau(v)$である。グラフのクラスタ係数というのはこれを平均した値だから、次数2以上のノードの集合を$V'$として
$\displaystyle C(G) = \frac{1}{|V'|} \sum_{v \in V'} c(v)$
である。
なお、次数が1までのノードについてもなんらかクラスタ係数を決め(0だか1だか)、単純平均してしまうという方法もある。
ここで加重クラスタ係数というのを考えてみる。各ノードにウェイトとして正の実数$w(v)$が振られているとしよう。グラフの加重クラスタ係数を
$\displaystyle C_w(G) = \frac{1}{\sum_{v \in V'} w(v)} \sum_{v \in V'} w(v) c(v)$
とする。
仮に、トリプルの数をウェイトにしたら、つまり$w(v) = \tau(v)$としたらどうなるか。$c(v) = \delta(v)/\tau(v)$より、総和記号の右の$\tau(v)$は消えて、
$\displaystyle C_\tau(G) = \frac{\sum_{v \in V'} \delta(v)}{\sum_{v \in V'} \tau(v)} = T(G)$
となる。
つまり推移性とは、各ノードが持つトリプルの数を重みにした加重クラスタ係数のことだ。全ノードの次数が同じとき、ないし全ノードのクラスタ係数が一致しているとき、グラフのクラスタ係数と推移性は等しくなる。
以上、次の論文のイントロ部分よりメモ。
Shank, T., Wagner, D. (2005) Approximating clustering coefficent and transitivity. Journal of Graph Algorithms and Applications. 9(2), 265-275.
なるほどね...
グラフの特性を記述する際、推移性を使うべきなのだろうか、グラフのクラスタ係数を使うべきなのだろうか。たとえばある社会が「友達の友達もまた友達だ」的性質を持っているかどうかを調べるならば、ノードをベースに考えて後者を使い、たくさんの離散的状態を遷移していくなにかについて、そこでの遷移が「3期後には元に戻っちゃう」的性質を持っているかどうかを調べるならば、エッジをベースに考えて前者を使う、ということかなあ...
雑記：データ解析 - ちょっとした覚え書き：グラフの推移性とクラスタ係数はどうちがうか