題目 スフィアアンカーマップによる

平成

19

筑波大学第三学群情報学類

卒業研究論文

題目 スフィアアンカーマップによる 大規模

2

3D

主専攻

著者名 伊藤 隆朗

指導教員 田中二郎 三末和男 高橋伸 志築文太郎

要旨

2

そのため，効果的な描画手法の研究が盛んに行われており，特に大規模グラフの描画手法の開発が望 まれている．アンカーマップは，一部のノードを

2D

2D

本研究では，大規模グラフの描画の際に広い空間を確保するため，アンカーマップを

3D

2

3D

2

i

目次

第

1

1.1

Graph Drawing ... 1

1.1 2

1.2 2

1.3

1.3.1

1.4 2D

1.5

1.6

第

2

2.1 2

2.2 3D

2.3

2.4

第

3

3.1

3D

3.2

3.2.1 2D

3.2.2

3.2.3

3.3

3.3.1

3.3.2

3.3.3

3.3.4

第

4

4.1

4.2

4.3

4.4

4.4.1

4.4.2

4.5

ii

4.5.1 Circular

第

5

5.1

5.2

5.2.1

5.2.2

5.2.3

第

6

6.1

6.1.1

6.1.2

1

6.1.3

2

6.2

6.2.1

6.2.2

6.3 2D

第

7

謝辞 ... 51

参考文献 ... 52

iii

図目次

図 1

2

図 2

2D

図 3 アンカーマップの特徴 ... 4

図 4 2Dアンカーマップによる大規模

2

図 5 スフィアアンカーマップ ... 6

図 6 本研究の位置づけ ... 8

図 7 スフィアアンカーマップの利点... 9

図 8 力の制御 ... 15

図 9 フェーズ

1・2 ... 16

図 10 フェーズ

2・3 ... 17

図 11

3D

図 12 被写界深度レンダリング ... 22

図 13 ラベルの表示方法 ... 24

図 14

Circular

図 15

Circular

図 16 ツールの概観 ... 27

図 17

GraphML

図 18 ノード色・ラベルの設定 ... 28

図 20 アクセスログの可視化 ... 29

図 19

DBLP

図 21

GraphML

図 22 力制御法による自動レイアウト ... 30

図 23 配置探索法による自動レイアウト ... 31

図 24 スフィアアンカーマップの回転 ... 32

図 25 ズームイン・ズームアウト ... 32

図 26 焦点と被写界深度の調節 ... 33

図 27 焦点の操作 ... 34

図 28 ラベル表示の切り替え ... 34

図 29 アンカーの分散評価 ... 35

図 30 隣接するアンカー間の距離の標準偏差 ... 36

図 31 隣接するアンカー間の距離 標準偏差/平均 ... 36

図 32

G7

図 33 G9の可視化例 ... 43

図 34

G8

2D

3D

iv

図 35

G9

2D

3D

2D

1

第

1

1.1

Graph Drawing

情報可視化（Information Visualization）とは，コンピュータグラフィックスを活用して抽象的な データを人間が直接見ることができる形で表現し，人間のデータ理解を支援することを目的とした研 究分野である．

コンピュータサイエンスにおける可視化の研究には，科学技術計算の結果をコンピュータグラフィ ックスで表現する科学的可視化(Scientific Visualization)と呼ばれる研究分野がある．この技術を科 学技術分野だけではなく，より広い抽象的なデータを対象にした研究分野が情報可視化である．

抽象的なデータの関係や構造を表現するためにグラフがよく使われる．グラフを適切に可視化する ことにより，抽象的なデータの関係を人間が理解しやすいように表現することができる．しかしなが ら，データ量が多くなると人の手だけでレイアウトを行うことは困難となる．そのため，グラフを計 算機によって人間が理解しやすいように自動的に描く手法が求められており，情報可視化の中でも特 にグラフ描画問題(Graph Drawing)と呼ばれている．本研究は，このグラフ描画問題を研究対象とし ている．

1.1 2

顧客とその顧客の購入した商品，論文と著者，Web ページとそのページの閲覧者など，実社会の 様々なところで

2

2

2

2

グラフ：

G = ( V , E )

ノード：

V = A ∪ B

A ∩ B =

E ⊆ A × B

顧客とその顧客の購入した商品を例に挙げると，顧客をノードの集合 A の要素，商品をノードの 集合 B の要素とし，顧客とその顧客の購入した商品のノード間にエッジをつなぐことで，顧客と商 品との関係を

2

2

1.2 2

2

3

売り上げ数など細かな情報を読み取ることができるが，商品間の関係など関係構造の直感的な把握に 向いているとは言い難い．次に，(b)のような

2

2

2

図 1

2

オレンジ

ジュース 紅茶 コーラ ^りんご

ジュース お茶 ^野菜

ジュース コーヒー

A さん 0 1 0 1 2 1 0

B さん 3 2 0 4 0 3 0

C さん 2 0 11 0 0 0 5

E さん 4 2 2 1 2 0 1

F さん 0 2 0 2 3 0 0

(a)行列形式

(b)2

3

1.3

1.3.1

2

1

現在提案されているアンカーマップの描画手法は，

2

2D

スプリングモデルを利用して隣接するアンカーとの関係において適切な位置にレイアウトするもの である．これ以降，本論文では，アンカーに制約を課した

2

2D

2

図 2

2D

2D

z アンカーを基準としたフリーノードの位置の把握

フリーノードはスプリングモデルによって関連のあるアンカーの近傍にレイアウトされる．アンカ ーは等間隔に固定されているため，アンカーを基準としてそのフリーノードがどのあたりに位置する かを視覚的に把握することができる（図 3(a)）．

4

z アンカーとの関係に基づくフリーノードクラスタの把握

アンカーとの接続関係により，フリーノードをクラスタに分けることができる．そのようなクラス タの存在およびそれらがどのアンカーとの接続によって形成されるかを把握することができる（図

3(b)）．

図 3 アンカーマップの特徴

1.4 2D

図 4(a)は，

52

1137

210

697

(a)

(b)

5

図

4 2D

2

1.5

本研究は，大規模な

2

2D

2D

3D

3D

3D

2

(a)フリーノードクラスタの混合

(b)アンカー周辺の関係が読み取りづらい

6

図

5

1.6

本論文の構成は以下のとおりである．本章では，

2

2

3

3D

4

5

6

7

7

第

2

2.1 2

Fößmeierらは， 2部グラフの片方の集合のノードを直線状にレイアウトし，もう片方の集合のノー

ドを直線の上か下に制約を持たせない形でレイアウトするTwo-Sides Freeモデルを提案し，与えられ た2部グラフをTwo－Sides Freeモデルでエッジ交差なしにレイアウトすることはNP困難であるこ とを証明した[4]．また，

Zheng

2

One-Layer-One-Cluster

2

Two-Cluster

NP

[5]

_Newton

2

2

[6]

Giacomo

2

これに対し本研究は大規模2部グラフにおいて高い可読性を維持するための新たな表現方法を開発 するものである．

2.2 3D

Robertson

3D

つことのできる描画手法

Corn Tree

Corn Tree

Focus+Context

H3

Hong

Sugiyama

method

3D

2

な混雑を軽減する描画手法を開発した[10]．本研究はこれらと同様に

3D

2

Dwyer

2D

3D

要性を比較しやすくする描画手法を開発した[11]．

Marco

2D

3D

2D

3D

8

トすることで可読性を向上する描画手法を開発した[13]．これらは，複数の

2D

3D

2D

2.3

Ahmed

3D

や

2.5D

2

2

2.4

本研究の位置づけを図 6に示す．本研究は，2.1 で述べた

2

2.2

3D

図

6

9

第

3

3D

3.1

3D

本研究では

2D

2

2D

3D

3D

第一の試みとして円から球という拡張を行った．球状のアンカーマップであることから，このような 描画手法をスフィアアンカーマップと呼ぶ．

スフィアアンカーマップは

2D

1D

2D

図 7 スフィアアンカーマップの利点

(a)フリーノードクラスタ混合の解消

(b)アンカー間の関係表現の広がり

10

3.2

スフィアアンカーマップのレイアウト方法を開発するにあたり，美的基準の設定を行った．一般的 にグラフ描画問題では美的基準を設定しそれを満たすようなレイアウト方法を開発する．スフィアア ンカーマップの美的基準は，2Dアンカーマップで用いられている美的基準をもとに，スフィアアン カーマップに適合する形に拡張することによって設定した．

3.2.1 2D

まず，スフィアアンカーマップの美的基準のもととなる

2D

2D

z

(E1) [描画規約]

z

(E2) [描画規約]

円周上に等間隔（正多角形の頂点上）にレイアウトする．Fの要 素（フリーノード）は位置の制約を受けない．

z

(E3) [描画規則]

z

(E4) [描画規則]

z

(E5) [描画規則]

z

(E6) [描画規則]

このうち描画規約とは必ず守るべき制約であり，描画規則とは良い描画の基準となるものである．

3.2.2

スフィアアンカーマップの描画規約は以下の通りである．

z

(C1)直線配線：エッジを直線で描く

z

(C2)複合座標系：2

ウトする．Fの要素（フリーノード）は位置の制約を受けない．

p(n)をノードnの位置を表す

3

(式 1) p( a ) = r

a ∈ A

スフィアアンカーマップの特徴的な部分は

C2

11

現である．2Dアンカーマップでは

E2

3.2.3

スフィアアンカーマップの描画規則は以下の通りである．描画規則はスフィアアンカーマップの評 価基準やレイアウトの基準として利用するため式の定義を行った．

p(n)は ノ ー ド n の 位 置 を 表 す

3

{ a a a a

}

A =

,

,

, K ,

F = { f

, f

, f

, K , f

}

合をE，ノードnに接続するh個のノードの集合を

L( n ) = { l

, l

, l

, K , l

}

z

(R1)隣接ノードの近接化（=エッジ線長の最小化）

(式 2)

(

∑

∈

−

E f a

f a

,

) ( p ) (

p

z

(R2)同一のフリーノードを共有するアンカーの近接化

(式 3) ∑ ∑

∈ ∈ <

−

⎟ ⎟

⎠

⎞

⎜ ⎜

⎝

⎛

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ •

F

f l l f i j

j i

j

i

r

l l

), ( L

, 2

1

p ( ) p ( )

cos

z

(R3)

(式 4)

a

− a

≤

<

≤

1

min

12

z

(R4)

(式 5)

( )

( ) ( ( ) )

( )

( ) _∑ ( ( ) )

∑

∑

≤

<

≤

≤

<

≤

≤

<

≤

−

−

−

−

t j i

j i t

j i

j i t j i

j i j

i

d f f s

f f

d f f s f f

1

2 1

2 1

, d ,

sim

, d ,

sim

の最小化

( )

) L(

) L(

) L(

) , L(

sim f f

f f f

f ∪ ′

∩ ′

′ =

, ^d ( ^{f , f ′} ) ^{= p( f ) − p( f ′ )}

( ) _∑ ( )

≤

<

−

=

t j i

j

i

f

t f s t

1

, 1 sim

2

, ( ) _∑ ( )

≤

<

−

=

t j i

j

i

f

t f d t

1

, 1 d

2

R1

R2

R3

R4

E6

R4

2D

E4

3D

13

3.3

3.3.1

スフィアアンカーマップの可読性は主にアンカーのレイアウトで決まる．そのため，描画規則を満 足するようなアンカーのレイアウト方法が重要となる．

2D

1D

2D

そこで，本研究では

2

3

もうひとつは，アンカーをスプリングモデルの力の制御によって球面上に一様に分散させて配置候補 を決めた後，アンカーの位置を入れ替えながら描画規則の式の値を小さくようなアンカーのレイアウ トを探索していく方法である．

3.3.2

アンカーのレイアウト方法を述べる前に，スフィアアンカーマップのレイアウトに使用されるスプ リングモデルについて述べる．スプリングモデルは力指向アルゴリズムの一種である．グラフをスプ リングや電磁力の働くような力学モデルと考え，シミュレーションを行うことによりモデルの安定状 態を求めレイアウトを決定するものである．

スフィアアンカーマップ中では，

2

≠

3

14

(式 6)

) p(

) p(

) p(

) 1 p(

1)

rep( n n'

n' k n

n,n',k

−

= −

z スプリングの収縮力

(式 7) ^{spr( n,n',k 2 )} = ^{k 2} ( ^{p( n )} − ^{p( n' )} )

斥力は同じ電荷を持った荷電粒子が反発する際の振る舞いを表している．また，スプリングの収縮 力では描画規則

R1

0

各ノードに対してこれらの力の合力を計算し，そのノードを合力の方向に大きさに比例した微小な 距離だけ移動を行う．スフィアアンカーマップではアンカー，フリーノードに別の力の係数を用いて 計算を行う．ノードnの接続するノードの集合を

L(n )

ra,sa,rf,sf

z ノード

n

(式 8)

のとき 　　　

のとき 　　　

⎪ ⎪

⎩

⎪ ⎪

⎨

⎧

⎟⎟ ∈

⎠

⎜⎜ ⎞

⎝

⎛ +

⎟⎟ ∈

⎠

⎜⎜ ⎞

⎝

⎛ +

=

∑ ∑

∑ ∑

≠

∈ ∈

≠

∈ ∈

F n n,a,

n,f',

A n n,f,

n,a', n

n f F

f a

n a A

a f n

' ,

' L(n)

' ,

' L( )

) sf spr(

) rf rep(

) sa spr(

) ra rep(

) dis(

ε ε

以上の移動量を元に各ノードの位置を更新する．球の半径をrとするとき，ノードnの新しい位置 p’(n)は以下のように表すことができる．

z ノード

n

(式 9)

⎪ ⎩

⎪ ⎨

⎧

∈ +

+ ∈ +

=

のとき 　　　

のとき 　　

F n n

n

A n n

n

n r n

n

) ( dis ) ( p

) dis(

) p(

) dis(

) p(

) ( p'

アンカーは常に半径rの球面上に位置される．このプロセスを繰り返し，安定状態を求めることで スフィアアンカーマップのレイアウトを求める．

15

3.3.3

まず試みたのは，ノードの安定状態を見ながら力の係数

ra,rf,sa,sf

初期配置としてアンカーは球面のランダムな位置に，フリーノードは球内部のランダムな位置に配 置する．その後，スプリングモデルと力の制御によってレイアウトを求める．力の制御は，主に

3

1,2

3

図 8 力の制御

フェーズ

1

R1

R2

2

R3

フェーズ

1

スプリングは収縮しようとするためエッジ長の短い位置関係に配置される（図 9 上段）．

フェーズ

2

ランダム 配置

フリーノードを共有するア ンカーの近接化

アンカーを球面上に一

様にレイアウト 配置完了

rf ー rf=0 rf=0 rf>0

ra ー ra>0 ra>>0 ra>>0

sf ー sf>0 sf>0 sf>0

sa ー sa>0 sa=0 sa=0

安定 安定

16

響が無く，互いに反発するだけの状態となる．球面上への頂点分散のひとつとして頂点を荷電粒子と して各粒子のエネルギーを最小化するという指標があり[19]，フェーズ

2

図 9 フェーズ

1・2

フェーズ

1

2

1

ps

ps

z フェーズ

1

(式 10) ∑ dis ( ) ps

∈

<

A a

a

z フェーズ

1

ps

(式 11) ps = c A

c

0

フェーズ

2

sa=0

2

3

rf>0

初期配置 ランダムに配置

フェーズ１

フェーズ２

スプリングの力の 影響を受けフリー ノードを共有する アンカーは近くに レイアウトされる

フェーズ

1

アンカーへのスプ リング力を

0

17

リーノード同士を反発させて重なりをなくし，フリーノードクラスタを視覚的に確認できる形にレイ アウトする（図 10）．

図 10 フェーズ

2・3

フェーズ

2

3

2

1

2

ps '

さくなったときに行うこととした．

ps '

z フェーズ

2

(式 12) ∑ dis ( ) ps '

∪

∈

<

F A n

n

z フェーズ

2

ps '

(式 13) ps ' = c ' A ∪ F

c '

0

フェーズ

1

2

0

2

力制御法は，実装が容易であり，アンカーを球面上にレイアウトする場合だけではなく，半球や円 柱といった他の形状に制約を課した場合にも容易に応用が可能であると考えられる．しかしながら，

完全に自動的にレイアウトを行う場合にはスプリングモデル特有のノード振動によって安定状態に ならないことや，力の係数や安定状態判定の定数の決定が難しいといった問題がある．

フェーズ２ フェーズ３

フリーノード間の 斥力を働かせる

フェーズ2でフリーノードのレイ アウトもほとんど求められる

フリーノード同士の 重なりを無くす

18

3.3.4

次に試みたのは，2Dアンカーマップで用いられているアルゴリズムをスフィアアンカーマップ用 に拡張した方法である．まず，スプリングモデルの係数を常に

sa=0

アンカーの配置候補を決定したとしても，アンカーの配置パターンはアンカー数の階乗通りある．

また，アンカーの配置候補となる位置には球面上で歪みが生じているため，円順列のように回転など を考慮してパターンを減らすことができない．アンカーの数が多い場合，全てのアンカーの並びを評 価することは膨大な計算量を要する．そこで，2Dアンカーマップで用いられている配置探索アルゴ リズムを拡張しアンカーの配置の中から美的基準に関する準最適配置を探索する方法を考案した．

配置探索アルゴリズムでは，アンカーを適当な順番で探索していき，あるアンカーとそのアンカー から最も遠いアンカー（d番目に近いアンカー）の位置を入れ替え，ペナルティと呼ばれる基準を計 算し，アンカーを入れ替える前よりも小さくなっていた場合にその配置を採用する．全アンカーを探 索しても，このペナルティが減少しなくなった場合，

d

d

このような処理を

d=0

1

ペナルティには描画規則の

R1， R2， R4

3

R2

R2， R4

0

この方法は，実装が多少複雑になる一方，力制御法で問題となった係数の設定やノードの振動によ る安定判定の難しさといった問題を回避できるという利点がある．

19 Algorithm 1(C#2.0)

---

double oldPenalty = double.MaxValue;

while (p0 < oldPenalty)

{

int d = AnchorList.Count - 1;

oldPenalty = p0;

while (d > 0) {

//入れ替え対象のノードを設定

AnchorList.ForEach(delegate(GraphNode anchor) {

//近い順にソート

anchorNodes.Sort(delegate(GraphNode gn1, GraphNode gn2) {

return (int)Math.Sign((gn1.Position - anchor.Position).Length - (gn2.Position - anchor.Position).Length);

});

anchor.SwapNode = anchorNodes[d];

});

bool c = false;

do {

c = false;

for (int i = 0; i < AnchorList.Count; i++) {

GraphNode targetAnchor = AnchorList[i];

GraphNode swapAnchor = targetAnchor.SwapNode;

SwapPosition(ref targetAnchor, ref swapAnchor);

double p1 = penaltyFunction();

if (p1 < p0) {

p0 = p1;

c = true;

} else {

SwapPosition(ref targetAnchor, ref swapAnchor);

} }

} while (c);

d = d / 2;

} }

---

20

第

4

3D

4.1

2D

しかし，

3D空間上に効果的なグラフレイアウトが行えたとしても，人間に対しては最終的に2Dで

C. Wareらは「動き」や「立体視」は閲覧者の奥行き情報の読み取りを支援し，3D空間にレイアウ

21

4.2

レイアウトしたスフィアアンカーマップを

3D

3D

2D

3D

3

図 11

3D

4.3

閲覧者は，レイアウトしたグラフの回転とズームイン，ズームアウトを行うことができる．ある角 度では他のノードに隠れて見ることができないノードや圧縮されてしまった奥行情報も，別の角度か ら眺めることによって確認することができる．さらに，回転のアニメーションによって

3D

閲覧者はマウスドラッグによってレイアウトしたグラフを回転させることができる．スフィアアン カーマップの球の中心を回転の中心にしてドラッグの量に比例した量だけ回転を行う．

ズームイン，ズームアウトはカメラをスフィアアンカーマップの中心へと近づける（遠ざける）こ と（図 11の

z

x y

z z

上方向ベクトル (0,1,0)

向きベクトル

(0,0,-1) カメラ位置ベクトル (0,0,z) 画角

視錐台

スフィアアンカーマップ

22

回転やズーム以外にも，カメラの向きの変更やレイアウトしたグラフの平行移動などの操作も考え られるが，これらの操作と回転を同時に行うには複雑な操作体系が必要と考えられる．球の内部と周 辺にすべてのノードがレイアウトされるスフィアアンカーマップでは回転とズームで十分に構造を 把握できると考え，操作が複雑にならないよう他の操作は採用しなかった．そのため，カメラの上方 向ベクトル，向きベクトルは固定している。

4.4

4.4.1

C. Ware

3D

することを示した．しかし，本研究では立体視のような特殊な機材を使用せず一般的な

2D

被写界深度を用いたレンダリングは，立体視の概念とは異なるものであるが，奥行き関係の情報表 示として自然な表現であると考え採用した．奥行きによって色を変えるといった他の表現方法も考え られたが，そういった情報を付加するような表現は人間にとって不自然なものであると考え採用しな かった．

図 12 被写界深度レンダリング

焦点を手前のノードに合わせた例 焦点を中心付近のノードに合わせた例