力学モデルを用いた階層型グラフデータ画面配置手法の
改良手法とウェブサイト視覚化への応用
土井 淳 伊藤 貴之*
日本アイ・ビー・エム(株) 東京基礎研究所
(* 京都大学情報学研究科と兼任)
An Improvement of Force-directed Hierarchical Graph Layout
And Its Application to Web Site Visualization
Jun DOI Takayuki ITOH
IBM Research, Tokyo Research Laboratory
[email protected], [email protected]
グラフデータの視覚化技術は，近年活発に研究が進められており，金融・交通・通信・社会組織・科学・計算機システム・ インターネットなど，非常に幅広い分野のデータ分析およびデータ監視の目的での実用が報告されている．グラフデータの視 覚化における最も大きな問題は，「グラフを誤読させない適切なノードの画面配置を，自動的に実現する」という問題である． この問題を解決するために，ノードに分子間力モデル，アークにバネモデルを適用して，運動方程式によって良質なノード配 置結果を得る手法が提案されている． 本論文では，上記のような「力学モデルを用いたグラフデータの画面配置手法」の改良手法および階層型グラフデータへの 拡張手法を提案する．本手法は，ノードを１個ずつ配置するインクリメンタルなアルゴリズムにより，配置結果を改善すると ともに，計算時間の増加を抑えることに成功している． また本論文では，上記手法を用いたウェブサイトの視覚化結果を提示する．本手法では，ウェブサイトを構成するウェブペ ージをノード，ウェブページ間のハイパーリンクをアークとして，またウェブページのディレクトリ階層を参照してウェブペ ージを階層型データに格納することにより，ウェブサイトを階層型グラフデータとして表現する．この階層型グラフデータを 上記手法により画面配置し，個々のウェブページをサムネイル画像で表示することにより，ウェブサイトの全体像を表現する．1. はじめに
グラフデータのグラフィックス表示技術は，非常に 幅広い分野のデータ分析およびデータ整理に有用であ る．最近では， ¾ ウェブサイトのリンク構造の表示． ¾ 金融・通信・交通・社会組織などの各種ネットワ ークの表示． ¾ 化学・生物などのサンプリングデータの傾向理解 のために，データを関連性で連結したグラフの表 示． ¾ テキストデータや画像データの整理のために，デ ータを関連性で連結したグラフの表示． ¾ 例えば並列計算機のプロセスなどのように，関連 あるモジュールの集合で構成されるシステムの 振舞いを表したグラフの表示． などの分野での実用例が報告されている．また，グラ フデータ視覚化のための基礎技術については，近年に なって有用な解説書やサーベイ論文が出版されている [1] [2]． グラフデータの視覚化における最も大きな問題は， 「グラフを誤読させない適切なノード画面配置を，自 動的に実現する」という問題である．この問題を解決 するために例えば， [条件 1] 近隣ノードが一定以上の距離を保つことにより，ノードどうしの画面上の重なりを避ける． [条件 2] アークの長さの総和をできるだけ短くして， アークで連結されたノードをお互いに近い位置に配置 する． [条件 3] アークどうしが交差しないようにする． [条件 4] アークが端点以外の場所で別のノードと重な らないようにする． などの条件（図 1 参照）を最大限満たすような配置結 果を算出する手法が多く報告されている． 上記の問題に対して，多くの視覚化アプリケーショ ンが求めている要件は，「最適でなくてもいいから，誤 読を防ぐことのできる最低限以上の配置結果を，高速 に求める」ことである．この「最低限以上の結果」を 「高速に求める」というトレードオフ的な条件に対し て，比較的バランスのとれた手法として，グラフのノ ードに分子間力モデル，グラフのアークにバネモデル を用いて，運動方程式を解くことによって各々のノー ドの適切な位置を算出する手法（図 2 参照）が知られ ている．しかし，この手法にしても，2 章にて後述する とおり，いくつかの課題を残している． 本論文では，分子間力モデルやバネモデルなどの力 学モデルを用いたグラフ配置に関する改良手法を提案 する． 本論文が提案する改良手法は，処理開始時から すべてのノードを配置する従来手法と異なり，１個ず つインクリメンタルにノードを配置する．このアルゴ リズムにより本手法は，「ノードの配置結果が初期配置 に大きく依存する」という問題を改善するとともに， 力学モデルの計算を局所化することで，従来手法より も高速なノード配置を実現する． 続いて本論文では，上記手法を階層型グラフデータ の画面配置に応用するアルゴリズムも提案する．ここ で階層型グラフデータとは，グラフを構成するノード に階層構造を設けた上で，ノード間を連結するアーク を設けたグラフデータを指す． さらに本論文では，上記手法を用いたウェブサイト の視覚化結果を提示する．本手法では，ウェブサイト を構成するウェブページをノード，ウェブページ間の リンクをアークとして，またウェブページのディレク トリ階層を参照してウェブページを階層型データに格 納することにより，ウェブサイトを階層型グラフデー タとして表現する．この階層型グラフデータを上記手 法により画面配置し，個々のウェブページをサムネイ ル画像で表示することにより，ウェブサイトの全体像 を表現する．
2. 関連研究
2.1. グラフデータの視覚化手法
グ ラ フ デ ー タ の 視 覚 化 手 法 は 1980 年 代か ら 広 く 研 究 が 進 ん で お り ，そ の 歴 史 と 構 成 は い く つ か の サ ー ベ イ 文 献 [1][2]に 要 約さ れ てい る ．1 章 に て， 分 子 間 力 や バ ネ モ デ ル な ど の 力 学 モ デ ル を 適 用 し た グ ラ フ デ ー タ 視 覚 化 手 法 に つ い て 述 べ た が ， こ れ も [3]に 代 表 さ れ る よ う に ， 1980 年 代 か ら 研 究 が 進 ん で い る ．こ の 手 法 は 1 章 であ げ た条 件 の う ち ，主 に [条件 1][条件 2]を 満 たす た めの 視 覚化 手 法 で あ る と い え る ． ま た 一 般 的 に ， [条 件 2]を 満 た す こ と が で き れ ば ， 同 時 に [条 件 3]を 満 た す 可 能 性 が 高 い ． こ の 力 学 モ デ ル を 用 い た 視 覚 化 手 法 に は ，以 下 の よ う な 問 題 点 が 指 摘 さ れ て い る ． 図 1 グラフデータ画面配置の典型的な条件 [条件 1] ノード同士の重なりを避ける [条件 2] アークの長さの総和を小さくする [条件 3] アーク同士の交差を避ける [条件 4] アークとノードの重なりを避ける 斥力 引力 図 2 力 学 モ デ ル の グ ラ フ デ ー タ 配 置 へ の 適 用• 対話的に処理ができるほど高速ではない．特に大 規模なグラフデータにおいて，非常に大きな計算 時間を要する． • ノードの配置結果が初期配置に大きく依存する にもかかわらず，適切な初期配置を決める方法が ない． • アークとノードの重なりを小さな計算時間で解 消する有効な方法がない．つまり 1 章で示した[条 件 4]を満たすことが難しい． こ れ ら の 問 題 点 を 解 消 す る た め に ，近 年 に な っ て 力 学 モ デ ル を 用 い た グ ラ フ デ ー タ 視 覚 化 手 法 に は 多 く の 改 良 手 法 が 提 案 さ れ て い る ．例 え ば 文 献 [4]で は ， 10 万 個 以 上 の ノ ー ド を も つ 巨 大 な グ ラ フ デ ー タ へ の 適 用 が 試 み ら れ て い る ．ま た 文 献 [5] で は ，ア ー ク ど う し の 交 差 を 減 ら す こ と に 主 眼 を お き な が ら ，同 時 に 適 切 な ノ ー ド の 配 置 を 実 現 し て い る ．ま た 文 献 [6]で は，ボロ ノ イ図 を 参照 し な が ら 力 学 モ デ ル を 適 用 す る こ と で ，ノ ー ド の 配 置 密 度 を 改 善 し て い る ． 本 論 文 の 3 章で 提 案し て いる イ ンク リ メン タ ル な ノ ー ド 配 置 手 法 に 類 似 す る 手 法 と し て ， 文 献 [7][8]などの従来手法がすでに報告されている．しかし これらの手法は，すでに部分的に配置されているグラ フデータに対して，局所的な追加・削除・修正を行う ことで，グラフデータのナビゲーションを実現するも のであり，グラフデータ全体の画面配置の高速化を目 的とするものではない． 本論文の 4 章で提案している階層型グラフデータ視 覚化手法の一環として，階層にあわせてグラフデータ を立体的に視覚化する手法や，その一部をズーム操作 する手法が提案されている[9][10]．しかしこれらの手 法も，階層型グラフデータ全体を 2 次元平面に高速配 置する本論文の提案手法とは目的が異なる．
2.2. ウェブサイトの視覚化手法
ウェブサイトの視覚化手法の多くは，ウェブサイト を構成するウェブページ群を一覧表示する．最も多く 見られるウェブサイト視覚化手法は，ウェブページを ディレクトリ階層またはトップページからのリンク構 造で階層化して表現する手法である．ウェブサイトの 階層構造を表現するサイトマップの典型的な例として， Inxight 社 が 公 開 し て い る ユ ー ザ ー イ ン タ フ ェ ー ス [11] がある．この手法は，Hyperbolic Tree [12] という 木構造データ視覚化手法を応用して，トップページを 根にしたウェブサイトの階層構造を表現しており，ユ ーザーの対話操作に連動した局所ズームによる詳細表 示を実現している．また，Durand らが提案した MAPA [13] も，ウェブページを階層構造にしたがって縦横に 並べる表現を用いており，ユーザーの対話操作にした がって段階的にかつ選択的にウェブページ群を表示で きる．また山口らは，長方形の入れ子構造を適用した 階層型データ視覚化手法を用いて，ウェブサイトのア クセス統計を視覚化する手法を提案している[14]． 一方，ウェブページ群をノード，ウェブページ間の ハイパーリンクをアーク，に変換することで構築され るグラフを視覚化する手法も多く提案されている．一 例として，力学モデルを用いてグラフ構造を 3 次元空 間に自動配置する手法を，ウェブサイトのリンク関係 の視覚化に適用した手法が報告されている [15]．一方， 自動配置ではなく対話的操作によってグラフ構造を理 解させる視覚化手法も多く知られている．塩澤らは， あらかじめ平面上に配置されたノードを持ち上げる操 作によって，特定のウェブページのリンク関係を対話 的に視覚化する手法を提案している [16]．これらの手 法はいずれも 3 次元空間上にウェブページ群を配置し ており，2 次元平面上にウェブページ群を配置する本論 文の提案手法とは大きく異なる．3. 力学モデルを用いたインクリメンタ
ルなノード配置の提案
3.1. 本手法で適用する力学モデル
本手法では，グラフのアークにバネ力，ノードに分 子間力を想定し，運動方程式を用いてアークの安定長 およびノード間の安定距離を求める．以下の説明では， 対象となる 2 個のノードを分子中心点として，「分子と しての半径の総和」に対する「ノード中心点間の距離 (またはアークの長さ)」の比を d とする．またすべての 分子は等しい半径をもつものとする． 本手法では，以下の式を用いて，アークで連結され た 2 個のノード間の斥力（または引力）F を求める（図a 3(左)参照）．⎩
⎨
⎧
−
−
−
−
=
)
0
.
1
(
)
0
.
1
(
D
k
d
k
F
a) ...( ) ...( D d D d ≥ <
ここで
k ,
D
は定数であり，D>1.0であるとする． この式はフックの法則によるバネモデルに類似してい るが，本手法では計算の発散を防ぐために，アーク長 が十分長い (d ≥D) ときに力の大きさが一定である という条件を加えている． また本手法では，以下の式を用いて，アークで連結 されていない 2 個のノード間の斥力F を求める（図b 3(右)参照）． ⎪⎩ ⎪ ⎨ ⎧ − + = 0 ) 8 9 8 19 4 5 ( d3 d2 k Fb ) 0 . 1 ...( ) 0 . 1 0 . 0 ...( ≥ < ≤ d d ここで k は定数であるとする．この式は，分子間力 モデルの一つであるファン・デル・ワールス力を 3 次 関数で近似したもの [17] であるが，本手法では引力は 不要なのでd
≥
1
.
0
のときに斥力をゼロとしている． 本 手 法 で は ，ノ ー ド を １ 個 ず つ 画 面 空 間 に 配 置 し ，す で に 配 置 さ れ て い る ノ ー ド 間 の 引 力 お よ び 斥 力 を 算 出 す る ． こ こ で ， i 番目のノードにかかる 力の合計をF ，位置をi x ，ノ ー ド の 質 量 をim
，ダ ン ピ ン グ 係 数 をc
とすると，下 記 の 運 動 方 程 式 i i icx
F
mx
'
'
+
'
=
の 反 復 演 算 に よ っ て ，ノ ー ド の 安 定 な 位 置 を 求 め る こ と が で き る ．3.2. インクリメンタルなノード配置による力
学計算の局所化
すでにいくつかのノードが配置されている図 4(a)の ような状態から，１個のノード N を追加することを0 考える．本 手 法 で は ， 以 下 の よ う な 方 法 で 力 学 計 算 を 局 所 化 し ，計 算 時 間 の 増 加 を 抑 え る ．まずN0 だけに「変位中」のフラグを立てる（図 4(b)参照）．続 いて， • 変位中ノードとアークで連結されたノード • 変位中ノードとアークで連結されていないが，十 分近い距離にあるノード のみに対して力を算出し，その力の総和を運動方程式 に代入して，ノードの新しい位置を計算する．移動量 が大きいノードについては，「変位中」のフラグを立て なおし（図 4(c)参照），「変位中」のノードに対して力 を算出する（図 4(d)参照）．続いて，この力の総和によ って再びノードの新しい位置を計算し（図 4(e)参照）， 同様に力を算出する（図 4(f)参照）．この処理の反復に より，本手法では力学モデルの計算を局所化し，計算 時間の増加を抑える． 筆者らの実装では，力学計算の反復の各ステップに て，ノードの分子半径の 0.5 倍以上の移動量を有する ノードに対してフラグを立てる．そしてフラグの立っ ているノードが全くなくなったときに，力学モデルの 反復計算が収束した，と判断する．この「分子半径の 0.5 倍」という数字には理論的根拠はなく，筆者自身に よる観察から経験的に決めている．筆者らの実装では， 大半の場合において5～30 回程度の反復計算で，1 個 のノード追加配置に対する反復計算を終了する．しか 0 N (a) (b) (c) (d) (e) (f) 図 4 力 学 計 算 の 局 所 化 ．灰 色 の ノ ー ド に「 変 位 中 」の フ ラ グ が た て ら れ て い る ．力 学 計 算 は 矢 印 で 結 ば れ た ノ ー ド 間 の み に 行 わ れ ，そ れ 以 外 の ノ ー ド 間 の 計 算 は す べ て 省 略 さ れ て い る ． 斥力 D 1 d 1 d 斥力バネモデル
分子間力モデル
図 3 本 手 法 で 用 い る 引 力 ・ 斥 力 の 算 出 式し残念ながら，まれにノードの運動が振動して収束を 妨げる事例もある．そこで筆者らは経験的に，1 個のノ ード配置に対する最大反復回数を 50 回とし，それまで に収束しなかった場合は 50 回目の反復計算時点での配 置結果を用いる． なお力学計算が収束しないという問題は，インクリ メンタルなノード配置アルゴリズムに固有の問題では なく，力学モデルを用いた配置問題の多くに共通する 問題である．現実問題として，商用のグラフ描画ソフ トウェア[18]に採用されている力学モデルにも，反復計 算が収束しない現象は観察できる．またグラフデータ 視覚化以外の問題，例えば三角メッシュ生成のための 力学モデル[17]においても，反復計算が収束しない現象 は観察されている．
3.3. ノード配置順の自動算出
本 手 法 で は ノ ー ド を 1 個 ず つイ ン クリ メ ンタ ル に 配 置 す る こ と を 前 提 と し て い る が ，そ の 配 置 順 は ユ ー ザ ー が 定 義 す る こ と も で き る し ，ま た 自 動 算 出 す る こ と も で き る ．ユ ー ザ ー が 定 義 す る 重 要 度 順 に ノ ー ド を 配 置 す れ ば ，ユ ー ザ ー の 関 心 の 高 い 順 に プ ロ グ レ ッ シ ブ に グ ラ フ デ ー タ を 表 示 す る こ と が で き る ．逆 に ，良 好 な 配 置 結 果 を 得 や す い よ う な 配 置 順 を 自 動 算 出 で き れ ば ，そ れ が 望 ま し い 場 合 も あ る ． 本 手 法 で は ノ ー ド の 配 置 順 を 自 動 算 出 す る 一 手 法 と し て ， ノ ー ド を 隣 接 ア ー ク 数 で ソ ー ト し ， 隣 接 ア ー ク 数 の 多 い ノ ー ド か ら 順 に 配 置 す る ，と い う 配 置 順 を 適 用 す る ．こ こ で 本 手 法 で は ，先 に 配 置 す る ノ ー ド が 中 央 部 に ，後 か ら 配 置 す る ノ ー ド が 周 辺 部 に 配 置 さ れ る よ う に ノ ー ド 位 置 を 決 定 す る ．な ぜ な ら 図 5 に 示 す通 り ，隣接 アー ク 数 の 多 い ノ ー ド が 中 央 部 に 位 置 す る 配 置 結 果 の ほ う が ，ア ー ク の 交 差 が 少 な い 場 合 が 多 い と 予 想 さ れ る か ら で あ る ．こ の 予 想 に し た が っ て 本 手 法 で は ，す で に k 個の ノ ード が 配置 さ れて い ると き に， (k+1)番 目 の ノ ー ド の 初 期 位 置p を 以 下 の 通 り 決 定 す る ． ) (p O p p = 0 +t 0 − こ こ で ，p0は(k+1)番目のノードにアークで連結さ れたノードの位置，Oはすでに配置されているノード 群の中心点，tは正の実数である．この算出式によって 初期位置を決定してから，力学計算を反復することに より，(k+1)番目のノードは隣接ノードよりも外側に配 置される．この反復により，図 5(左)のような配置を実 現する．3.4. 本手法のアルゴリズムおよび特徴
本 手 法 に よ る イ ン ク リ メ ン タ ル な ノ ー ド 配 置 の ア ル ゴ リ ズ ム を ， 図 6 に 示す ． すべてのノードを最初から画面配置する非インクリ メンタルな手法と比較して，本手法には以下のような 特徴がある． 一つ目の特徴として，本手法は非インクリメンタル な手法と比較して，計算時間を大きく短縮できる点が 1. ノードを所定の順で FIFO に登録する． 2. FIFO からノードを抽出し，「変位中」のフラ グをたてる． 3. 抽出されたノードの初期位置を算出する． 4. (4a)～(4d)を，最低１個のノードに「変位中」 のフラグがたっている限り反復する． (4a) 変位中ノードについて，アークで結ばれた ノードとの力を，バネモデルで算出する． (4b) 変位中ノードについて，アークで結ばれて いない近隣ノードとの力を，分子間力モデルで算 出する． (4c) 力を算出したノードの新しい位置を求め る． (4d) 変位の大きいノードに「変位中」のフラグ を立てる． 5. FIFO が空になるまで，2.～4. を反復する． 図 6 イ ン ク リ メ ン タ ル な ノ ー ド 配 置 手 法 の ア ル ゴ リ ズ ム ． 図 5 (左)隣 接ア ー ク数 の 多い ノ ード が 中央 部 に 位 置 す る よ う な 配 置 結 果 ．(右 )隣 接 ア ーク 数 の 多 い ノ ー ド が 周 辺 部 に 位 置 す る よ う な 配 置 結 果 ． 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9あげられる．力学モデルを用いた反復計算の計算量は， ノード数を
n
としたときに，力学計算がまったく局所 化されていない状態でO( )
n2 で あ り ， 力 学 計 算 を 局 所 化 す る に し た が っ てO( )
n に 近 づ く ．こ の こ と か ら ，力 学 モ デ ル の 局 所 化 に 貢 献 し て い る 本 手 法 は ， 計 算 時 間 の 短 縮 に 貢 献 で き る こ と が わ か る ． 5 章 に 示 す 実 験 結 果 か ら も ，計 算 時 間 の 大 幅 な 短 縮 が 実 証 で き て い る ． 二つ目の特徴として，1 章で示した[条件 1][条件 2] の観点において，非インクリメンタルな手法と同等， あるいはそれ以上に良好な配置結果を得ることができ る点があげられる．この特徴も，5 章に 示 す実 験 結果 か ら 実 証 で き て い る ． 三 つ 目 の 特 徴 と し て ， 3.3 節 で 示 し た ノ ー ド 配 置 順 に よ り ，ア ー ク の 交 差 を 減 ら す ，つ ま り 1 章 で 示 し た [条 件 3]の 観 点 で 改 善 を 達 成 し て い る 点 で あ る ．この特徴も，5 章 に示 す 実験 結 果か ら 実証 で き て い る ． 一方で，以下の点が課題として残っている．本手法 は 1 章で示した[条件 4]を改善するものではない．した がって依然として，ノードとアークの干渉は見られる ことがある．この問題に対して筆者らは，アークを曲 線化する手法によって，非階層型グラフデータの視覚 化に対して改善を達成している[19]が，これを階層型グ ラフデータに適用するには問題を残している．よって 6 章で示すウェブサイトの視覚化には，アークの曲線化 手法は用いていない．階層型グラフデータ視覚化およ びウェブサイト視覚化のためのアーク曲線化手法を，7 章にて今後の課題として位置づけている．4. 階層型グラフデータへの応用
4.1. 階層型グラフデータ
グ ラ フ デ ー タ は ，ノ ー ド 間 の 関 係 を ，ア ー ク で 結 ぶ こ と で 表 現 さ れ た デ ー タ で あ る が ，こ れ と は 別 に 同 じ 属 性 の ノ ー ド の 集 合 を グ ル ー プ と し て と ら え る こ と で ，階 層 型 の グ ラ フ デ ー タ を 表 現 す る こ と が 可 能 で あ る ．さ ら に ，グ ル ー プ 自 体 を ノ ー ド と し て と ら え る こ と に よ り ，グ ル ー プ 間 の 関 係 を ア ー ク で 結 ぶ こ と で ，新 た な グ ラ フ デ ー タ を 表 現 す る こ と が で き る ．こ の よ う に し て ，ノ ー ド 間 の 横 の つ な が り と ツ リ ー 構 造 の よ う に 階 層 的 な 縦 の つ な が り を 持 っ た よ う な グ ラ フ デ ー タ の こ と を ， 階 層 型 グ ラ フ デ ー タ と 呼 ぶ ． 図 7 に 階層 型 グラ フ デー タ の例 を 示す ． 図 7(i) は 階 層 化 す る 前 の 通 常 の グ ラ フ デ ー タ で あ る ．こ こ で a～h の グル ー プに ノ ード を 振り 分 ける と ， 図 7(ii)の よう な新 た なグ ラ フが 生 成さ れ る．同じ よ う に 図 7(iii)の よ う に さ ら に 上 位 の 階 層 の グ ラ フ が 生 成 さ れ る ． こ の と き ， 図 7(iii)の ノ ー ド A に 対 し て ，図 7(ii)の ノー ド a~c で 構成 され る グラ フ の こ と を A の 子グ ラ フ ，逆に ノ ード a~c から 見 て ノ ー ド A を親 ノ ード ， ノー ド ABC で構 成 され る グ ラ フ の こ と を 親 グ ラ フ と 呼 ぶ ． こ の 例 で は ， 階 層 型 グ ラ フ の 階 層 の 深 さ は 同 一 で あ る が ， 図 7(i)の ノ ー ド に さ ら に 子 グ ラ フ が あ る よ う な ， 深 さ の 異 な る グ ラ フ も 考 え ら れ る ． こ の よ う な 階 層 型 の グ ラ フ デ ー タ は ， 例 え ば ， 地 域 毎 の 通 信 や 輸 送 や 電 力 等 の ネ ッ ト ワ ー ク の 可 視 化 ，社 内 組 織 の 関 係 や ビ ジ ネ ス プ ロ セ ス の 可 視 化 ， 等 に 有 効 で あ る ． 階 層 型 の グ ラ フ デ ー タ を 用 い る こ と に よ っ て ， 次 の よ う な 効 果 を 得 る こ と が で き る と 考 え ら れ る ． ・ 大 規 模 グ ラ フ の 大 ま か な 理 解 上 位 の 階 層 の グ ラ フ を 表 示 す る こ と に よ っ て グ ラ フ 全 体 像 の 理 解 を 助 け る ． ・ 注 目 箇 所 の 効 果 的 な 可 視 化 注 目 箇 所 の 子 グ ラ フ を 任 意 に 表 示 す る こ と に よ り ，全 体 的 な 理 解 を 損 な わ ず に 注 目 箇 所 の 詳 細 な デ ー タ を 得 る こ と が で き る ． ・ 可 視 化 処 理 の 効 率 化 a b c d e f g hA
B
C
A
B
C
(i)
(ii)
(iii)
図 7 階 層 型 グ ラ フ デ ー タ の 例 ． a b c d e f g h上 位 の ノ ー ド か ら 適 応 的 に ノ ー ド を 配 置 す る こ と で ， 可 視 化 処 理 を 高 速 化 す る こ と が で き る ． こ の 手 法 に つ い て は 後 述 す る ．
4.2. 階層型グラフデータのノード配置
階 層 型 グ ラ フ デ ー タ も 任 意 の 階 層 で グ ル ー プ や ノ ー ド を ア ー ク で 結 ば れ た グ ラ フ デ ー タ で あ る と 考 え ら れ る ．そ こ で ，任 意 の 階 層 の グ ラ フ デ ー タ の グ ル ー プ や ノ ー ド を 配 置 す る に は 3 章で 述 べ た ，力 学 的 手 法 を 用 い た ノ ー ド 配 置 手 法 を 用 い る こ と が で き る ．本 研 究 で は ，大 規 模 グ ラ フ デ ー タ の ノ ー ド 配 置 処 理 の 効 率 化 と ，イ ン タ ラ ク テ ィ ブ な 可 視 化 を 実 現 す る た め に ，最 上 位 階 層 か ら 再 帰 的 に 子 グ ラ フ を 配 置 し て い く 手 法 を 採 用 し た ． こ の 手 法 の ア ル ゴ リ ズ ム を 図 8 に 示し ，詳細 に つ い て 述 べ る ． 図 8 に 示し た アル ゴ リズ ム は，階層 型 グ ラフ の 任 意 の 階 層 の 部 分 グ ラ フ の ノ ー ド 配 置 処 理 に 適 用 す る こ と が で き ，こ の 処 理 を 再 帰 的 に 呼 び 出 す こ と に よ っ て ，グ ラ フ 全 体 を ノ ー ド の 重 な り な し に 配 置 す る こ と が で き る ．図 8 の それ ぞ れの 処 理 に つ い て 図 9 を用 い て説 明 する ． 処 理 1 は， 図 9(i)の よ う に着 目 して い る階 層 の グ ラ フ ABC のノ ー ド配 置 を行 う ．続 い て処 理 2 の よ う に 各 ノ ー ド ABC に つい て 処理 3～6 を行 う ． 処 理 3 では ，図 9(ii)の よう に，ノー ド C につ い て 子 グ ラ フ の 配 置 を 行 う ．図 9(ii)の 円内 のよ う に， 親 グ ラ フ と は 別 の 空 間 内 で ノ ー ド 配 置 処 理 を 行 う ．こ の 処 理 は ，図 8 のア ルゴ リ ズム を 再帰 的 に 呼 び 出 す こ と で 実 現 す る ． 処 理 4 では ，図 9(iii)の よ うに ，別 空間 に配 置 さ れ た 子 グ ラ フ の バ ウ ン デ ィ ン グ ボ ッ ク ス を 親 ノ ー ド C の大 きさ に 反映 さ せ，親ノ ード C を拡 大 す る ．ノ ー ド の 拡 大 に 伴 い ，親 ノ ー ド が 他 の ノ ー ド と 重 な っ て し ま う こ と が あ る ． こ の よ う な 場 合 ， 処 理 5 にお い て ，重 な りが なく な るよ う に ，親 グ ラ フ の ノ ー ド を 再 配 置 す る 必 要 が あ る ．こ の 再 配 置 処 理 は ，下 の 階 層 の グ ラ フ が 配 置 さ れ る た び に 頻 繁 に 呼 び 出 さ れ る た め ，効 率 よ く 処 理 す る た め に 3.2 章 で 述 べた 局 所的 な ノー ド 配置 処 理を 適 用 す る ．拡 大 さ れ た 親 ノ ー ド に「 変 位 中 」の フ ラ グ を 立 て て ，図 4(b)～(f)と 同 様な 局 所的 な 力学 計 算 を 反 復 す る こ と に よ り ，高 速 な 再 配 置 処 理 を 実 現 す る ．な お ，処 理 4 によ っ て拡 大 され た 親ノ ー ド が 既 に 配 置 さ れ て い る ア ー ク と 交 差 し て し ま う 可 能 性 が あ る ． こ の 問 題 は ， 3.4 節 で も 述 べ ら れ て い る よ う に ，本 手 法 に お い て は ，根 本 的 に ノ ー ド と ア ー ク の 交 差 を 除 去 す る こ と を 解 決 し て は い な い ．今 後 ，こ の よ う な 場 合 に つ い て も ，交 差 を 取 り 除 く よ う な 処 理 の 導 入 を 検 討 し て い き た い ． 処 理 6 では ，図 9(iv)の よ うに ，拡 大 さ れた 親 ノ ー ド の 位 置 に ，別 の 空 間 で 配 置 さ れ た 子 グ ラ フ を マ ッ ピ ン グ す る こ と で ，既 に 配 置 さ れ て い る ノ ー ド と 重 な り な し に 子 グ ラ フ の ノ ー ド を 配 置 す る こ と が で き る ． こ の よ う な 処 理 に よ り ，任 意 の 階 層 の グ ラ フ を 適 応 的 に 可 視 化 す る こ と が 可 能 と な る ．ユ ー ザ ー は グ ラ フ の 全 体 像 を つ か み つ つ ，注 目 し た い 部 分 の 詳 細 な グ ラ フ を 見 る と い っ た 操 作 が 可 能 に な る ．ま た ，階 層 型 グ ラ フ デ ー タ の 配 置 処 理 を 用 い る こ と で 近 い 性 質 の ノ ー ド を 近 い 位 置 に 配 置 す る こ と が で き ，グ ラ フ の 理 解 を 助 け る 効 果 も あ る ． 階 層 型 グ ラ フ デ ー タ の 可 視 化 の 例 を デ ジ タ ル デ ー タ と し て 用 意 し た ．図 8 に示 し た処 理の 過 程 の 様 に ，親 グ ラ フ の 配 置 結 果 か ら ，親 ノ ー ド を 選 択 し て い く こ と に よ り ，子 グ ラ フ が 配 置 さ れ て い く 様 子 が 分 か る よ う に な っ て い る ． 1. グラフ G を構成するノードを配置する 2. グラフ G に属するノード Ni(i=0,1,…,n)につ いて処理 3～6 を行う 3. ノード Ni が子グラフ Gi を持つとき，子グラ フ Gi について別の空間を用意し，1 からの処 理を再帰的に呼び出す 4. 処理 3 で子グラフ Gi の占有領域にあわせて ノード Ni の大きさを拡大する 5. ノード Ni のサイズ変更に伴いグラフ G を局 所的に再配置する 6. ノード Ni に子グラフ Gi をマッピングする 7. 親ノードにグラフ G の占有領域を返し親グラ フの処理 4 に反映する 図 8 階 層 型 グ ラ フ デ ー タ の 再 帰 的 な ノ ー ド 配 置 手 法 の ア ル ゴ リ ズ ム ．図 9(iv)に お いて ，親 ノー ドに 挿 入さ れ た子 グ ラ フ の ノ ー ド か ら ，実 際 に は ノ ー ド A お よび B に属 す る 子 グ ラ フ の ノ ー ド へ ，ア ー ク が 接 続 さ れ て い る こ と に な る が ，こ こ で は ，親 ノ ー ド C と親 ノ ー ド A およ び B とを 結 ぶア ー クで 代 表し て 表示 す る こ と に し て い る ．本 手 法 で は ，正 確 な ノ ー ド 間 の 繋 が り を 表 示 す る こ と よ り も ，階 層 構 造 と ，そ の 間 の 関 係 を 見 や す く す る こ と に 重 点 を お い て 可 視 化 を 行 う 方 向 で 考 え ，親 ノ ー ド 間 の ア ー ク に よ る 接 続 で 子 ノ ー ド 間 の 複 雑 な 接 続 関 係 を 代 表 し て 表 示 す る こ と で 表 示 が 複 雑 に な る の を 防 い で い る ．な お ，子 ノ ー ド 間 の ア ー ク の 情 報 は 保 持 さ れ て い る の で ，特 定 の ノ ー ド を 選 択 し て ，元 の ア ー ク を 再 現 す る こ と も 可 能 で あ る が ， こ こ で は ， そ の ア ー ク が 他 の ノ ー ド や ア ー ク と 交 差 す る 問 題 に つ い て は 解 決 し て い な い ．ア ー ク を 再 現 し た 後 ，局 所 的 な 再 配 置 処 理 を 子 ノ ー ド に 対 し て 実 行 す る こ と で ，交 差 を 取 り 除 く こ と は 可 能 で あ る が ， こ れ に よ っ て グ ル ー プ 化 さ れ た ノ ー ド が 遠 く に 配 置 さ れ る と い っ た 問 題 や ，処 理 の 効 率 を 落 と す 問 題 が あ る ． ま た ，大 規 模 な グ ラ フ デ ー タ に お い て は ，同 時 に す べ て の ノ ー ド の 配 置 処 理 を 行 お う と す る と 膨 大 な 計 算 時 間 が 必 要 と な る ．本 手 法 に よ る 力 学 計 算 に よ る ノ ー ド 配 置 の 計 算 量 は ， n 個 のノ ー ド の 配 置 を 行 う 場 合 ，力 学 計 算 は 実 際 に は 局 所 的 に 計 算 さ れ る が 1 個 のノ ー ドに 対 して 最 大で n-1 組 の 計 算 を 行 う た め ，O
( )
n2 で あ る ． し か し ，階 層 型 グ ラ フ デ ー タ を 用 い る こ と で 各 部 分 グ ラ フ で は 少 な い ノ ー ド 数 で 配 置 処 理 を 行 う こ と が で き ，上 位 グ ラ フ の 再 配 置 処 理 も 局 所 的 な 処 理 で 済 む の で グ ラ フ 全 体 の 配 置 処 理 の 計 算 時 間 を 比 較 的 短 く す る こ と が で き る と 考 え ら れ る ． 仮 に ， n 個の ノ ード の グラ フ につ い て，k 個 ず つ の ノ ー ド を m 個 の グ ル ー プ に わ け 親 グ ラ フ を 作 り ，さ ら に k 個ず つ の 親ノ ー ドを グ ルー プ に ま と め て・・・と い う 処 理 を 反 復 し て 階 層 型 グ ラ フ を 作 っ た と す る ．こ の と き の 階 層 の 深 さ は 平 均m
log
と な り ，部 分 グ ラ フ の 総 数 は 平 均m log
m
と 見 積 も る こ と が で き る ．こ の と き ，図 8 に示 し た 再 帰 的 な ノ ー ド 再 配 置 処 理 の 回 数 は(
)
2log m
m
と 見 積 も る こ と が で き る ．ま た ，階 層 型 グ ラ フ デ ー タ の ノ ー ド 配 置 処 理 で は ，力 学 計 算 以 外 の 計 算 量 も 多 く な る が ，そ の 計 算 量 は 力 学 計 算 の 計 算 量 と 比 較 し て 無 視 で き る く ら い 小 さ い ．よ っ て ，階 層 型 グ ラ フ デ ー タ の 配 置 処 理 に お け る 力 学 計 算 の 計 算 量 は ，(
)
2( )
2 logm Ok m と な り ，O( )
n2 よ り も 少 な い 計 算 量 と な る ．実 際 に ノ ー ド 配 置 処 理 の 処 理 時 間 を 比 較 し て み る と ， 図 16 の よ う にな る ．5. グラフデータ配置手法の実行例
本 章 で は ， 3 章お よ び 4 章 で提 案 した グ ラフ デ ー タ 配 置 手 法 を 実 装 し て 実 行 し た 結 果 を 示 す ．筆 者 ら は ， 本 手 法 を Microsoft Visual C++で実 装 し， IBM IntelliStation M Pro (Intel Pentium III 3.06 GHz RAM 1.0GB)お よ び ，Microsoft Windows XP 上 に て 実 行 し た ． 図 10 は ，3 章 で提 案 した 手 法に よ るイ ン クリ メ ン タ ル な ノ ー ド 配 置 処 理 の ス ナ ッ プ シ ョ ッ ト を 示 し た も の で あ る ．な お こ の グ ラ フ デ ー タ は ，表 1 に 示 さ れ て い る 図 11 の グ ラ フ デ ー タ と 同 一 の グ ラ フ デ ー タ で あ る ． 図 11 お よび 図 12 は， 3 章で 提 案し た 手法 に よ る イ ン ク リ メ ン タ ル な ノ ー ド 配 置 結 果 と ，初 期 段 階 か ら す べ て の ノ ー ド を 配 置 す る 非 イ ン ク リ メ ン タ ル な 手 法 に よ る ノ ー ド 配 置 結 果 を 比 較 し た※
Visual C++および WindowsXP は Microsoft 社の登録商標． IntelliStation は IBM 社の登録商標．
A
B
C
(i) (ii)
(iii)
A
B
C
(iv)
A
B
C
a
b
c
d
A
B
C
a
b
c
d
図 9 階 層 型 グ ラ フ デ ー タ の ノ ー ド 配 置 の 例 ．も の で あ る ．こ こ で 非 イ ン ク リ メ ン タ ル 手 法 で は ， す べ て の ノ ー ド を 画 面 空 間 の 原 点 近 傍 に ，座 標 値 を 乱 数 と し て 発 生 さ せ る こ と で 初 期 配 置 し た ．ま た 非 イ ン ク リ メ ン タ ル 手 法 と 提 案 手 法 と で は ，力 学 計 算 の 係 数 や 収 束 条 件 な ど を 同 一 に し て い る ． 表 1 は ，図 11 およ び図 12 の対 象 とな るグ ラ フ デ ー タ の ノ ー ド 数 お よ び ア ー ク 数 を 示 し た も の で あ る ． 表 2 は ，図 11 およ び図 12 の結 果 に対 する 処 理 時 間 を 実 測 し た も の で あ る ． 表 2 およ び表 3 は， 図 11 およ び 図 12 の 結 果 に対 し て ，ア ーク の 長さ の 平 均 値 ， ア ー ク の 交 差 数 ， を 算 出 す る こ と で ， 配 置 結 果 を 数 値 評 価 し た も の で あ る ．こ こ で ア ー ク の 長 さ は ， 理 想 値 （ 力 学 モ デ ル 上 の 分 子 半 径 ） を 1 と した 相 対値 で 表現 し てお り，そ の 平均 値 が 1 に 近 い ほ ど 良 好 な 配 置 で あ る と い え る ． ま た ア ー ク の 交 差 数 は 少 な い ほ ど 良 好 な 配 置 で あ る と い え る ． 表 1 図 11,12 の対象となるグラフデータ 図 11 図 12 ノード数 70 100 アーク数 81 180 表 2 処理時間の測定結果(1) (単位ミリ秒) 図 11 図 12 非インクリメンタル手法 9542.5 19477.1 本手法 2483.7 4052.3 表 3 配置結果の数値評価 (アークの長さの平均) 図 11 図 12 非インクリメンタル手法 1.14 1.24 本手法 0.94 0.99 表 4 配置結果の数値評価 (アークの交差数) 図 11 図 12 非インクリメンタル手法 8 31 本手法 0 0 図 11 につ い ては ， 表 3 より ア ーク の 長さ に つ い て は 両 手 法 と も 好 ま し い 結 果 と な っ て お り ，ま た 表 4 よ り ア ーク の 交差 数 につ い ても 両 手法 と も 少 な く な っ て い る ．し か し 表 2 から わ か るよ う に， 提 案 手 法 の ほ う が 計 算 時 間 は 大 幅 に 小 さ い ． 図 12 に つ い ては ，表 4 から わ かる よ うに ， 非 イ ン ク リ メ ン タ ル 手 法 で は ア ー ク の 交 差 数 が 非 常 に 多 い こ と か ら ，提 案 手 法 の ほ う が 明 ら か に 良 好 な 配 置 結 果 を 実 現 し て い る ．ま た 表 2 から わ か る よ う に ，提 案 手 法 の ほ う が 計 算 時 間 は 大 幅 に 小 さ い ． 図 12 ノ ー ド 配 置 結 果 の 比 較 (2)． 左 は 非 イ ン ク リ メ ン タ ル ， 右 は 本 手 法 ． 図 11 ノ ー ド 配 置 結 果 の 比 較 (1)． 左 は 非 イ ン ク リ メ ン タ ル 手 法 ， 右 は 本 手 法 ． (1) (2) (3) (4) (5) (6) 図 10 本 手 法 によ る イ ンク リメ ン タ ルな ノー ド 配 置 処 理 の ス ナ ッ プ シ ョ ッ ト ．
図 13 は ， 本 手法 に よる 階 層型 グ ラフ デ ータ の ノ ー ド 配 置 処 理 の ス ナ ッ プ シ ョ ッ ト を 示 し た も の で あ る ． 図 13(1)～(4)に矢 印 で示 し たノ ー ドを 選 択 し そ の 子 グ ラ フ を 展 開 す る こ と で ノ ー ド 配 置 を 行 う 様 子 を 示 し た ． 図 13(6)が 最 終 的 な ノ ー ド 配 置 結 果 で あ る ． 図 14 お よ び 図 15 は ，そ れぞ れ 同一 の グラ フ に 対 し て ，階 層 化 し た も の と ，そ の ま ま の 状 態 の も の と で ，ノ ー ド 配 置 処 理 を し た 結 果 を 示 し た も の あ る ．こ の 結 果 か ら ，階 層 型 グ ラ フ デ ー タ の ノ ー ド 配 置 処 理 で は ，ノ ー ド の グ ル ー プ が 明 確 に 表 現 さ れ ，グ ラ フ の 全 体 的 な 構 造 を 把 握 し や す い も の と な っ て い る ． な お ，図 14，図 15，図 16 で使 用 した グラ フ デ ー タ は ，n 個（図 14 で は n=50，図 15 で は n=100） の ノ ー ド を ラ ン ダ ム に ア ー ク で 結 び ，階 層 型 グ ラ フ は ，同 じ グ ラ フ に 対 し て ， ア ー クで 隣接 する 5 ～ 10 個 の ノ ー ド が 入 る よ う に グ ル ー プ を 作 っ て い き ，グ ル ー プ か ら で き る グ ラ フ を 反 復 的 に 階 層 化 し て 作 ら れ た も の で あ る ． 表 5 は ，図 14， 図 15 そ れ ぞれ の 配置 処 理の 処 理 時 間 を 比 較 し た も の で あ る ． ま た 図 16 は， 階 層 型 グ ラ フ と 非 階 層 型 グ ラ フ の ノ ー ド 配 置 処 理 の 処 理 時 間 を ，グ ラ フ の ノ ー ド 数 で 比 較 し た 測 定 結 果 で あ る ．階 層 の 深 さ や 各 グ ル ー プ に 属 す る ノ ー ド 数 等 の 違 い で 結 果 が 変 化 す る が ，階 層 型 の グ ラ フ デ ー タ の ノ ー ド 配 置 処 理 に よ っ て ，効 率 よ く グ ラ フ の 配 置 処 理 が 行 わ れ て い る こ と が わ か る ． 表 5 処理時間の測定結果(2) (単位ミリ秒) 図 14 図 15 通常のグラフ 510.2 1993.1 階層型グラフ 66.9 156.6 (1) (2) (3) (4) (5) (6) 図 13 本 手 法 によ る 階 層型 グラ フ デ ータ のノ ー ド 配 置 処 理 の ス ナ ッ プ シ ョ ッ ト ． 図 15 ノー ド 配置 結 果の 比 較(4)． 同 一 グラ フ に 対 し て 右 は 階 層 化 し ノ ー ド 配 置 を 行 っ た ． 図 14 ノー ド 配置 結 果の 比 較(3)． 同 一 グラ フ に 対 し て 右 は 階 層 化 し ノ ー ド 配 置 を 行 っ た ．
0 2000 4000 6000 8000 10000 12000 0 50 100 150 200 ノード数 処理 時間[ ms]
階層型グラフ
通常のグラフ
図 16 階 層 型 と通 常 のグ ラ フデ ー タの ノ ード 配 置 処 理 時 間 の 比 較 ．6. ウェブサイト視覚化への応用例
階 層 型 グ ラ フ デ ー タ の 可 視 化 例 と し て ，こ こ で は ウ ェ ブ サ イ ト 可 視 化 を 例 に あ げ る ．ウ ェ ブ サ イ ト は HTML 言 語 で 記 述 さ れ た ウ ェ ブ ペ ー ジ か ら 構 成 さ れ ， そ の ウ ェ ブ ペ ー ジ は ， http://で 始 ま る ホ ス ト 名 と ，そ の あ と に 続 く デ ィ レ ク ト リ 名 と フ ァ イ ル 名 で 識 別 さ れ る ． ま た ， ウ ェ ブ ペ ー ジ は HTML の ハ イ パ ー リ ン ク に よ っ て 他 の ウ ェ ブ ペ ー ジ へ 接 続 さ れ る ．こ こ で は ウ ェ ブ サ イ ト の 構 造 を ， ウ ェ ブ ペ ー ジ を ノ ー ド ，ハ イ パ ー リ ン ク を ア ー ク と し ，ホ ス ト 名 と デ ィ レ ク ト リ 階 層 で グ ル ー プ 化 し た 階 層 型 グ ラ フ デ ー タ と し て 可 視 化 を 行 う ． 一 般 的 な ウ ェ ブ サ イ ト の 構 築 方 法 と し て ，図 17 の よ う に ，共 通 す る 内 容 の ペ ー ジ を 同 一 デ ィ レ ク ト リ に ま と め て 公 開 す る 方 法 が よ く 使 わ れ る ．デ ィ レ ク ト リ 階 層 を 用 い て 階 層 化 さ れ た グ ラ フ デ ー タ を 可 視 化 す る こ と に よ り ，共 通 の 内 容 の ペ ー ジ を ま と め て 表 示 で き ，ウ ェ ブ サ イ ト の 構 成 を 理 解 し や す く な る ． 階 層 型 の グ ラ フ 構 造 を 用 い る こ と で ，階 層 構 造 を 表 現 す る と と も に ，木 構 造 を 用 い た ウ ェ ブ サ イ ト 可 視 化 手 法 [11][13][14]で は 表 現 し き れ な い ウ ェ ブ ペ ー ジ 間 の リ ン ク 関 係 を も 表 現 で き る 利 点 が あ る ．ま た ，三 次 元 空 間 に ウ ェ ブ ペ ー ジ を 配 置 す る ウ ェ ブ サ イ ト 可 視 化 手 法 [15][16]と は 異 な り ， 視 点 の 回 転 操 作 等 を 必 要 と せ ず に 一 画 面 に ウ ェ ブ サ イ ト の 全 体 像 を 可 視 化 で き る 利 点 が あ る ．ま た 階 層 構 造 を 用 い な い ，グ ラ フ デ ー タ に よ る 可 視 化 の 場 合 ，ウ ェ ブ ペ ー ジ 同 士 の リ ン ク の 数 が 多 く ， と て も 煩 雑 な 可 視 化 結 果 に な っ て し ま う こ と が あ る が ， 階 層 化 し グ ル ー プ 化 す る こ と に よ っ て ， グ ル ー プ 間 の リ ン ク で ，ペ ー ジ 間 の リ ン ク を 代 表 す る 手 法 を 用 い る こ と で ，リ ン ク の 混 雑 具 合 を 調 整 す る こ と が で き る 利 点 が あ る ．特 に ，デ ィ レ ク ト 構 造 を 用 い て 整 理 さ れ た ウ ェ ブ サ イ ト で あ れ ば ，他 の デ ィ レ ク ト リ へ の リ ン ク よ り も 同 一 デ ィ レ ク ト リ 内 で の リ ン ク 構 造 の 方 が 重 要 で あ る こ と が 多 く ，階 層 化 グ ラ フ デ ー タ の 可 視 化 に よ っ て ， 同 一 デ ィ レ ク ト リ 内 の ペ ー ジ の リ ン ク 構 造 を 見 や す く 提 供 す る こ と が で き る ． ウ ェ ブ サ イ ト の 階 層 型 グ ラ フ を 構 築 す る に は ， ト ッ プ ペ ー ジ か ら リ ン ク を た ど る こ と に よ っ て ノ ー ド を 収 集 し て い く ．こ の と き ，ウ ェ ブ サ イ ト 外 部 の ペ ー ジ（ ホ ス ト 名 の 違 う ペ ー ジ や ト ッ プ ペ ー ジ の 属 す る デ ィ レ ク ト リ 階 層 の 下 に 属 さ な い も の ）は 同 じ グ ル ー プ に ま と め て お き ，そ れ 以 上 先 の リ ン ク は た ど ら な い ．ま た ，上 の 階 層 へ の リ ン ク や 既 に た ど っ た ペ ー ジ へ の リ ン ク は ，そ れ 以 上 先 を た ど ら な い ．こ こ で は ，無 向 グ ラ フ を 用 い る た め ，元 の ペ ー ジ へ 戻 る よ う な リ ン ク は 考 慮 し な い ．ウ ェ ブ サ イ ト 内 の ペ ー ジ は デ ィ レ ク ト リ 階 層 ご と に グ ル ー プ 化 し ，階 層 型 グ ラ フ を 構 築 す る ． 図 18 は ウ ェ ブサ イ トを 階 層型 グ ラフ 化 しノ ー トップページ / 会社概要 /profile 製品情報 /products オンラインショップ /shop ソフトウェア /products/software 周辺機器 /products/hardware 図 17 ウ ェ ブ サイ ト の ディ レク ト リ 階層 と構 成 の 例 ．ド 配 置 を 行 い ，ノ ー ド 部 分 に そ の ペ ー ジ の サ ム ネ イ ル を 表 示 し た 可 視 化 例 で あ る ．こ の よ う な 可 視 化 の 結 果 の 画 像 を 用 い て ，ペ ー ジ の 繋 が り を 理 解 し な が ら ウ ェ ブ サ イ ト 内 を ナ ビ ゲ ー ト す る こ と が 可 能 で あ る ． 図 19， 図 20 はウ ェ ブサ イ トの 情 報を 可 視化 し た 例 で あ る ． 図 19 で は ウ ェブ ペ ージ の 更新 情 報 を ノ ー ド の 色 で 示 し た ．赤 が 最 近 更 新 さ れ た ペ ー ジ で ，青 が 最 後 に 更 新 さ れ て か ら の 月 日 の 長 く 経 過 し た ペ ー ジ で あ る こ と を 示 し て い る ．ま た 図 20 は 図 19 に 加 えて ， ペー ジ の一 日 のア ク セス 数 を ノ ー ド の 大 き さ で 示 し た 結 果 で あ る ．こ の よ う に ， ア ク セ ス 数 や 更 新 頻 度 等 の 情 報 を 示 す こ と で ，ウ ェ ブ サ イ ト の 管 理 者 向 け の 情 報 を ，ウ ェ ブ サ イ ト の 階 層 構 造 や リ ン ク 構 造 と 共 に 可 視 化 す る こ と が で き る ．こ の よ う な 可 視 化 結 果 を 用 い る こ と で ， 例 え ば ，人 気 の あ る ペ ー ジ と そ の 関 連 す る ペ ー ジ を 見 つ け た り ，更 新 が 頻 繁 に 行 わ れ て い る に も 関 ら ず ア ク セ ス が 少 な い ペ ー ジ を 見 つ け ，そ の 原 因 は そ の ペ ー ジ に た ど り 着 く ま で の 階 層 の 深 さ が 問 題 で あ る と い っ た こ と を 発 見 す る た め に 使 用 し た り ， と い っ た 使 用 法 が 考 え ら れ る ． な お ，図 18，図 19，図 20 に示 す ウェ ブサ イ ト の 可 視 化 例 で は ， 4.2 節 で 述 べ た よ う に ， す べ て の ペ ー ジ 同 士 の リ ン ク を 正 確 に 表 示 す る こ と は 避 け ，下 位 の 階 層 の ペ ー ジ 同 士 の リ ン ク は ，親 ノ ー ド 同 士 の リ ン ク で 代 表 し て ペ ー ジ 間 の 関 係 を 表 す よ う に す る こ と で ，リ ン ク 表 示 に よ る 混 雑 の 度 合 い を 調 整 す る よ う に し て い る ．し か し な が ら ， こ の 手 法 で は あ る ペ ー ジ が ，ど の ペ ー ジ か ら 参 照 さ れ て い る と い う 正 確 な 情 報 を 知 る こ と が で き な い ．例 え ば ，あ る ペ ー ジ を 選 択 し て ，そ の ペ ー ジ に 繋 が る リ ン ク の み を 正 確 に 表 示 す る と い っ た 可 視 化 の 手 法 を 取 り 入 れ て い く べ き で あ る と 考 え て い る ．ま た ，管 理 者 向 け の 情 報 可 視 化 の 例 に 挙 げ た ，頻 繁 に 更 新 さ れ て い る に も か か わ ら ず ア ク セ ス 数 の 少 な い ペ ー ジ を 発 見 す る 際 ，例 え ば ト ッ プ ペ ー ジ か ら そ の ペ ー ジ へ 至 る リ ン ク に よ る 経 路 の み を 表 示 す る と い っ た 可 視 化 手 法 も 実 用 的 で あ る と 考 え ら れ る ．今 後 は ，こ の よ う な 適 応 的 に 可 視 化 を 行 う 手 法 に つ い て も 検 討 し て い き た い ． ウ ェ ブ ペ ー ジ の 可 視 化 の 例 と し て ，デ ジ タ ル デ ー タ を 用 意 し た ． 1 つ 目 は ，実 際 のウ ェ ブペ ー ジ の 可 視 化 結 果 で あ り ，サ ム ネ イ ル を ク リ ッ ク す る と 実 際 の ペ ー ジ へ 行 く こ と が で き る ． 2 つ目 は ， 図 19，図 20 に 対応 す る実 際 の可 視 化結 果 であ る ． 図 18 ウ ェ ブ サイ ト の可 視 化の 例 ． 図 19 ウ ェ ブ ペー ジ の更 新 状況 の 可視 化 例．
7. むすび
本論文では，力学モデルを用いたグラフデータ視覚 化手法に対して，ノードをインクリメンタルに 1 個ず つ画面配置する，という考え方により配置結果および 処理時間を改善する手法を提案した．また，この手法 を階層型グラフデータの視覚化に応用する手法を提案 した．また，これらの手法の従来手法に比べる優位性 を実験結果で示すとともに，ウェブサイトの視覚化に 適用した例を示した． 今後の課題として，ウェブサイト以外の階層型デー タに対して提案手法を適用し，効果的な視覚化を実証 することがあげられる． また筆者らは，グラフデータ視覚化に関する関連手 法として， ¾ アークの曲線化により，アークとノードの重なり を避ける手法[19] ¾ 階層型グラフデータを効果的に透視投影する手 法[20] も提案しているが，これらの手法は本論文ではウェブ サイトの視覚化に適用していない．これらの手法がど のように効果的に実用化できるか，についても実証し たい． また，階層的なグラフ構造を可視化する上で，ユー ザーの操作によっていかに効果的に可視化を行うかと いう点について，例えば，効果的なアークの表示手法 や，ユーザーの注目点の効果的な表示手法，等につい ても検討していきたい．参考文献
[1] Battista G. D., Eades P., Tamassia R., Tollis I. G., Graph Drawing – Algorithms for the Visualization of Graphs, Prentice Hall, ISBN0-13-301615-3, 1999.
[2] Herman I., Melancon G., Marshall M. S., Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on Visualization and Computer Graphics, Vol. 6, No. 1, pp. 24-43, 2000.
[3] Eades P., A Heuristic for Graph Drawing, Congressus Numerantium, Vol. 42, pp. 149-160, 1984.
[4] Quigley A., Eades P., FADE: Graph Drawing, Clustering and Visual Abstraction, Symp. Graph Drawing 2000, 2000. [5] Bertault F., A Force-Directed Algorithm that Preserves Edge Crossing Properties, Graph Drawing ’99, pp. 351-358, 1999.
[6] Gansner E., et al., Improved Force-Directed Layouts, Graph Drawing '98, LNCS 1547, pp. 364-373, 1998. [7] Huang M. L., Eades P., Wang J., On-line Animated Visualization of Huge Graphs Using a Modified Spring Algorithm, Journal of Visual Languages and Computing, Vol. 9, pp. 623-645, 1998.
[8] North S., Incremental Layout in DynaDAG, Graph Drawing ’95, pp. 409-418, 1995.
[9] P. Eades, et al., Multilevel Visualization of Clustered Graphs, Graph Drawing ’96, pp. 101-112, 1996.
[10] D. Schaffer, et al., Navigating Hierarchically Clustered Networks through Fisheye and Full-Zoom Methods, ACM Trans. Computer-Human Interaction, Vol. 3, No. 2, pp. 162-188, 1996.
[11] Inxight Star Tree (TM) SDKs,
http://www.inxight.com/products/sp/ht/sdk/index.html [12] Lamping J., Rao R., The Hyperbolic Browser: A Focus+context Technique for Visualizing Large Hierarchies, Journal of Visual Languages and Computing, Vol. 7, No. 1, 図 20 ウ ェ ブ サイ ト の情 報 の可 視 化例 ．
pp. 33-55, 1996.
[13] Durand D., et al., MAPA: A System for Inducing and Visualizing Hierarchy in Web sites, 9th ACM Conference on Hypertext and Hypermedia, pp. 66-76, 1998.
[14] 山口, 伊藤, 池端, 梶永, 階層型データ視覚化手 法「データ宝石箱」とウェブサイトの視覚化, 画像電子 学会論文誌 Visul Computing 特集号, Vol. 32, No. 4, pp. 407-417, 2003.
[15] Hendley R. J. , Drew N. S., Wood A., Beale R., Narcissus: Visualizing Information, IEEE Information Visualization '95, pp. 90-96, 1995. [16] 塩澤, 西山, 松下, 「納豆ビュー」の対話的な情報 視覚化における位置付け, 情報処理学会論文誌, Vol. 38, No. 11, pp. 2331-2342, 1997. [17] 嶋田, 物理モデルによる自動メッシュ分割, シミ ュレーション, 12, 1, 11-20, 1993. [18] LEDA, http://www.algorithmic-solutions.com/enleda.htm [19] 伊 藤 , 井 上 , 土 井 , 梶 永 , 池 端 , 力 学 モ デ ル を 用 い た グ ラ フ デ ー タ の 視 覚 化 手 法 の 改 良 , 情 報 処 理 学 会 グ ラ フ ィ ク ス &CAD 研 究 会 , 2001-CG-103, pp. 7-12, 2001. [20] 土 井 ，伊 藤 ，梶 永 ，池 端 ，階 層 型 グ ラ フ デ ー タ の た め の 可 視 化 手 法 ， グ ラ フ ィ ク ス と CAD シ ン ポ ジ ウ ム 2001 予 稿 集， pp.47-50,2001.
