射影に基づく対話的三次元グラフ可視化手法

全文

(1)Vol.2012-HCI-146 No.6 2012/1/19. 情報処理学会研究報告 IPSJ SIG Technical Report. 1. はじめに. 射影に基づく対話的三次元グラフ可視化手法. グラフはオブジェクトの関係を表現する方法である．グラフにおいてオブジェクトはノードとして表され，２つのオブジェクトの関係は対応するノードを繋ぐエッジとして表現され. 高見. 将則†1. 細. 部. 博. 史†2. 脇田. 建†3. る．グラフで表現された情報を可視化することは，その構造を直感的に理解するための重要な技術である．そのためオブジェクトの関係からノードとエッジの適切な位置を自動的に計算するグラフ配置あるいはグラフ描画と呼ばれる手法がさかんに研究されている．グラフは. 本稿では細部の提案した対話的グラフ可視化手法を拡張し，可視空間として二次元に限らず，任意の次元で対話的にグラフ配置を操作する手法を提案する．本手法ではまず多次元尺度法を用いて高次元空間での静的なグラフ配置を求め，それを可視空間へ射影する．そしてユーザの操作に応じて射影を更新することで，対話的に可視空間でのグラフ配置を更新する．さらに可視空間として三次元を採用した試作システムの実装とその実行結果について述べる．. ノードやエッジに関連する構造や属性によって木，無向グラフ，有向グラフなどの種類に分類される．無向グラフはエッジの方向が定められていないグラフであり，ネットワークの構造を持つ様々な情報を表現するために用いられている．無向グラフを可視化する技術としては力学的手法がよく知られている1)7)2) ．これはエッジをバネに見立てて，ノード同士が引力と斥力を及ぼしあうような仮想的な物理系をグラフから構成し，シミュレーションやエネルギーの最小化によって各ノードの安定的な配置を求. A projection-based method for interactive 3D visualization of complex graphs. める方法である．しかし，ある程度の大きさと複雑性を持つより一般的な無向グラフでは，グラフの構造が複雑なゆえ静的な配置に可視化することは難しい．. Masanori. Takami,†1. Hiroshi and Ken Wakita†3. Hosobe†2. このようなグラフに対しては，ユーザの操作に応じて対話的にグラフ配置を変化させる対話的グラフ配置が有効である．細部は最初に高次元空間でのグラフ配置を求めておき，そこから二次元グラフ配置への射影をユーザの操作に応じて変化させることで，対話的にグラフ配置を変更する手法を提案した3) ．この手法は二つの特徴があり，一つは二次元グラフ配置. Proposed is a new interaction technique to manipulate graph layouts presented on two- and higher-dimensional spaces. The work extends a highdimensional interactive graph visualization technique proposed by Hosobe, which deals with graph layouts presented on two-dimensional spaces. The proposed method first computes static graph layouts in high-dimensional space using multidimensional scaling, and then projects it on a low-dimensional space. Updating this projection according to user interaction, it enables the user to handle a graph layout in the low-dimensional space interactively. The report gives a theoretical foundation to interact with graph layouts and presents experimental results obtained with an early prototype system using three dimensions.. の計算が極めて高速で，ユーザの対話的操作がリアルタイムに反映されるということである．もう一つはユーザが移動するノードを中心にして配置の更新を行うため，少ないノードの移動によってグラフの特定部分を強調することができる．本稿ではこの細部の提案したグラフの対話的可視化手法を拡張することで，高次元空間から二次元平面に限らず，任意の次元の空間に射影する方法を提案する．また提案手法の可視空間として三次元を採用した場合の実装を示し，試作システムでの実行結果を与える．本稿の構成は以下のようになっている．まず二節で関連研究について紹介する．次の三節では細部の手法について説明し，四節では提案手法について述べる．そして五節では提案手. †1 東京工業大学理学部情報科学科 Department of Information Science, Tokyo Institute of Technology †2 国立情報学研究所 National Institute of Informatics †3 東京工業大学大学院情報理工学研究科/JST CREST Tokyo Institute of Technology/Japan Science and Technology Agency. 法の可視空間として三次元を採用した場合についての実装について述べ，六節でその実行結果について示す．最後の七節で本研究のまとめと今後の課題を述べる．. 1. c 2012 Information Processing Society of Japan ⃝.

(2) Vol.2012-HCI-146 No.6 2012/1/19. 情報処理学会研究報告 IPSJ SIG Technical Report. 2. 関連研究. aij =. k=1. 無向グラフの配置を求める手法としては力学的手法がある．Eades はエッジにバネを対 1). 応させ，その引力と斥力から物理的に安定なノードの配置を求めた． Kamada-Kawai 法. n n n n 1∑ 2 1 ∑∑ 2 1 1∑ 2 ( dik + dkj − 2 dkl − d2ij ) 2 n n n. 7). k=1 l=1. k=1. このように定義すると A は実対称行列になり，直交行列 V を用いて以下のように対角化で. はノード間のバネのエネルギーの和を最小化することで系の平衡状態を求める方法である．. きる．. Fruchterman らは隣接するノード同士には引力を与え，それ以外の任意のノード同士には.  . λ1. V T AV = Λ =  . 斥力を与える手法を提案した2) ．細部は文献 6) で異なる力学的手法を統一の数値最適化問題として捉えた．グラフの行列表現の一つであるラプラス行列の固有ベクトルを元にグラ. 0 ... 0. フ配置を求める手法もある．ACE アルゴリズム8) はラプラス行列の固有値計算を高速に行. ..    . λn. い，数百万ノードのグラフのレイアウトを一分以内に求めることができる．また HDE9) は. Λ は対角行列であり，λi は A の固有値で λ1 ≥ λ2 ≥ . . . ≥ λn とする．また各 λi に対応す. 五十程度の基準となるノードを定めてそれに基づいて高次元配置を求め，主成分分析を利用. る固有ベクトルを v i とすると V = (v 1 , . . . , v n ) となる．そして正の固有値の数を d する. 13). して二次元に射影する手法である．Kruskal らは多次元尺度法（MDS）. （λ1 ≥ λ2 ≥ . . . ≥ λd > 0）．. を用いて二次元. 最後に n × d 行列 X = (x1 , . . . , xn )T を以下のように定義する．  √    λ1 0 x1   ..  .    . ˜ 1/2 = (v 1 , . . . , v n )   ..  = V Λ X= √      0 λd  xn 0. のグラフ配置を求めた11) ．細部は Kruskal らの手法を応用したグラフの対話的可視化手法を提案し，AGI（Active Graph Interface）を実装した3) ．Kruskal と細部の手法は三節で詳しく説明する．また文献 5) で Kruskal らの手法を利用した場合と他の手法を利用した場合の比較実験を行った．さらに複数のノードを同時に移動できるように方程式系を最適化に緩和する手法を文献 4) で提案した．. 3. 高次元アプローチによる対話的可視化手法. ˜ 1/2 は Λ から負の固有値を含む列を取り除き、成分ごとに平方根をとった n × d 行列であ Λ. 本節ではまず Kruskal らによる多次元尺度法を用いたグラフ配置を求める手法について. る．ここで X の k 行目の行ベクトル xk = (xk1 , . . . , xkd ) はノード k の d 次元空間での位. 述べ，次にこれを利用した細部の対話的グラフ可視化手法について説明する．. 置ベクトルを表している．通常では固有値の大きい方から少数個だけ用いてそれらに対応す. 3.1 Torgeson の方法による高次元グラフ配置 Kruskal らは多次元尺度法である Togerson の方法. る座標成分を利用する．例えば d = 2 とすれば，これは固有値の大きい方から二番目まで 13). を用いて，連結な一般無向グラフ. のみを利用することを意味し，(xk1 , xk2 ) が対応する配置となる．細部は d として固有値が. の二次元空間のグラフ配置を求める手法を提案した11) ．多次元尺度法とはオブジェクト間. 正となるものをすべて利用することで，グラフの高次元空間での配置を得た．. の関係性を基にして，その関係性をできるだけ保持するような多次元空間でのオブジェクト. 一般的にグラフ理論的距離に基づく距離行列 D に対して Togerson の方法を用いると，固. 配置を求める統計的手法である．Togerson の方法ではオブジェクト間の関係性として距離. 有値が正となるものは比較的多く，結果として高い次元でのグラフ配置を得ることができ. の公理を満たすものを用いて多次元空間の配置を求める．今，オブジェクトの数を n とし，. る．いくつかのデータを用いて固有値が正となる数を調べたのが表 1 である．固有値が極端. 各オブジェクト間の距離を表す距離行列を D = (dij ) とする．Kruskal らは距離としてグラ. に 0 に近いものは除いており，値が 10−6 以上の数を数えた．用いたデータは Zachary の. フ理論的距離を用いており，ここでの dij はノード i からノード j への最短のステップ数で. Karate club と文献 10) で用いられいる mixi の友人関係におけるクラスタ構造，そして文. ある．そして D = (dij ) から以下のような計算をして行列 A = (aij ) を得る．. 献 3) で用いられている三種類の AT&T のネットワーク（ug 166,ug 263,ug 380）である．それぞれノード数の半数以上の数の固有値が正となっており，結果として高次元空間でのグ. 2. c 2012 Information Processing Society of Japan ⃝.

(3) Vol.2012-HCI-146 No.6 2012/1/19. 情報処理学会研究報告 IPSJ SIG Technical Report. 明する．細部はノードの移動に応じて e1 , e2 が張る射影平面を，移動するノードに関する. ラフ配置が得られていることが分かる．. ベクトルを加えた三次元空間内で回転移動することで実現した．ここで回転に関する回転軸表 1 高次元配置による次元 Table 1 Dimensions of high-dimensional layouts. は三次元空間ではなく元の射影平面である二次元平面内に取っていることに注意されたい．そしてノードの移動による射影平面の回転移動を決定するために，新しい射影平面を張るベ. ノード数. エッジ数. 高次元配置の次元. Karate club. 34. 78. 22. 以下手法の詳細を述べる．最初に入力となる定数を定義する．現在の射影平面を張る正規. mixi. 158. 680. 97. 直交ベクトルを e1 , e2 とし，ユーザが移動したノード k の高次元空間での位置ベクトルを. ug 166. 71. 74. 61. ug 263. 141. 162. 125. ug 380. 1104. 3231. 698. クトルが満たす制約式を構成し制約解消を行う．. ′ ′ xk とする．可視空間でのノード k の移動前の座標を (wk1 , wk2 )，移動後の座標を (wk1 , wk2 ). とする．ここで xk を e1 , e2 によって正規直交化して得られるベクトルを e0 とする．e0 は以下のように求められる．. e0 = f 0 /||f 0 ||, f 0 = xk − wk1 e1 − wk2 e2 定義より ||f0 || =. 3.2 二次元平面への配置と更新. √. 2 2 ||xk ||2 − wk1 − wk2 である．e0 と e1 , e2 が線形従属となる場合を避け. るために ||(wk1 , wk2 )|| < ||xk || を仮定して移動の制限をしている．また同じノードを続け. 細部は多次元尺度法によって得られたグラフの高次元配置を二次元平面へ射影することに. ′ ′ て移動できるように ||(wk1 , wk2 )|| < ||xk || も仮定する．. よって可視空間でのグラフ配置を得た．そしてユーザーが可視空間内でノードをマウスド. そして現在の射影平面を，e0 , e1 , e2 で張られる三次元空間でノードの移動に応じて回転. ラッグによって移動したとき，その移動に応じて高次元空間から二次元平面への射影を更新. させる．回転移動によって得られる新しい射影平面を張るベクトルは e′1 ，e′2 を６つの変数. することで対話的に可視空間でのグラフ配置を変えることを可能にした．ここでは二次元平. a10 , a11 , a12 , a20 , a21 , a22 を用いて e0 , e1 , e2 の線形結合で表すことができる．. 面への射影の方法とその更新方法について説明する．. e′1 = a10 e0 + a11 e1 + a12 e2. ノード k の高次元空間での位置ベクトルを xk = (xk1 , . . . , xkd ) とする．最初の射影のた. e′2 = a20 e0 + b21 e1 + b22 e2. めに正規直交なベクトル e1 , e2 を以下のように A の固有値である λi を用いて高次元空間. 元の射影平面から新しい射影平面への回転移動の軸 r は元の射影平面内に取るので，二つ. 内にとる．. の変数 b1 , b2 を用いて. e1 = f 1 /||f 1 ||, e2 = f 2 /||f 2 ||. r = b1 e1 + b2 e2. f 1 = (λδ1 , 0, λδ3 , 0, . . .), f 2 = (0, λδ2 , 0, λδ4 , . . .). と表せる．以上の変数と定数を用いて以下の三種類 8 つの制約を構成する．. そして xk を e1 , e2 によって張られる二次元平面へ射影する．射影先である二次元平面. ′ ′ xk · e′1 = wk1 , xk · e′2 = wk2. でのノード k の座標は (xk · e1 , xk · e2 )⋆1 で与えられる．f 1 , f 2 の中で現れる δ は正の実. ||e′1 || = 1, ||e′2 || = 1, e′1 · e′2 = 0, ||r|| = 1. 数の値を取るパラメータであり，δ の値が大きくなるほど高次元の座標成分の影響が低下す. r · e1 = r · e′1 , r · e2 = r · e′2. る．特に λ1 > λ3 かつ λ2 > λ4 ならば，δ → ∞ のときの極限は 3.1 節での d を 2 とした. 一行目はノードの移動に関する制約で，二行目は新しい射影平面を張るベクトルが正規直交. ものに収束し，Kruskal らの手法で求まる二次元グラフ配置に相当する．δ の適切な値の決. であることと回転軸の長さに関する制約，そして三行目は回転軸への射影は回転移動によっ. 定は一般には困難なので，δ = 1/2 と固定の値にしている．. て変化しないという回転に関する制約を表している．制約式には二次の等式制約が含まれて. 次にユーザが可視空間でノードを移動したとき，どのように射影を更新するかについて説. いるが，変数の数と制約式の数が一致しているのでニュートン法のような基本的な連立非線形方程式の数値解法によって解くことができる．この方法では最初に求めた高次元配置を変. ⋆1 本稿では · はベクトルの内積を表し，列ベクトル，行ベクトルの任意の組み合わせに対して用いる．. 3. c 2012 Information Processing Society of Japan ⃝.

(4) Vol.2012-HCI-146 No.6 2012/1/19. 情報処理学会研究報告 IPSJ SIG Technical Report. ここで細部の手法における射影平面の回転移動が一般の次元ではどうなるか考える．細部. 更する必要はないため，ノードの移動に応じて高速に二次元グラフ配置を更新することがで. の手法では三次元空間における射影平面の回転移動に対して回転軸を定義していた．この回. きる．. 転軸を回転によって不変な空間と捉える．二次元空間での回転では回転によって不変な空間. 4. 射影に基づく対話的グラフ配置. は回転の中心，すなわち零次元である．三次元空間での回転では回転によって不変な空間は. 本節では提案手法について説明する．3.2 節で述べた細部の手法では射影先の可視空間と. 回転の軸，すなわち一次元である．このように次元が上がれば回転によって不変な空間の次. して二次元空間を採用しており，ノードの移動に応じて射影平面を回転移動することで射影. 元も一緒に上がる．よって (dL + 1) 次元での回転では (dL − 1) 次元の回転によって変化し. の更新を行った．これによってユーザが対話的に可視空間内でのグラフ配置を変更すること. ない空間が存在するはずである．この考えをもとに新しい射影ベクトルと回転移動に関する制約式を定義する．移動前の. を可能にした．我々はこの手法を可視空間として二次元に限らず，一般の次元でも扱えるよ. ノード k の可視空間での位置ベクトルを q L = (wk1 , . . . , wkdL )，移動後の位置ベクトルを. うにする方法を提案する．. ′ ′ q ′L = (wk1 , . . . , wkd ) とする．また現在の射影行列を P = (e1 , . . . , edL ) とし，新しい射 L. Torgerson の方法によって得られた高次元空間の次元を dH ，高次元空間からの射影先で. 影行列を P ′ = (e′1 , . . . , e′dL ) とする．q ′L は q H と P ′ の積で求まる（q ′L = q H P ′ ）．. ある可視空間の次元を dL と表すことにする．そして可視空間である dL 次元空間を張る最. 新しい射影ベクトル e′1 , . . . , e′dL をそれぞれ (dL + 1) 個の変数 αij を用いて e0 , . . . , edL. 初の正規直交ベクトル e1 , . . . , edL をとする．e1 , . . . , edL は以下のようにベクトルの成分として Torgerson の方法の途中で得られた A の正の固有値の平方根を (dL − 1) 置きに取る. の線形結合で表す．. ように定義する．. ei = f i /||f i || f i = (0, . . . , 0,. √. | {z } i−1. λi , 0, . . . , 0,. e′i =. √. | {z }. λi+dL , 0, . . . , 0, . . .). | {z }. dL −1. T. αij ej. (1 ≤ i ≤ dL ). j=0. (dL + 1) 次元での回転によって不変な空間の次元は (dL − 1) 次元である．回転によって. dL −1. このように定義すると ||ei || = 1 であり，異なる i, j に対して ei · ej = 0 となり. dL ∑. L {ei }di=1. 不変な空間を張る正規直交ベクトルを r 1 , . . . , r dL −1 とし，それぞれ (dL − 1) 個の変数 βij. は正規直交系となる．この ei を射影ベクトルと呼び，ei を順番に並べた n × dL 行列. を用いて e1 , . . . , edL の線形結合で表す．. P = (e1 , . . . , edL ) を射影行列と呼ぶことにする．ノード k の高次元空間での位置ベクトルを q H = (xk1 , . . . , xkdL ) とすると，可視空間での k の位置ベクトル q L は以下のように q H. ri =. と P の積で書ける．. dL ∑. βij ej. (1 ≤ i ≤ dL − 1). j=1. q L = q H P = (q H · e1 , . . . , q H · edL ). 前節でも述べたが，回転によって不変な空間は実際の回転移動を考える (dL + 1) 次元では. この射影行列 P ，すなわち e1 , . . . , edL を可視空間でのノードの移動に応じて更新すること. なく元の可視空間内である dL 次元内にとる．これは細部の手法のアイディアをそのまま踏. で可視空間でのグラフ配置を変更する．ノードの移動を反映させるために以下のようにして. 襲している．新しく定義した e′1 , . . . , e′dL , r 1 , . . . , r dL −1 について以下の 4 種類の制約を与える．. q H を e1 , . . . , edL で正規直交化して得られるベクトルを e0 とする． e0 = f 0 /||f 0 ||, f 0 = q H −. dL ∑. ′ q H · e′j = wkj. e′i · e′j = δij. xkj ej. r i · r j = δij. j=1. r i · ej = r i ·. そして現在の可視空間を張るベクトル e1 , . . . , edL に e0 を加えた dL + 1 次元空間での回転移動を考える．. e′j. (1 ≤ j ≤ dL ). (1). (1 ≤ i, j ≤ dL ). (2). (1 ≤ i, j ≤ dL − 1). (3). (1 ≤ i ≤ dL − 1, 1 ≤ j ≤ dL ). (4). (1) は q H を新しい射影行列によって射影した座標が移動先の座標であるというノードの移. 4. c 2012 Information Processing Society of Japan ⃝.

(5) Vol.2012-HCI-146 No.6 2012/1/19. 情報処理学会研究報告 IPSJ SIG Technical Report d −1. L L 動の制約を表す．(2)，(3) の δij はクロネッカーのデルタであり，それぞれ {e′i }i=1 , {r j }j=1. d. が正規直交系であるということを表している．(4) は回転によって不変な空間への射影は回転移動によって変化しないという回転に関する制約である． L ここで変数と制約式の数について見る．{e′i }i=1 を表すために用いた変数は dL (dL + 1) 個，. d. L −1 {r j }dj=1 を表すために用いた変数は dL (dL − 1) で合計 2d2L 個の変数を必要とする．一方. 制約式の数は，(1) で dL 個，(2)，(3) については冗長なものを除くとそれぞれ (dL C2 + dL ) 個と (dL −1 C2 + dL − 1) 個の制約式があり，合わせると d2V 個になる．(4) からは dL (dL − 1) 個の制約式ができる．(1) から (4) の制約式の数を合わせると，dL + d2L + dL (dL − 1) = 2d2L となり，変数の数と一致する．制約式の種類も高々二次であり，細部の手法と同様ニュートン法のような数値解法によって解くことができる．なお以上において ||q L || < ||q H || と. ||q ′L || < ||q H || の仮定が必要となるが，理由は細部の手法の時と同様である．. 図 1 試作版 AGI3D Fig. 1 The prototype system AGI3D. 提案手法において可視空間の次元として dL = 2 とすると細部の手法に完全に一致する．よって提案手法は細部の手法の一般化になっていることが分かる．この一般化によって理論. 座標，z 座標を増減させることで移動する．. 的には可視空間として任意の次元に関して対話的なグラフ配置が定義できる．しかし可視化. 射影行列の更新の時に解く方程式系は GSL で提供されている非線形方程式のソルバーを. という観点から見ると，可視空間としての次元 dL は二次元と三次元が一般的である．射影先として四次元以上を取った場合の応用方法については今後の課題である．次の節では可視. 用いて解いている．本手法で出てくる方程式系は解付近でのヤコビ行列の行列式が 0 に近. 空間の次元として dL = 3 としたときの実装と実行結果を示す．. いため単純なニュートン法では解がうまく収束しない．よってそのような場合でも解が収束. 5. 実. する修正ハイブリッド法12) を用いている．方程式系を解くときの初期値は基本的には −1. 装. から 1 の間でランダムにとっている．ただし選択したノードが連続して動く場合には前の移動で求まった解を次の移動の初期値としている．. 本節では前節で提案した射影に基づく対話的グラフ可視化手法を用いて，可視空間を三次元とした試作システム AGI3D（Active Graph Interface 3D）を C と Java を用いて実装し. 6. 結. た．Java から C の関数が呼べるよう Java Native Interface（JNI）を用いており，数値計. 果. 算の部分は C の関数で行いグラフの表示の部分は Java が行なっている．C での数値計算に. ここでは実際のグラフのデータ描画した図と，ノードを動かした時の振る舞いについて検. は GNU の数値計算ライブラリである GSL-1.15（GNU Science Library）⋆2 を用い，Java. 証した結果を示す．表 1 に上げたデータのうち Karate club を除いた四つのデータに対し. での三次元描画の API として Java 3D-1.5.1⋆3 を用いた．図 1 は AGI3D の実行画面で，サ. てノードを移動した時のグラフの変化を観察した．図 2，図 3 はそれぞれは ug 166，ug 263 のグラフを描画したもので，図中で色が変わっ. ンプルとして Karate club のデータを表示している．ノードの移動はキーボード入力によって行う．まず移動したいノードをマウスクリックに. ているのが移動したノードを表している．共に一つのノードを選択し，図 2 では選択した. よって選択する．選択したノードは割り当てられたキーボードの入力に応じて，x 座標，y. ノードを下 (図 2(a)→(b))，左上 (図 2(b)→(c))，右（図 2(c)→(d)）の順に移動した様子を順に表示している．図 3 では選択したノードを左上（図 3(a)→(b)），下（図 3(b)→(c)），右（図 3(c)→(d)）の順に移動した．それぞれノードを動かしている時のグラフ全体の動き. ⋆2 http://www.gnu.org/s/gsl/ ⋆3 http://java3d.java.net/. を観察すると，グラフの構造そのものは大きく変化せずにノードの移動に応じてグラフの向. 5. c 2012 Information Processing Society of Japan ⃝.

(6) Vol.2012-HCI-146 No.6 2012/1/19. 情報処理学会研究報告 IPSJ SIG Technical Report. きが変わったり一種の回転をするような動きが見られた．. drawing, proceedings of the Asia Pacific Symposium on Information Visualisation, Sydney, Australia, Australian Computer Society, Inc., pp.15–20 (2005). 5) Hosobe, H.: Analysis of a high-dimensional approach to interactive graph drawing, proceedings of the Asia Pacific Symposium on Visualisation, Sydney, Australia, IEEE, pp.93–96 (2007). 6) Hosobe, H.: Numerical optimization-based graph drawing revisited, to appear in proceedings of the 5th IEEE Pacific Visualization Symposium, Songdo, Korea, IEEE (2012). 7) Kamada, T. and Kawai, S.: An algorithm for drawing general undirected graphs, Information Processing Letters, Vol.31, No.1, pp.7–15 (1989). 8) Koren, Y., Carmel, L. and Harel, D.: ACE: A fast multiscale eigenvectors computation for drawing huge graphs, proceedings of the IEEE Symposium on Infomation Visualization, Boston, MA, USA, IEEE, pp.137–144 (2002). 9) Koren, Y. and Harel, D.: Graph drawing by high-dimensional embedding, proceedings of the 10th International Symposium on Graph Drawing, Lecture Notes in Computer Science, No.2528, Irvine, CA, USA, Springer, pp.207–219 (2002). 10) 越田港，細部博史，脇田建：大規模社会ネットワークの階層的視覚化手法，コンピュータソフトウェア， Vol.28, No.2, pp.206–216 (2011). 11) Kruskal, J. and Seery, J.: Designing network diagrams, proceedings of the First General Conference on Social Graphics, Leesburg, VA, USA, pp.22–50 (1978). 12) Powell, M. J.D.: A hybrid method for nonlinear equations, chapter6, pp.87–114, Gordon and Breach (1970). 13) 齋藤堯幸，宿久洋：関連性データの解析法: 多次元尺度構成法とクラスター分析法.，共立出版 (2006).. 一方，図 4，図 5 は mixi，ug 380 の結果である．それぞれ最初の配置はノードが中心に集まっており，グラフの構造が複雑であることが分かる（図 4(a)，図 5(a)）．ここではそれぞれ中心に集まっているノードのうち三つを選択して中心から外に出すようなノードの移動を行った．mixi の図ではノードを動かすことによって最初は見えなかったハブの役割を果たすノードがノードの移動によって見えやすくなった．ug 380 の図では最初に一つのノードを中心から外に向かって移動した（図 5(b)）．そして移動したノードにつられて現れた構造を広げるような移動を行った（図 5(c),(d)）．これによってグラフの一部分を強調して表示することができた．これらの例ではどちらも最初の配置では見ることの出来なかった構造が移動によって見えるようになった．. 7. おわりに本稿では，無向グラフの対話的可視化手法として細部の提案した手法を拡張し，多次元尺度法に基づくグラフの高次元配置から任意の次元の可視空間に対して射影する方法とその射影の更新方法を提案した．またグラフの可視空間として三次元を採用した試作システムの実装を行い，いくつかのデータに対して実験し検証した．今後の課題としては提案手法内で用いた回転移動に関する幾何的な解釈について，より詳細な説明を与えることである．実装に関しての課題は，試作システム AGI3D をより対話的に扱えるようにすることである．現在ノードの移動はキーボードで行なっているが，ユーザがより操作しやすいようにノードの移動をマウスドラッグで行えるようにする予定である．また，様々な種類のグラフに対して本システムでノードの移動を行ったとき，それぞれどのような特徴があるのかについても調査する予定である．. 参. 考. 文. 献. 1) Eades, P.: A heuristic for graph drawing, Congressus numerantium, Vol.42, pp. 149–160 (1984). 2) Fruchterman, T. and Reingold, E.: Graph drawing by force-directed placement, Software: Practice and Experience, Vol.21, No.11, pp.1129–1164 (1991). 3) Hosobe, H.: A high-dimensional approach to interactive graph visualization, proceedings of the 19th Annual ACM Symposium on Applied Computing, Nicosia, Cyprus, ACM, pp.1253–1257 (2004). 4) Hosobe, H.: An extended high-dimensional method for interactive graph. 6. c 2012 Information Processing Society of Japan ⃝.

(7) Vol.2012-HCI-146 No.6 2012/1/19. 情報処理学会研究報告 IPSJ SIG Technical Report. (a). (b). (a). (b). (c). (d). (c). (d). 図 2 グラフ ug 166 の対話的配置 Fig. 2 Interactive layout of graph ug 166. 図 3 グラフ ug 263 の対話的配置 Fig. 3 Interactive layout of graph ug 263. 7. c 2012 Information Processing Society of Japan ⃝.

(8) Vol.2012-HCI-146 No.6 2012/1/19. 情報処理学会研究報告 IPSJ SIG Technical Report. (a). (b). (a). (b). (c). (d). (c). (d). 図 4 グラフ mixi の対話的配置 Fig. 4 Interactive layout of graph mixi. 図 5 グラフ ug 380 の対話的配置 Fig. 5 Interactive layout of graph ug 380. 8. c 2012 Information Processing Society of Japan ⃝.

(9)