グラフ・ネットワーク分析で遊ぶ(1)：グラフ可視化・描画手法

ちょっと興味が湧いてきたので、今後しばらくグラフ理論・ネットワーク分析に力を入れてみようかなと思ってます。ということで『レ・ミゼラブル』の時同様にオープンデータセットを取ってきましょう。

• Network data

今回使うのは"Neural network"。これは（厳密には違うんですが）僕の以前の専門でもあった神経科学のデータで、C. elegansという線虫の神経回路網を測定・記録したものです。

Neural network: A directed, weighted network representing the neural network of C. Elegans. Data compiled by D. Watts and S. Strogatz and made available on the web here. Please cite D. J. Watts and S. H. Strogatz, Nature 393, 440-442 (1998). Original experimental data taken from J. G. White, E. Southgate, J. N. Thompson, and S. Brenner, Phil. Trans. R. Soc. London 314, 1-340 (1986).

上記リンク先のWikipedia記事にもあるように、C. elegansはこれほど小さい微生物であるにもかかわらず脳に相当するような中枢神経系を持っており、原始的ながら様々な神経系の性質に依存する行動を取ることも知られているため、神経科学研究のモデル動物としても盛んに用いられています。

ということで、この"Neural network"は297個のニューロンから成るC. elegansの「脳」内における神経細胞同士のつながりを記録したデータセットです。では、ちょこちょこ{igraph}とか使って遊んでみましょう。今回のお題は「グラフ可視化・描画手法」です。このシリーズのテキストはこちら。

ネットワーク分析 (Rで学ぶデータサイエンス 8)

この1冊にコンパクトにグラフ理論＆ネットワーク分析のエッセンスが詰まっているので、僕はいつも脇に置いて重宝させてもらってます。できれば他にももっとゴツいテキストないかなぁと思って洋書含めて探してるんですが、ゴツ過ぎて鈍器みたいなのばっかりでなかなか難しいようで。。。

グラフ・ネットワークは可視化するのが最も分かりやすい

どんなグラフというかネットワークも、はっきり言って可視化した方がどう見ても分かりやすいです。例えば以下のように{igraph}を用いてランダム生成したグラフを見てみましょう。

> library(igraph)
> g<-erdos.renyi.game(8,3/8,directed=T)

下のように隣接行列だけ見ても何が何だか分かりづらいですが、

	1	2	3	4	5	6	7	8
1	.	1	.	.	.	1	.	1
2	.	.	.	.	1	1	.	.
3	1	.	.	1	.	.	.	1
4	.	.	.	.	1	1	1	.
5	.	.	1	.	.	1	.	.
6	.	1	1	.	.	.	1	.
7	.	.	.	.	.	.	.	.
8	.	.	1	1	1	.	.	.

これをグラフ描画で可視化してやれば一目瞭然かと。

ということで、グラフ・ネットワークの基本のきであるデータ表現と、その可視化の話を今回はおさらいしていこうかと思います。

グラフは隣接行列がエッジリストで表す

そもそも「グラフ」と言った場合、何かしらの「頂点（ノード）」(vertex / node)から別の頂点へと伸びる「辺」(edge)の集合体からなるデータを基本的には指します。これをどう表現するかというのは色々流儀があって、例えば上に既に例の出ている「隣接行列」(adjacency matrix)であれば「行→列」なる関係性で表します。

> x<-get.adjacency(g)
Loading required package: Matrix
> x
8 x 8 sparse Matrix of class "dgCMatrix"
                    
[1,] . 1 . . . 1 . 1
[2,] . . . . 1 1 . .
[3,] 1 . . 1 . . . 1
[4,] . . . . 1 1 1 .
[5,] . . 1 . . 1 . .
[6,] . 1 1 . . . 1 .
[7,] . . . . . . . .
[8,] . . 1 1 1 . . .

ただし隣接行列はグラフの規模が大きくなるとデータとしてはかなり重くなることが予想されます。でかいデータが相手だとつらいことが多いのも事実です。

これに対して「ある頂点→別の頂点」なるデータの集合として表したのがエッジリストで、{igraph}なら以下のようにして取得できます。

> y<-get.edgelist(g)
> y
      [,1] [,2]
 [1,]    1    8
 [2,]    3    1
 [3,]    1    2
 [4,]    6    2
 [5,]    3    8
 [6,]    5    3
 [7,]    6    3
 [8,]    8    3
 [9,]    3    4
[10,]    8    4
[11,]    2    5
[12,]    4    5
[13,]    8    5
[14,]    1    6
[15,]    2    6
[16,]    4    6
[17,]    5    6
[18,]    4    7
[19,]    6    7

ちなみに逆にgraph.edgelist関数を使えばエッジリストのデータ（マトリクスで良い）からグラフデータ構造を作れるので、前処理なんかを考えてもエッジリストで全部やり取りした方が多分効率的です。

とりあえず単純にグラフ可視化＝グラフ描画してみる

普通にlayout {igraph}のヘルプを見るとこんな感じでズラッと描画アルゴリズムのオプションが出てくるんですが（笑）、多分全部使うことはないと思うので主要なものだけ抜粋して紹介しておきます。

layout.auto(graph, dim=2, ...)
layout.random(graph, params, dim=2)
layout.circle(graph, params)
layout.sphere(graph, params)
layout.fruchterman.reingold(graph, ..., dim=2, params)
layout.kamada.kawai(graph, ..., dim=2, params)
layout.spring(graph, ..., params)
layout.reingold.tilford(graph, ..., params)
layout.fruchterman.reingold.grid(graph, ..., params)
layout.lgl(graph, ..., params)
layout.graphopt(graph, ..., params=list())
layout.svd(graph, d=shortest.paths(graph), ...)
layout.norm(layout, xmin = NULL, xmax = NULL, ymin = NULL, ymax = NULL,
      zmin = NULL, zmax = NULL)

上の方でランダム生成したグラフgを描画し、ランダムシードは予めset.seed(71)に固定しておきます*1。まず、一般にグラフ・ネットワークの可視化というと馴染み深いのが円形グラフ。これはどのノードがどれくらいのエッジを集めているかが分かりやすく、また目視レベルでもいわゆるスモールワールド性を判断しやすい描画方法です。

> set.seed(71)
> plot(g,layout=layout.circle)

次に、いわゆる力指向グラフ描画アルゴリズムと呼ばれるものを2つ。Wikipedia日本語版記事にはこのように概説されています。

力学モデルによるグラフ描画（力指向アルゴリズム）は、グラフを美しく描画するためのアルゴリズムの一つである。 このアルゴリズムは、グラフのノードを2次元空間や3次元空間に配置して、辺の長さをほぼ等しい長さにし、グラフの辺ができるだけ交差しないようにすることを目的にしている。

このアルゴリズムでは、グラフの頂点と辺に仮想的な力を割り当て、力学的エネルギーの低い安定状態を探すことで、この目的を達成している。もっとも直截的なモデルでは、それぞれの辺をフックの法則にしたがうばねとみなし、それぞれの頂点をクーロンの法則にしたがう電荷をもつ粒子とみなす。 そして、その力学系の挙動をシミュレートし、弾性力や静電気力が粒子を近づけたり遠ざけたりするようすを計算する。粒子が安定な配置になり、位置が変化しなくなるまで、力の計算と粒子の移動を繰り返す。その時点で、グラフのレイアウトが完了し、描画される。この平衡状態は、すべての力が釣り合った状態に相当する。

ということで、力指向グラフ描画アルゴリズムを用いることで、グラフをより美しく、なおかつある程度直感的に理解しやすく描画することができます。ここで言う「直感的な理解」とは、例えば今後の記事で紹介する予定の中心性(centrality)や経路長といった指標とグラフ構造との関係性についての理解を含んでいます。

で、1つ目はFruchterman - Reingoldアルゴリズム。91年の原典論文が公開されている*2ので厳密な詳細はそちらをお読みください。アルゴリズムの性質としては「エッジでつながっているノードほど近くに描画する」*3「同時にあまりノード同士を近付けさせない」という2つのルールに従うようです。また高速化にも配慮したアルゴリズムだと論文中では述べられていますね。描画結果はこんな感じになります。

> set.seed(71)
> plot(g,layout=layout.fruchterman.reingold)

2つ目はKamada - Kawaiアルゴリズム。こちらも89年の原典論文が公開されているので厳密な詳細はそちらを。概ね、ノード間の距離が最短経路長に従い、なおかつ事前に初期値の最適化を行うということのようです。描画結果はこんな感じになります。

> set.seed(71)
> plot(g,layout=layout.kamada.kawai)

なお、Wikipedia記事にもあるようにこの2つのアルゴリズムはそれぞれ得手不得手があり、Kamada - Kawaiは初期値の設定に優れ、Fruchterman - Reingoldは隣接ノードの配置に優れると言われるようです。そこで、こんな感じに実行した結果がこちら。

> set.seed(71)
> plot(g,layout=layout.kamada.kawai)
> plot(g,layout=layout.fruchterman.reingold)

先にKamada - Kawaiで初期値を作ってやり、これをFruchterman - Reingoldで巧みに動かす、みたいな流れなんだそうです。でもこのやり方でうまく行ってるのかなぁ。。。

C elegansのデータを可視化してみる

ということで、ここでようやく冒頭に紹介したC elegansのデータを可視化してみようかと思います。ZIP形式のデータで、解凍すると"celegansneural.gml"というファイルが出てくるので、read.graph関数でGMLフォーマットを指定して読み込みます。

> g<-read.graph("celegansneural.gml",format="GML")
> set.seed(71)
> plot(g,layout=layout.kamada.kawai)
> plot(g,layout=layout.fruchterman.reingold,vertex.size=5,edge.arrow.size=0.3)

こんな感じで、何やら意味ありげなデータ構造を伴うグラフとして描画されました。いやもちろんこれはある程度知覚刺激に対応した行動を取る動物の神経ネットワークなので、何かしらの意味ある構造を持っていて当然なのですが、それがきちんと目で見て分かるように描画できるというのは良いですね。

ということで、今後しばらくこんな感じでだらだらとグラフ・ネットワーク分析まわりを復習しつつ色々学んでいこうかと思います。

*1:別に魔法のランダムシードというわけではありません笑

*2:ただし何故かftp

*3:これは副作用としてノード間の距離が最短経路長に比例する傾向を持つ、という性質につながっているようです