WEKO3
-
RootNode
アイテム
階層的独立固有時間刻み法によるグラフ可視化計算の高速化
https://ipsj.ixsq.nii.ac.jp/records/17106
https://ipsj.ixsq.nii.ac.jp/records/1710698668f56-d75e-4045-aab3-a43c8226bf34
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TOM4815013.pdf (2.1 MB)
|
Copyright (c) 2007 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2007-10-15 | |||||||
| タイトル | ||||||||
| タイトル | 階層的独立固有時間刻み法によるグラフ可視化計算の高速化 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Hierarchical Individual Timestep Algorithm for Large Scale Graph-drawing | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | オリジナル論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 日本電信電話株式会社NTTコミュニケーション科学基礎研究所 | ||||||||
| 著者所属 | ||||||||
| 日本電信電話株式会社NTTコミュニケーション科学基礎研究所 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| NTT Communication Science Laboratories, NTT Corporation | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| NTT Communication Science Laboratories, NTT Corporation | ||||||||
| 著者名 |
松林, 達史
山田, 武士
× 松林, 達史 山田, 武士
|
|||||||
| 著者名(英) |
Tatsushi, MATSUBAYASHI
Takeshi, YAMADA
× Tatsushi, MATSUBAYASHI Takeshi, YAMADA
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本研究では，大規模なネットワークデータのための高速かつ効率的な可視化座標計算の手法を提案する．従来のネットワーク可視化手法の１つとして Fruchterman らによる力学モデルを用いる手法がよく知られている．彼らの手法はノード間やエッジに対し力学関数を与えることにより，系全体のエネルギーを定義し，加速度方向に各ノードの座標を更新することによって，系のエネルギーの極小状態を求める．この手法では座標の更新頻度は一様で，すべてのノードを毎回更新していたが，提案手法では階層的独立固有時間刻み法を用いて個々のノードに独立な更新時間を設定し，局所的に更新頻度を変えることにより計算の高速化を可能にした．この手法は，天体力学において用いられている局所的に密集した領域を精度良く計算する手法を，グラフ可視化手法に拡張したものである．また，提案手法は並列処理に適しており，粒子間相互作用専用並列計算機 MDGRAPE-3 PCI-X に実装することによって，計算速度の数百倍高速化が可能であることを示した．さらに，LGL（Large Graph Layout）法を用いた Opte Project の可視化結果との比較を行い，提案手法により高精度な可視化が可能であることを示した． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In this paper, we propose a fast and efficient method for drawing very large-scale graph data. The conventional force-directed method proposed by Fruchterman and Rheingold (FR method) is well-known. It defines repulsive forces between every pair of nodes and attractive forces between connected nodes on a edge and calculates corresponding potential energy. An optimal layout is obtained by iteratively updating node positions to minimize the potential energy. Here, the positions of the nodes are updated every global timestep at the same time. In the proposed method, each node has its own individual time and timestep, and nodes are updated at different frequencies depending on the local situation. The proposed method is inspired by the hierarchical individual timestep method used for the high accuracy calculations for dense particle fields such as star clusters in astrophysical dynamics. Experiments show that the proposed method outperforms the original FR method in both speed and accuracy. We implement the proposed method on the MDGRAPE-3 PCI-X special purpose parallel computer and realize a speed enhancement of several hundred times. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464803 | |||||||
| 書誌情報 |
情報処理学会論文誌数理モデル化と応用（TOM） 巻 48, 号 SIG15(TOM18), p. 126-136, 発行日 2007-10-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7780 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
