第2回にして既にUCIのデータセットではないんですが（笑）、ちょっと自分の練習も兼ねてご紹介。今回はグラフというかネットワークがお題です。ぶっちゃけ僕自身はグラフ理論＆ネットワーク分析は全くもって真面目に勉強してないので、炎上ラーニングも兼ねて全力でマサカリ投げていただけると嬉しいです。ということで、ネタ元はUCI ML repositoryではなく、こちら。
この中にある『レ・ミゼラブル』の人物相関図のネットワークデータです。
Les Miserables: coappearance network of characters in the novel Les Miserables. Please cite D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing, Addison-Wesley, Reading, MA (1993).
『レ・ミゼラブル』は僕も若い頃愛読した小説なのでよく知ってますが、ヴィクトル・ユーゴーの徹底したリアリズムを反映してかとにかく描写が細かいんですよね。時代背景についての解説がたっぷりついた後にようやく本編に入る上に、本編は本編で色々伏線は張られてるし教養小説の常として登場人物も多い。
その登場人物たちの"coappearance"つまり同時に登場する度合いを表したのがこのデータセットということのようです。ちなみに提供元は何とあのKnuth御大。。。というかこの本知りませんでした（汗）。
このデータのファイルであるlesmis.zipですが、解凍するとlesmis.txtとlesmis.gmlの2つのファイルに分かれます。lesmis.txtはデータの説明、lesmis.gmlはGML形式のネットワークデータで、{igraph}パッケージのread.graph関数で読み込むことができます。
> library(igraph) > g<-read.graph("lesmis.gml",format="gml") > g IGRAPH U--- 77 254 -- + attr: id (v/n), label (v/c), value (e/n)
idはノードID、labelは登場人物名、そしてvalueは要は重み付け（同じ章の同じ場面に同時に現れた回数らしい）です。では、これをちょっと料理してみましょう。
> g.bw<-betweenness(g,directed = F,weights = E(g)$value) > g.com<-spinglass.community(g,weights = E(g)$value,spins = 50)
今回は登場人物同士の関係性に興味があるので、ノードの特徴量に注目してみました。ここで使うのは媒介中心性(betweeness centrality)と、スピングラス法によるコミュニティ検出で得られるコミュニティ分類。
媒介中心性は、きちんとした説明が上のWikipedia記事に出ていますが*1、端的に言えば「ネットワーク上でボトルネックになる度合いの強さ」を示した量。そのノードが消滅するとその先に続いているノード群へつながらなくなってしまうため、一種のハブ的側面を反映する特徴量だとも言えそうです。
「コミュニティ検出」と言った場合、ネットワーク分析ではノードのクラスタリングのことを指すことが多いようです。スピングラス法は、その中でも統計物理*2に基づく方法でクラスタリングしていく手法であるとのこと。元論文がarXivに上がっているので、興味のある方はお読みください。なお、{igraph}の解説記事で有名な九大の竹本先生は数あるコミュニティ検出手法の中でこの手法をお薦めされています。
ということで、これで大体重要なノード特徴量は分かりました。では、これらを活かして可視化してみましょう。可視化というかグラフ描画には力学的描画アルゴリズムを用います。僕が好んで使うのはFruchterman-Reingoldアルゴリズム。元論文も公開されていますが、端的に言うと「関係性の近いノード同士ほど描画グラフ上でも近い位置に配置される」*3アルゴリズムです。
> plot(g,vertex.size=log10(g.bw+10)*5,vertex.color=g.com$membership,layout=layout.fruchterman.reingold,margin=-0.3)
ノード(vertex)のサイズが媒介中心性の大きさに関連するように、ノードの色がコミュニティ分類を表すように、プロットしてみました。ちなみにtkplot関数を使うとインタラクティブにノードの位置をマウスでクリック＆ドラッグして動かせます*4。
で、見てみると。。。意外にもちゃんと主人公ジャン・ヴァルジャンのグループ、著者ユーゴーがモデルとも言われる第2の主人公・マリユスのグループ、第1章に出てくる聖者・ミリエル司教のグループ、第1章のみの登場ながら重要な伏線となる悲劇の女性・ファンティーヌのグループ、第4章でバリケードのリーダーとなる革命家・アンジョルラスのグループ、そして第2章以降を引っかき回し続ける悪党・テナルディエのグループ*5がきちんと分類されているのが分かります。
面白いのがジャヴェール警部。ある意味浮いた存在だからかも＆ずっと一緒に登場するからかもですが、ジャン・ヴァルジャンのグループに属してるんですね。そしてバマタボワという、娼婦に堕したファンティーヌが逮捕されるきっかけになるいざこざを起こした相手の男が地味～に小さなグループを形成しているのも興味深いです。
そして一番凄いと思ったのが、マニョンというジルノルマン氏（マリユスの祖父）を強請って生活費を受け取っていた強欲な女の位置。グラフ上ではマリユス・ジルノルマン氏を初めとしたジルノルマン家の近くに配置されているのですが、コミュニティとしては彼らのグループ（ジャン・ヴァルジャンも含む）ではなくしっかり本文中でも触れられている通りにテナルディエのグループに分類されているんですね～。これは面白いです。
ちなみにそのマニョンがテナルディエ家から引き取った2人の子供は、面倒を見ていたガヴローシュ（テナルディエの実の息子にして浮浪児でアンジョルラスのグループに加わって蜂起に加担する）から伸びる独立したコミュニティに属していて、これもまた興味深いです。
という感じで、たかだか人物のcoappearanceを見るだけでもこれだけ小説の本文の内容に沿った関係性が可視化できるということがよく分かりました。実際にビジネスの場で展開されるソーシャルグラフ・データセットなどを用いるともっと面白い結果になることもあるのですが、その話はまた改めて（笑）。
