- igraphパッケージのcohesive.blocks()関数のExamplesにあり、この論文の中でも扱われている例をとって、cohesive blocksの取り出し手順を確認してみよう
- k-component
- 連結な(サブ)グラフがあって、ノードを除去すると、(サブ)グラフが２つ以上に分けられるとする。ある(サブ)グラフについて、そのようにできる最小のノード数をkとして、その(サブ)グラフをk-componentと言う。また、その(サブ)グラフk-connectedであるとも言う
- k-cutsets
- k-componentな(サブ)グラフには、k個のノードのセットが１つ以上あって、そのセットの要素ノードを取り除くと２つ以上に分けられる。このようなk個のノードのセットをk-cutsetsという
- 階層的にk-component/k-cutsetsを用いてグラフを分離しつつ、よりkの大きなサブグラフを同定していく作業が(階層的な)cohesive blockingである
- 下図を見よう
- 第１階層
- 全体が連結のグラフである(ノードは1,2,...,23)
- このグラフ全体は、ノード7を取り除くと２つに分かれるから、1-componentであり、1-cutsetは{7}のである(ほかには1-cutsetはない)
- 第２階層
- 1-cuset {7}により、{1,2,3,4,5,6,7,8,12,19,20,21,22,23}と{7,9,10,11,13,14,15,16,17,18}とに分かれた
- {7}は両方にあることに注意(cutsetによる分離で、どこにも属さないノードを作らない)
- 分離してできた２つについてそれぞれ考える
- (1){1,2,3,4,5,6,7,8,12,19,20,21,22,23}について考える
- 1-componentではない(1-componentならば、前の階層で1-cutsetをすべて確認しているはずなので)
- 7,5を除くと分離するから、2-componentである(1-componentではなくて、1より1大きいだけの2の2-componentなので、これが最小)
- 2-cutsetの一つが{5,7}である
- 他に2-cutsetsがあるか、と確かめると{5,7},{8,12},{5,12},{7,8}の４セット取れる
- 2-cutsetsの要素が置いてきぼりにならないように分けると{1,2,3,4,5,6,7},{8,12,19,20,21,22,23}の２つにわかれる
- (2){7,9,10,11,13,14,15,16,17,18}について考える
- 1-componentではない(上記と同じ理由)
- {9,14}を選べば、分離する。したがって、2-component
- 他に2-cutsetsがあるか、と調べれば、{9,14},{14,17},{11,17}の３セットある
- これらによって分離すれば{7,9,10,11,14,15,17},{9,13,14},{11,17,18},{14,16,17}となる
- 第３階層
- {1,2,3,4,5,6,7},{8,12,19,20,21,22,23},{7,9,10,11,14,15,17},{9,13,14},{11,17,18},{14,16,17}の６サブグラフについて考える
- 2-cutsetsまで検討してあるから、どちらもk >= 3 を探すことになる
- (1){1,2,3,4,5,6,7}について考える
- {2,3,4,5,6}の5つを除くと1,7に分離するから5-component
- 他にも5-cutsetsは{1,3,4,5,7}などいくつかある
- 分離してできるサブグラフはノード数6だが、さらにkを大きくしようとするとk>=6だ。しかし、ノード数が6で6-componentはありえないので、この先はもう終わり
- (2){8,12,19,20,21,22,23}について考える
- {8,12,21}を取り除くと{19,20},{22,23}に分かれるから3-component。2-componentよりkが大きくなっている
- できるサブグラフのノード数は5である。ここにk>=4のk-componentを作れるとすれば、それはノード数5の完全グラフである場合だが、そうでないことはわかる。したがって、ここで終了
- (3){7,9,10,11,14,15,17}について考える
- 3-component以上を考えている。
- {15}を除けば分離するので1-componentだけれど、これはもう考えない
- そんな小さいkのk-componentは作る端から、切り捨てていって{7,9,10,11}が残る
- これは、ノード数４の完全グラフで、3-component
- k>=3を探していて、k=3が見つかり、それが完全グラフでそれ以上密にしようがないから、このサブグラフも終了
- (4){9,13,14},{11,17,18},{14,16,17}について考える
- k>=3を探していて、これらはノード数3だから、もう考えなくてよい
- 結局、3階層まで進んで、以下が出る
- {1,2,3,...,23}の初期状態(1-component)
- {1,2,3,4,5,6,7,8,12,19,20,21,22,23}(2-component)
- {7,9,10,11,13,14,15,16,17,18}(2-component)
- {1,2,3,4,5,6,7}(5-component)
- {8,12,19,20,21,22,23}(3-component)
- {7,9,10,11}(3-component)
- 以下の実行結果で{8,12,19,20,21,22,23}(3-component)が表示されていないのが、ちょっと気になるが…
- 分離して、それより階層が下がらないときには、より大きいkのk-componentだけがあったとみなす、というルールなのか(そうしない方がよいように思うけれども)
mw <- graph.formula(1-2:3:4:5:6, 2-3:4:5:7, 3-4:6:7, 4-5:6:7,
5-6:7:21, 6-7, 7-8:11:14:19, 8-9:11:14, 9-10,
10-12:13, 11-12:14, 12-16, 13-16, 14-15, 15-16,
17-18:19:20, 18-20:21, 19-20:22:23, 20-21,
21-22:23, 22-23)
mwBlocks <- cohesive.blocks(mw)
mwBlocks
blocks(mwBlocks)
cohesion(mwBlocks)
plot(mwBlocks, mw)
> mwBlocks
Cohesive block structure:
B-1 c 1, n 23
'- B-2 c 2, n 14 oooooooo.. .o......oo ooo
'- B-4 c 5, n 7 ooooooo... .......... ...
'- B-3 c 2, n 10 ......o.oo o.oooooo.. ...
'- B-5 c 3, n 4 ......o.oo o......... ...
> blocks(mwBlocks)
[[1]]
[1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
[[2]]
[1] 1 2 3 4 5 6 7 8 12 19 20 21 22 23
[[3]]
[1] 7 9 10 11 13 14 15 16 17 18
[[4]]
[1] 1 2 3 4 5 6 7
[[5]]
[1] 7 9 10 11
> cohesion(mwBlocks)
[1] 1 2 2 5 3
