■アルゴリズムによる高速化
引力と斥力に分ける
|
従来のグラフ可視化の計算では，Kamada & Kawai (1989)によるバネモデルが広く用いられてきた．
例えばgraphvizなどのアプリケーションで使われている．しかしながらこの手法では，ノード間の
最短パスをあらかじめ求める必要性があり，大規模なネットワークデータでは莫大な計算量と物理
メモリを要求し計算が不可能になる．
Fruchterman & Raingold (1991)は，エネルギー関数をノードの接続情報（エッジ）とノード間の
反発力に分けて考えることによって上記の問題を解決した．しかしながらノード間の計算には未だ
莫大な計算量が必要であるため，Tree-codeを使ったFADEなどが提案されている．
我々の研究ではこのFruchterman & Raingold の手法を元に，階層的独立固有時間刻み法による
高速化手法や，さらに並列処理ボードを用いた計算の高速化に関して研究を行っている．
■並列処理による高速化
|
|
Asia Pacific - Red
Europe/Middle East/Central Asia/Africa - Green
North America - Blue
Latin American and Caribbean - Yellow
RFC1918 IP Addresses - Cyan
Unknown - Gray
|
左図は、左がLGL法によるClassC のIPネットワークの可視化図。
tracerootコマンドで得られた13万ノードのネットワークを、LGL法を用いて可視化したものであり、
計算時間にはおよそ5時間ほど要する。
一方右図は我々の手法（独立固有時間刻み法）を用いて計算を行った手法。
近似手法と異なり、圧倒的に精度良く計算が行われているのが分かる。
なお、我々の手法ではMDGRAPE3 PCI-Xを用いておよそ5時間強であった。
近似手法にも限界があり、このような性質のネットワークには、少なくともLGL法は不向きであり、
我々のような並列処理を有効に利用した手法を行う必要がある。
また，近年ではGPUによる計算の高速化に関する研究も行っており，左のムービーはGPUによる処理を行った．
当研究チームには、共通計算機として60ノードを越えるXeonマシン（理論性能値 5Tflops メモリ1.5TB）のPCクラスタがあり、
さらに、マルチGPUPCや、大容量メモリPC(4CPU 16-core 128GBmemory)を8ノード(理論性能値 1Tflops メモリ1TB)もあります．
■ラベル付きグラフ可視化
ラベル付きネットワークの可視化例
|
一般的なグラフ可視化においてはネットワークの関連性を元に，２次元もしく
は３次元のユークリッド空間にノードを「点」として，エッジを点と点を繋ぐ
「直線」として投影し描画する．しかしながら，各ノードが固有情報，例えば
ノードの名称や画像などを持ち，これらをノード上に直接文字列あるいは縮小
版画像として埋め込みたい場合もある．これらの場合は，ノードは
「点」ではなく大きさを持つ「ラベル」として描画する必要がある．
従来のラベル付きグラフ可視化の座標計算アルゴリズムは Force-directed 法
やバネモデルといった，ノードを「点」として扱う座標計算を行うために，文
字列や，異なるサイズのラベルを扱う時にはラベル同士が重なってしまうと言
う問題が生じる．
ラベルの重なりを回避する手法はいくつか提案されて来たが，いずれの手法も
可視化計算を行った後に，再び座標計算処理を必要とする．これ等の手法では
大規模なグラフ可視化では計算量が莫大になり，さらに元の可視化結果を破壊
してしまうという問題も生じる．
我々の提案手法では，各ノードにラベルサイズに依存した固有楕円ポテンシャルを
与え，ラベルの大きさを考慮する事によって，ラベル同士の重なりを回避する
座標計算を可能とした．さらに，斥力項に対し点対称ポテンシャルと固有楕円
ポテンシャルの関数の重ね合わせることにより，メンタルマップを保ちつつ局
所的にはラベルの重なりを回避する手法を提案した．
左は我々の固有楕円ポテンシャル法(Individual Ellipsoidal Potentail
method)による座標計算ムービーです．
■まっしゅるーむ
システム構成図のひとつ
|
「環境知能」は、環境に潜む知能、あるいは、知能が埋め込まれた環境、のことを指します。環境に潜む知能は、私たちの暮らしに潜む妖精・妖怪であり、この妖精・妖怪を「環境知能」プロジェクトでは「まっしゅるーむ」と呼んできます。また、知能が埋め込まれた環境は、妖精・妖怪すなわちまっしゅるーむの棲む世界のことであり、これを「まっしゅルーム」と呼んでいます。そのうちのひとつ「ふーふーくん」のシステムにグラフ可視化の技術が利用されています。
■BLOGRANGER TG
現在サービス中のタグクラウド地図．
ただし画像は2008年5月現在のもの．
|
広域図
|
``BLOGRANGER TG''とは，ＮＴＴサイバーソリューション研究所とＮＴＴコミュ
ニケーション科学基礎研究所が共同で研究を進めているプロジェクトであり，
2007年12月よりgooラボにて公開されている，タグクラウド・ブログ地図である．
このプロジェクトでは，従来のタグクラウドのように順番に羅列するのではな
く，類似性を持ったタグ同士をノード間の類似度を基準に,関連性の高いもの
近傍に配置するように２次元可視化計算を行い配置したものである．
左図は現在サービス中のタグクラウド地図である．
ただし画像は2008年5月現在のものである．
左上に全体の広域図が表示され，中央に一部分の広域図が示されている．
このグラフデータは，ノード数約5000の規模を持つ，重みつきの無向グラフであり，
各エッジに類似度が与えられている．
このプロジェクトにおいては，各ノードが重ならず，かつラベルの密集を防ぐ
ため、"固有楕円ポテンシャルを用いたラベル付きグラフ可視化の座標計算手法"
を用いている。
■Topigraphy Project
3D Topigraphy
 
Topigraphy Project on OpenGL (c)NTT corp. Tatsushi Matsubayashi.
|
左の立体地形図は，BLOGRANGER TG で行ったトピック地形図表現(Topigraphy)を，
OpenGLを用いて3D表現したものです．
フルスクリーンモードと，NVIDIAの3D vision を用いることによって，
立体視することも可能です．
実際のデータはWikipediaの人名ネットワークを用いたが，
このように様々なデータで，我々の提案するTopigraphyの表現が可能である．
Mobile Topigraphy
Topigraphy 可視化ツールをAndroid端末にも実装しました．
詳しくはポスターページを
■Realtime Graph Drawing
CC総研のHPでも紹介されています
|
