ネットワーク全体指標はあまりビジネス的に扱うことが多くないので、代わりに今回はコミュニティ検出（要はグラフ構造内でのクラスタリング）について取り上げます。ただし前回まで参考にしていた『ネットワーク分析』はあまりコミュニティ検出についてそこまで詳説していないので、九工大の竹本和広先生の資料サイトも参照することにします。
- 作者: 鈴木努,金明哲
- 出版社/メーカー: 共立出版
- 発売日: 2009/09/25
- メディア: 単行本
- 購入: 5人 クリック: 62回
- この商品を含むブログ (9件) を見る
ちなみに竹本先生の資料は、それ単体で僕が書いてきたグラフ・ネットワーク分析に関するエントリ4つ（今回含めて）全てを合わせたよりも内容が濃いので、こんなブログまどろっこしいという方は竹本先生の資料を読んだ方が早いです（笑）。
なお、今回に限ってはサンプルデータセットとして『レ・ミゼラブル』の人物相関図のみを取り上げます。理由は簡単で、同作品の読者としては実際にどういうコミュニティがネットワーク内に存在するかを事前知識として知っているからです（笑）。
> g2<-read.graph("lesmis.gml",format="GML")
前回の記事同様にNetwork dataから"lesmis"データセットをDLしてきてgmlファイルをインポートしておきましょう。
エッジ媒介中心性に基づくコミュニティ検出とQ値
これだけは『ネットワーク分析』にも載っているので、同書pp.81-86に沿って紹介しておきます。この方法論の発想としては「ネットワークの中で相対的に密度の高い部分をサブグループ（≒コミュニティ）として抽出する」というものであり、その指標を「凝集性」(cohesion / cohesivenss)と呼びます。その定義はグラフの隣接行列をとし、グラフ全体のノード数を
、サブグループ
に属するノード数を
とすると、
と書けます。これはサブグループ内のノード同士の関係密度と、サブグループ内のノードとサブグループ外のノードとの関係密度の比となっていて、これが1より大きければそのサブグループは外部と区別可能な凝集性を持っているとみなすことができるそうです。ただ、そこには当然閾値を決める必要があったり、色々と大変なようで。
そこで出てくるのが、エッジ媒介中心性に基づくコミュニティ検出です。エッジ媒介中心性とは、前回の記事でも取り上げた（ノードの）媒介中心性をエッジに適用したもので、あるエッジがノード間の最短経路上に存在する「程度」を指標化したものです。このエッジ媒介中心性の算出と、媒介中心性最大のエッジの除去を繰り返すことでグラフを分割し、凝集性の高いコミュニティを検出するというのがこの方法論のポイントです（同書p.82に詳細な説明があります）。{igraph}ではedge.betweeness.community関数で実行することができます。
> g2.eb.com<-edge.betweenness.community(g2,weights = E(g2)$value,directed = F) > g2.eb.com IGRAPH clustering edge betweenness, groups: 5, mod: 0.5 + groups: $`1` [1] 1 2 3 4 5 6 7 8 9 10 $`2` [1] 11 12 13 14 15 16 29 30 31 32 33 34 35 36 37 38 39 45 46 $`3` [1] 17 18 19 20 21 22 23 24 $`4` + ... omitted several groups/vertices > set.seed(25) > plot(g2,vertex.color=g2.eb.com$membership,layout=layout.fruchterman.reingold)
それっぽい結果に一見見えますが、よく見るとジャヴェールとマリユスとコゼットが同じコミュニティにいるのに、何故かヴァルジャンがシャンマチウとかと同じコミュニティにいてちょっとおかしな感じがしますね。
というのはここでは一旦置いといて、ここではそのコミュニティ分割の様子を見てみましょう。これは上記のアルゴリズムの概略からもピンと来た人もいるかと思いますが、やっていることはWard法などの階層的クラスタリングと似ています。つまり、デンドログラムを描いてどこかの閾値で切った結果というわけです。その様子は以下のように可視化できます。
> g2.dend<-as.dendrogram(g2.eb.com) > plot(g2.dend)
今回はedge.betweeness.community関数が決めたある適当な閾値で切られているわけですが、そもそもその閾値をどう評価すべきかが気になりますね。その評価指標として同書で紹介されているのがモジュラリティ(modularity)です。これは分割されたコミュニティ内のエッジの数と、コミュニティ間同士のエッジの数との比較により、コミュニティが高密度のサブグループをうまく抽出しているかどうかを示す指標です。詳細は同書pp.84-85をお読みいただくとして、モジュラリティ指標は、グラフが
個のコミュニティに分割されている時に
のコミュニティ間の関係を表す対称行列
を用いて、以下のように表せます。
{igraph}にはその名もズバリmodularity関数というモジュラリティ指標を算出する関数があるので、これで同書に示された方法同様にステップ0（1つのノードが1つのコミュニティの状態）からステップ77（全てのノードが1つのコミュニティに属している状態）までのQ値の変化を求めてみます。
> g2.Q<-rep(0,77) # 以下『ネットワーク分析』で用いられているcommunity.to.membership関数が # {igraph}から削除されているのでcut_at関数で代用した > for (i in 1:77){ + memb<-cut_at(g2.eb.com,i) + g2.Q[i]<-modularity(g2, memb) + } > plot(g2.Q,type='b') > which(g2.Q==max(g2.Q)) [1] 7
ステップ7の時がQ値が最大になることが分かりました。ということで改めてステップ7の場合のコミュニティ検出結果に合わせて可視化してみましょう。
> g2.eb.mb7<-cut_at(g2.eb.com,7) > set.seed(25) > plot(g2,vertex.color=g2.eb.mb7,layout=layout.fruchterman.reingold)
相変わらずヴァルジャンのコミュニティがおかしい気がするんですが（汗）、とりあえずもう少し『レ・ミゼラブル』の内容に近付いた結果になったかと思います。
ランダムウォークに基づくコミュニティ検出
以下竹本先生のサイトに天下り的に従ってやってみます。これは"Computing Communities in Large Networks Using Random Walks" (Pons & Latapy, 2006)によるアルゴリズムです。{igraph}ではwalktrap.community関数でいけます。
> g2.wt.com<-walktrap.community(g2,weights=E(g2)$value) > set.seed(25) > plot(g2,vertex.color=g2.wt.com$membership,layout=layout.fruchterman.reingold)
エッジ媒介中心性の時より少し良くなった気がしますが、まだしっくり来ない感じですねぇ。。。
貪欲アルゴリズムに基づくコミュニティ検出
これは"Finding community structure in very large networks" (Clauset, Newman, & Moore, 2004)によるアルゴリズムです。{igraph}ではfastgreedy.community関数でいけます。
> g2.fg.com<-fastgreedy.community(g2,weights=E(g2)$value) > set.seed(25) > plot(g2,vertex.color=g2.fg.com$membership,layout=layout.fruchterman.reingold)
これはこれで何か違う気がするんですよねぇ。。。
固有ベクトルに基づくコミュニティ検出
これは"Finding community structure in networks using the eigenvectors of matrices" (Newman, 2006)によるアルゴリズムです。{igraph}ではleading.eigenvector.community関数でいけます。
> g2.le.com<-leading.eigenvector.community(g2,weights=E(g2)$value) > set.seed(25) > plot(g2,vertex.color=g2.le.com$membership,layout=layout.fruchterman.reingold)
前のアルゴリズムより分割が多くなった気がするんですが、逆にストーリーからの逸脱が大きくなってるような。。。汗
多段階最適化に基づくコミュニティ検出
"Fast unfolding of communities in large networks" (Blondel et al., 2008)によるアルゴリズムです。{igraph}ではmultilevel.community関数でいけます。
> g2.ml.com<-multilevel.community(g2,weights=E(g2)$value) > set.seed(25) > plot(g2,vertex.color=g2.ml.com$membership,layout=layout.fruchterman.reingold)
これもなーんか違うんだよなぁ。。。
スピングラス法に基づくコミュニティ検出
"Statistical mechanics of community detection" (Reichardt & Bornholdt, 2006)によるアルゴリズムです。{igraph}ではspinglass.community関数でいけます。
> g2.sg.com<-spinglass.community(g2,weights=E(g2)$value,spins=15) # spins引数は最大分割数を示す > set.seed(25) > plot(g2,vertex.color=g2.sg.com$membership,layout=layout.fruchterman.reingold)
ようやくそれっぽくなってきました。実は以前『レ・ミゼラブル』の人物相関図単体で取り上げた時の記事と同じ結果がこれです。
きちんとマニョンという女の子供2人が別コミュニティに分かれ、シャンマチウと修道女たちとがごちゃごちゃになっていたのがきちんと分かれ、概ねストーリーに沿ったコミュニティ分割がなされています。
ラベル伝播法に基づくコミュニティ検出
"Near linear time algorithm to detect community structures in large-scale networks" (Raghavan, Albert & Kumara, 2007)によるアルゴリズムです。{igraph}ではlabel.propagation.community関数でいけます。
> g2.lp.com<-label.propagation.community(g2,weights=E(g2)$value) > set.seed(25) > plot(g2,vertex.color=g2.lp.com$membership,layout=layout.fruchterman.reingold)
一見より細かくなったように見えるんですが、テナルディエがヴァルジャンと同じコミュニティになってしまうなど変なところがチラホラ目に付きます。
Infomap法に基づくコミュニティ検出
"Maps of random walks on complex networks reveal community structure" (Rosvall & Bergstrom, 2008)によるアルゴリズムです。{igraph}ではinfomap.community関数でいけます。
> g2.im.com<-infomap.community(g2,e.weights=E(g2)$value) > set.seed(25) > plot(g2,vertex.color=g2.im.com$membership,layout=layout.fruchterman.reingold)
これがなかなか良くて、もしかしたらスピングラス法とどっこいぐらい『レ・ミゼラブル』のストーリーに忠実かもしれません。ただしポンメルシー夫人が何故かテナルディエの一味に入ってしまうなど、惜しいところも目に付きます。
どのハードクラスタリング・コミュニティ検出が良いか？
以上に取り上げたのは「全てのノードは必ずどれか1つコミュニティだけに属する」ハードクラスタリングタイプのコミュニティ検出なんですが、では一体どれが良いのでしょうか？ 一応竹本先生は"Community detection in graphs" (Fortunato, 2010)という総説を引いて「Q値最大化という意味ではスピングラス法が最も良さそう」とコメントされていますが、上記の論文を読みながら色々検討してみるのも良いかもしれません。個人的にはInfomap法が場合によってはスピングラス法よりも優れているかも？という印象を持ちました。
ソフトクラスタリング・コミュニティ検出：Link Community, Overlapping Cluster Generator
これは比較的新しい手法で、{igraph]ではなく{linkcomm}というパッケージで実装されています。要は読んで字の如く、「どのノードにも2つ以上のコミュニティに属することを許す」ようにしてコミュニティ検出を行う方法です。なお、{linkcomm}は{igraph}とは若干異なるクラス定義に依っているのでクラスを共有することは難しいのですが、おあつらえ向きなことに{linkcomm}にはそのものズバリ『レ・ミゼラブル』のデータが同梱されているので（笑）、これを使いましょう。
Link Communityの場合
これは"Link communities reveal multiscale complexity in networks" (Ahn, Bagrow & Lehmann, 2010)によるアルゴリズムです。{linkcomm}ではgetLinkCommunities関数でいけます。
> gl<-lesmiserables > gl.lc<-getLinkCommunities(gl) Checking for loops and duplicate edges... 100.000% Calculating edge similarities for 254 edges... 100.00% Hierarchical clustering of edges... Calculating link densities... 100.00% Maximum partition density = 0.5247315 Finishing up...4/4... 100.00% Plotting... Colouring dendrogram... 100% > plot(gl.lc) # これは実は自動プロットされる > plot(gl.lc,type='graph',margin=-0.5) Getting node community edge density...100% Getting node layout... Constructing node pies...100%
これは非常に面白い結果で、特に興味深いのがジャヴェールとパトロン・ミネットたちの分類。彼らは同時に幾つものコミュニティに関わっているのが『レ・ミゼラブル』本編を読めばよく分かるわけですが、それを反映するかのように非常に多くのコミュニティに少しずつ寄与しているという推定結果を示しています。
Overlapping Cluster Generator (OCG)の場合
これは"Multifunctional proteins revealed by overlapping clustering in protein interaction network" (Becker et al., 2012)によるアルゴリズムです。{linkcomm}ではgetOCG.clusters関数でいけます。
> gl.ocg<-getOCG.clusters(gl) Calculating Initial class System....Done Nb. of classes 43 Nb. of edges not within the classes 19 Number of initial classes 43 Running.... Remaining classes: None Reading OCG data... Extracting cluster sizes... 100% > plot(gl.ocg,type='graph')
Link Communityの時に比べて、さらにヴァルジャンのマルチコミュニティぶりが強調される結果になっています。一方で例えばトロミエスなど他のコミュニティに属しようがない人間はきちんと単一のコミュニティ内に封じ込まれ、他方ミリエル司教が共起した人物ごとのマルチコミュニティに分けられ、さらにはジャヴェールやテナルディエやマリウスのように幾つものコミュニティと関わりがありなおかつそれらに濃度差がある人物の推定結果がきちんと「いびつな」塗り分けられ方になっていて、実に面白いです。
最後に
というわけで、4回に渡ってグラフ・ネットワーク分析を取り上げてみました。正直、こういうデータセットって実務の現場でお目にかかることはあまり多くないんですが、確実にあるところには存在し、しかも往々にしてデータ分析を必要とする状況にあることは経験上よく知っているので、今回まとめるついでに勉強したことはしっかり覚えておこうと思います。
