著者

松林 達史 山田 武士

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.48, no.SIG15(TOM18), pp.126-136, 2007-10-15

---

本研究では,大規模なネットワークデータのための高速かつ効率的な可視化座標計算の手法を提案する.従来のネットワーク可視化手法の1つとして Fruchterman らによる力学モデルを用いる手法がよく知られている.彼らの手法はノード間やエッジに対し力学関数を与えることにより,系全体のエネルギーを定義し,加速度方向に各ノードの座標を更新することによって,系のエネルギーの極小状態を求める.この手法では座標の更新頻度は一様で,すべてのノードを毎回更新していたが,提案手法では階層的独立固有時間刻み法を用いて個々のノードに独立な更新時間を設定し,局所的に更新頻度を変えることにより計算の高速化を可能にした.この手法は,天体力学において用いられている局所的に密集した領域を精度良く計算する手法を,グラフ可視化手法に拡張したものである.また,提案手法は並列処理に適しており,粒子間相互作用専用並列計算機 MDGRAPE-3 PCI-X に実装することによって,計算速度の数百倍高速化が可能であることを示した.さらに,LGL(Large Graph Layout)法を用いた Opte Project の可視化結果との比較を行い,提案手法により高精度な可視化が可能であることを示した.