動的ネットワークの 成長過程と差分の可視化手法

筑波大学大学院博士課程  システム情報工学研究科修士論文 

動的ネットワークの 

成長過程と差分の可視化手法 

石原 正樹 

（コンピュータサイエンス専攻） 

指導教員 田中二郎 

2007 年 3 月 

        概要  

動的ネットワークの変化を表現するために成長過程と差分を可視化する描画手法を 開発し，その有効性の評価を行なった．これまで，ネットワークの可視化手法は，ネッ トワークが変化しないことを前提としている場合が多かった．しかし，現実のネットワ ークは時々刻々と変化しており，このような動的ネットワークを対象とした成長過程や 差分の可視化手法の開発が課題であった．従来，動的ネットワークの成長過程や差分の 表現の多くは，複数枚の静止画や動画などを用いる．しかし，これら表現手法では，ネ ットワークの変化の認識を見る者自身に委ねてしまう問題がある． 

本研究では，動的ネットワークを対象として，その成長過程と差分それぞれの表現方 法に，時間一覧性と単一性の二つの性質を導入した新しい描画手法を開発した．時間一 覧性とは，表示していない情報の記憶を人間に強いないために，ある時点の表示像を切 り出してきても，必要な全期間の情報がその像に表示されていることである．また，単 一性とは，同一対象物に対する複数像間での同一性の判定を人間に強いないために，一 時には単一像だけが表示されることである． 

成長過程の表現手法として，「波紋表現」を開発した．これは，時間とともにネット ワークが成長してゆく過程を，エッジの長さに時間を対応付けて描画する可視化手法で ある．また，差分の表現手法として，「差分表現」を開発した．これは，前状態と次状 態の二つのネットワーク図を重ねて提示し，ノードの位置が移動したことによる差分を 矢印アイコン（ベクトル）で表現する可視化手法である．  

波紋表現と差分表現により，動的ネットワークの変化そのものを見る者に分かりやす く提示でき，今まで難しかった，1 枚のネットワーク図によるネットワーク構造の時系 列分析が可能となった．その適用例として，Weblog 記事のリンク関係の波紋表現と購 買履歴の差分表現を行なった．その結果，ネットワークに潜む「リンク構造の時間特性」

を表現できるようになった． 

目次 

第

1

... 1

1.1

... 1

1.2

... 1

1.2.1

... 1

1.2.2

... 2

1.3

... 2

1.3.1

... 3

1.3.2

... 3

1.4

... 3

1.4.1

... 3

1.4.2

... 3

1.5

... 5

1.6

... 5

第

2

... 7

2.1

... 7

2.1.1

... 7

2.1.2

... 7

2.2

... 8

2.2.1

... 8

2.2.2

... 8

2.2.3 2

... 8

2.3 Weblog

... 9

第

3

... 10

3.1

... 10

3.1.1

... 11

3.1.2

... 11

3.2

... 11

3.2.1

... 12

3.2.2

... 13

第

4

... 14

4.1

... 14

4.1.1

... 14

4.2

... 16

4.2.1

... 16

第

5

... 19

5.1

... 19

5.1.1

... 19

5.1.2

... 19

5.1.3

... 19

5.2

... 20

5.2.1

... 20

5.2.2

... 20

5.2.3

... 21

5.2.4

... 21

5.3

RippleTree ... 21

5.3.1

... 22

5.3.2

... 23

第

6

... 26

6.1

... 26

6.1.1

... 26

6.1.2

... 26

6.1.3

... 26

6.2

... 27

6.2.1

... 27

6.2.2

... 28

6.2.3

... 28

6.3

DiffGraph... 29

6.3.1

... 30

6.3.2

... 30

第

7

... 36

7.1

... 36

7.1.1 Weblog

... 36

7.1.2 Weblog

... 38

7.2

... 42

7.2.2

... 42

7.2.3

... 42

第

8

... 45

8.1

... 45

8.2

... 45

8.2.1

... 45

8.2.2

... 46

8.2.3

... 52

8.3

... 53

8.3.1

... 53

8.3.2

... 54

8.4

... 55

8.4.1

... 55

8.4.2

... 55

第

9

... 57

9.1

... 57

9.2

... 57

9.3

... 58

9.3.1

... 58

9.3.2

... 58

9.3.3

... 58

第

10

... 59

謝辞

... 60

参考文献

... 61

脚注

... 65

図目次 

図

1

... 4

図

2

... 6

図

3

... 12

図

4

... 15

図

5

... 17

図

6

... 20

図

7

RippleTree

... 22

図

8

RippleTree

... 23

図

9

... 24

図

10

... 25

図

11

DiffGraph

... 29

図

12

DiffGraph

... 30

図

13

Before Graph View... 31

図

14

After Graph View ... 31

図

15

Merged Graph View ... 32

図

16

... 33

図

17

... 33

図

18

... 34

図

19

... 35

図

20

... 36

図

21

... 37

図

22

... 38

図

23

Weblog

... 40

図

24

Weblog

... 40

図

25

Weblog

... 41

図

26

2006

8

1

12

1

... 43

図

27

2006

8

1

12

1

... 44

図

28

... 47

図

29

... 47

図

30

... 48

図

31

... 49

図

32

... 49

図

33

... 50

図

34

... 53

図

35

... 54

図

36

... 56

表目次 

表

1

... 10

表

2

... 46

表

3

... 46

表

4

... 51

表

5

... 52

表

6

... 54

第 1 章 序論

1.1 ^{可視化とは}

普段，我々は物事を図で理解をすることが往々にしてある．これは，人間が直接「見る」

ことのできないデータを，「見る」ことができる表現に変換することで，人間の理解や記憶と いった認知能力を視覚的に支援ができるためである．このように，「見る」ことができる表現 に変換することを可視化(Visualization)と呼ぶ．

コンピュータサイエンスにおける可視化の研究には，科学技術計算の結果をコンピュータ グラフィクス（

CG

(Scientific Visualization)

[1]

Web

その用途はデータマイニングや情報検索，ビジュアルインタフェースなど多様化している．

これに伴い，「用途に応じて，いかに分かりやすい表現を行なうか」という課題のもと，情報 可視化（Information Visualization）と呼ばれる研究が盛んに行なわれている

[2]

1.2 情報可視化とネットワーク

筆者はネットワークを可視化対象にした情報可視化手法について研究を行なった．ネット ワークの例として，

WWW

オブジェクトがノード（節点・頂点）に対応し，つながりがエッジ（経路・辺・リンク）に 対応している．エッジの性質は，有向と無向に分けられる．ノードやエッジの追加的な情報

（名前，ラベル，カテゴリ，時刻など）は属性として付属している．

1.2.1

一般に，情報可視化で対象とするデータには，株価や温度といった数値データの他に，プ ログラムコードや文書といったテキストデータ，会社組織やファイルといった階層構造を持 ったデータ，友人関係や

WWW

これらデータを可視化する表現手法は大きく分けて以下の５つに分類できる

[3]

(1)

:

(2)

:

(3)

:

(4)

:

(5)

:

これら表現方法の中で，座標系と行列系は比較的に表現方法が既に確立しているのに対し，

連結系や連結系およびそれらの複合系は，その描画法があまり発達していない

[4]

連結系の表現方法で対象としているネットワークのデータは，数値やテキストデータと比較 して， つながり や 関係性 といった一般に目に見えにくい構造情報が重要な意味を持っ ている．したがって，情報可視化の分野においてネットワークを可視化対象とした研究が特 に活発に行なわれている．

1.2.2

ネットワークを可視化する主な意義は，以下の

2

‚ ネットワークの全体像を俯瞰でき，直感的に要素間のつながりを捉えることが可能と なる．

‚ ネットワークから新たな発見や有用な情報を見つけ出せるようになる．

「百聞は一見にしかず」という諺の通り，人間は言葉による理解よりも，視覚的に理解す る場面が多い．ネットワークデータは，数値や文字データであり，コンピュータに解釈でき ても，人間には要素間のつながりを捉えることが難しい．そこで，ネットワークの要素を点 で表現し，要素間のつながりを線で表現するといった可視化を行なうことで，人間にとって 視覚的に分かりやすい表現形式に変換できる．これにより，人間はネットワークの全体像を 俯瞰でき，そして，認知能力を最大限に発揮できるようになる．

この人間の認知能力を利用してビジュアルデータマイニングや情報検索といった知的活動 が行える．例えば，友人関係のネットワークを可視化することで，ある友人間のつながりが 強いグループ（コミュニティ）やグループ間を仲介する重要な人物を素早く見つけ出せるよ うになる．

1.3 ^{動的ネットワークとは}

情報可視化研究において，近年は，「ネットワークは変化する」という前提で動的ネットワ ークの可視化手法も注目され始めている．以下に，変化するネットワークとその変化の理由 について述べる．

1.3.1

従来は，可視化対象のネットワークが変化しないことを前提とした，静的ネットワークの 可視化手法について主に研究されてきた．しかし，現実のネットワークは時々刻々と成長お よび変化している．このようなネットワークを「動的ネットワーク」と呼ぶ．動的ネットワー クとは，「時間経過に伴って構造（ノードおよびエッジの増減）や属性（関係性の強さ）が変 化するネットワーク」である．

1.3.2

なぜネットワークが変化するかということについては，ネットワーク科学の分野で研究が 進められているが，「ネットワークはそもそも成長を続ける」という前提に立脚してネットワ ークを分析することが重要とされている．

例えば，

Barabasi

ルフリーネットワークと呼ばれる現実の

WWW

1999

[5, 6]

また，

Watts

中で物事が起こるからということだけでなく，ネットワークそのものが，それを構成する要 素の活動や決定に突き動かされて，時とともに展開，変化するからだ．」と説明されている

[7]

1.4 動的ネットワークの変化を可視化する有用性

動的ネットワークを可視化するには，単純に従来の静的ネットワークの可視化手法を拡張 し，各時点のネットワークを可視化したネットワーク図を用意し，それを時系列に沿って並 べて提示する，もしくはアニメーションのように動画で提示することで実現できる．しかし，

動的ネットワークの可視化で最も重要なのは，「時間の前後関係で何が変化しているか」とい うことを観察者に分かりやすく提示することである．これにより「どういった傾向が読み取 れるか」という新しい知見を視覚的に抽出できるようになる．

1.4.1

具体的な動的ネットワークの例として，

Weblog

[8]

1.4.2

動的ネットワークの可視化では，静的ネットワークには無かった新たな可視化要素として，

「変化」が加わる．例えば，ネットワークを時間関数と見れば，その時間関数を各時刻にプ

ロットしたものが，その時点の静的ネットワーク図となる．このプロット（ネットワーク図）

をいくつか眺めることで，時間関数の性質（ネットワークの性質）が見えてくる．このよう に，ネットワークを時系列に沿って観察する際には，各時点のネットワークの静止画を時系 列に並べた提示手法と動画による提示手法が考えられる．前者は，いくつかのプロット点を 並べて観察し，後者はプロット点を連続的に繋いで観察を行なう手法に相当する（図

1

図 1 ネットワークの差分と成長過程の概念

以上のように，時系列にネットワークを分析する際に，前後関係から観察者が見比べて変 化（差分や成長過程）を発見するという認知的負荷を与えずに，変化そのものも可視化要素 として扱うことを本研究では行なう．

t1 t2 tn

t

ND(t)

t

⊿ND

ND(t

)+Σ⊿ND

ND(t2) ND(tn)

ネットワークの動き 

⊿ND

⊿t ND(t)

静止画を並べて提示する手法  t ND(t)

t

ND(t)  

動画で提示する手法 

1.5 ^{本研究の目的}

本研究では，より現実的な動的ネットワークを対象とし，その時間的な変化を適切な表現 で可視化する手法を開発する．すなわち，動的ネットワークを構成する要素が「いつ，何が，

どのように変化したのか」という観点から，分かりやすい可視手法を開発する．そして，変 化そのものを可視化することで，今まで見えなかった「ネットワークが持つ時間特性や傾向」

という新たな知見を明らかにする．

1.6 ^{本研究の貢献}

可視化手法を，その用途と可視化対象の性質で分類すると，図

2

斜線で示した部分が，本研究が対象とした可視化手法である．これまで，動的ネットワーク を対象とした可視化手法は，情報可視化分野においてあまり研究されてこなかった．本研究 では，この動的ネットワークを可視化対象とし，その変化を捉えやすい可視化手法を開発し た．この可視化手法を用いることで，観察者はネットワークの変化を認知する負荷から解放 できる．

また，動的ネットワークの変化である差分や成長過程を可視化することで，今まで行えな かったネットワーク構造の時間特性を分析することが可能となった．例えば，

CM

図 2 本研究で対象としている可視化手法（斜線部）

情報可視化 (Information Visualization) 科学的可視化 

(Scientific Visualization) 

動的 

ネットワーク可視化手法  数値データ可視化手法 

静的

動的ネットワーク  可視化手法 

静的ネットワーク  可視化手法 

可視化対象の性質

可視化手法の用途

第 2 章 関連研究

本研究が対象としている研究分野において，関連する研究や技術を以下に挙げる．

2.1

”

”

2.2

そして，

2.3

2.1

3

2.1 可視化対象に関連する研究

2.1.1

動的ネットワークの可視化ツールは，いくつか開発されており，その多くがアニメーショ ンによる提示やユーザの操作に対してインタラクティブに提示するものである．

鈴木らが開発した

Network Viewer [9]

4

ネットワーク上で情報が伝播するモデルの可視化に適用している．

また，

Moody

static flip book (

画

)

dynamic movie (

)

ャルネットワークの動的関係性を，ノード位置を固定し，エッジを積み重ねて提示する．後 者は，ノード位置を関係性の変化とともに移動させて提示する手法である

[10]

2.1.2

動的ネットワークを対象として，その変化を可視化対象とした研究は非常に少ない．

Erten

Aggregate Layout,

Merged Layout, Converging Iterations Layout

3

提案している．特に，

Aggregate Layout

Aggregate View

2

3

[11]

同様に，中園らは，時系列ごとのネットワーク図をレイヤーごとに管理し，観察者がスラ イダバーを操作することで，インタラクティブに各時点のネットワーク図を差分とともに提

示できる

Nel2

Erten

[12]

豊田らは，

Web

WebRelievo[13]

WebRelievo

トレンドを発見することに応用できると述べている．可視化技法の特徴は，差分とクラスタ の二つのビューを用意しており，各時間のグラフを時系列に並べて提示している．観察者は，

これらグラフを見比べることで，変化を捉えることができる．近年は，この手法を用いて，

Web

Web

[8]

2.2 可視化手法に関連する研究

2.2.1

木構造の視覚化に関して，これまで多くのシステム開発や研究が行われてきた．代表的な 木構造表現手法に，

Hyperbolic Tree[14]

また他にも，木構造の階層に注目し，画面空間の再帰分割で表現した

Tree-Maps[15],

[16]

Information

Cube[17]

効である．つまり，情報をカテゴライズして捉えるのに有効な表現手法である．

Ka-Ping Yee

[18]

2.2.2

John V. C.

ている

[19]

[20]

と「時間軸の進行方向や時間的関連性」の二つの観点を問題視し，これらを解決している．

2.2.3 2部グラフの可視化手法

2

G

V(G)

2

2

(Anchored Map)

この描画スタイルにより，アンカーノードとフリーノード間の関係性の強さが位置（アンカ ーノードとフリーノード間の距離）により提示することができる

[21]

2.3 Weblog に関連する研究

Weblog

,

マイニング

[22],

[23, 24, 25]

[26]

Weblog

[27]

Weblog

[28,29]

特に，ネットワーク構造の時間特性に着目し，時系列に沿った

Weblog

[30]

第 3 章 視覚的表現

動的ネットワークの変化を可視化する際に，どのような視覚的表現を行えば分かりやすい か，要求される表現の性質について考察する．また，動的ネットワークの差分と成長過程の 二つの可視化手法において可視化すべき要素について述べる．

3.1 ^{視覚的表現への要求}

人間にとって動的ネットワークの変化を捉えやすい視覚的表現とは，以下の二つの性質を 満たす必要がある．

‚ 時間一覧性 

‚ 単一性 

これらについて以下に詳しく述べるが，端的に表現すれば，「

1

1

表 1 提示手法の分類 単一性  

不満足 満足

不満足

3

インタラクティブ提示手法

時間一覧性

満足

各時刻の図を並べた 複数枚の図による提示手法

時間軸を座標系に導入した

1

Aggregate View [11]

など

波紋表現，差分表現

WebRelievo [13]など

Static flip book [10]

Nel2 [12]

Network Viewer [9]

dynamic movie [10]

3.1.1

時間一覧性とは，表示の切り替えや，表示していない情報の記憶を人間に強いないために，

ある時点の像を切り出して来ても，必要な全期間の情報とその情報に付随するタイムスタン プがその像に表示されていることである．

3次元画像による提示手法： 不満足

3

3

1

3

2

動画やインタラクティブ操作による提示手法： 不満足

自動もしくは，スライダバーなどの

GUI

時間情報が反映された静止画による提示手法： 満足

時間情報が反映された静止画を提示することで，変化の過程を一覧して提示できる．時間 軸を座標系に導入した静止画と，各時刻の静止画を並べて提示する

2

3.1.2

単一性とは，同一対象物に対する複数像間での同一性の判定を人間に強いないために，一 時には単一像だけが表示されることである

[31]

各時刻の図を並べた複数枚の静止画による提示手法： 不満足

各時刻の静止画を比較することで， 間違い探し のように変化を認知する．しかし，複数 枚の静止画が必要となり，その枚数が増えるに従って，動画と同様に，記憶による認知的負 荷が増大してしまう．

時間軸を座標系に導入した１枚図による提示手法： 満足

時間軸を座標系に導入した

1

1

表現する時間を必要としない．

3.2 ^{表現すべき要素}

1

3.1

を満たした可視化手法が表現すべき要素について以下に述べる．

3.2.1

グラフの差を

1

トポロジに関する差は，ノードの増減およびエッジの増減である．トポロジの差だけに着 目すれば，要素（ノードおよびエッジ）の増減を表現するだけであるので，容易である．一 方のグラフを基準にすれば，増加した要素，減少した要素，変わらない要素の

3

Web

[13]

視覚的にグラフを表現した場合には，トポロジカルな観点だけでなく，ジオメトリックな 観点も重要である．ネットワークの視覚的表現には，その目的によっては，トポロジカルな 情報だけでなくジオメトリックな情報の表現をも重視するものも少なくない．つまり，重み の付与されたエッジによって表現されたノード間の関連性の強さを，視覚的に表現するもの も多い．

ジオメトリに関する差は，ノードの移動およびエッジの変形である．トポロジの変化やエ ッジに付与された重みの変化によって，ノードの位置やエッジの形状が変化する可能性があ る．このようなジオメトリックな差は色では表現できないため，トポロジの差の表現のよう に単純ではない．

図 3 トポロジ変化とジオメトリ変化 エッジ追加 ノード追加

ノード削除 エッジ削除

(a)トポロジ変化（構造変化）

(b)ジオメトリ変化（レイアウト変化）

移動

3.2.2

時間一覧性の「時系列の変化を一覧して表現する」ために，成長過程の可視化には差分の 表現要素であるトポロジとジオメトリ変化の他に，各時点の状態を一連に表現する必要があ る．

差分では，トポロジとジオメトリの変化の前後関係で異なることが分かればよかったので，

色や形状で表現する場合には，

2

第 4 章 動的ネットワークの変化の提示手法

時間一覧性と単一性を満たした動的ネットワークの変化の提示手法として，差分と成長過 程の可視化手法を提案する．なお，本章ではそれぞれの可視化手法の概要と利点などを述べ るにとどめる．詳しい説明は

5

6

4.1 ^{成長過程の可視化手法}

ネットワークの構造と時系列の変化を同時に表現するために，グラフレイアウトに時間情 報を反映させるアプローチを取った．具体的に時間情報を反映させる描画要素として，エッ ジ長，ノードの色，ノードの大きさなどがあるが，ここでは，観察者が変化を最も認知しや すいジオメトリ要素（レイアウト要素）の，エッジ長に時間情報を対応付けた．この動的ネ ットワークの成長過程の可視化手法を「波紋表現」と名づけた．

4.1.1

新しい情報を中心に配置し，その情報がもつ時刻（履歴）が古くなるのに従って，中心か ら離れて行くという波紋の特徴を利用した表現手法「波紋表現」を提案する．対象とするデ ータ構造は，木と同様であるが，表現の方法が次の二点で違いがある．

‚ 最新の情報は，親ノードの近傍に配置される．

‚ 子ノード間の関係は，親ノードからのエッジ角度で表現される．

波紋表現のコンセプトは「新しいものは近くに，古いものは遠くに配置する」ことである．

これは，波紋が広がる特徴を利用しており，ゆえに波紋表現と呼ぶ．

系統図に代表されるように，従来の木構造の時系列階層表現は図

1(a)

C-F

(b)

(a)時系列階層表 (b)波紋表現 図 4 木構造の時系列階層表現と波紋表現との比較

特徴

波紋表現は，時系列階層表現と比較して階層の順番が異なっている．木構造の時系列階層 表現の場合，ルートからリーフ方向へ向かって古い時刻から新しい時刻へと順番に配列され る．一方，波紋表現では，各部分木の一番古いリーフの時刻から親ノード（中心）に向かっ て新しくなってゆくように配置される．ただし，親ノード位置のみノード生成時刻とする．

すなわち，時系列階層の並びが時系列階層表現と逆になっているのが特徴である．

自然界にも波紋や木の年輪のように，波紋表現と同様の時系列の並びを様々な場所で見る ことができる．基本的に，時間の経過とともに成長する性質を持つものが，こうした時系列 階層の形をとる．年輪の間隔は成長周期の

1

波紋表現においても，各波紋の周期はすべて同じである．この表現では，波紋とノードが 同期しており，ノードの生成時刻と波紋の発生時刻が同じである場合，波及してゆくその波 紋上にそのノードが配置される．波紋の中心には，親ノードが配置され，ある一定間隔で同 心円状に波紋が発生する．すなわち，同一波紋上にあるノードは，すべて同じ時刻に発生し たノードを表している．

利点

波紋表現では，各波紋の周期が分かれば，ある時点から最も古い時間までの履歴を視覚的 に把握することが可能となる．さらに，波紋の周期を変化させることで，様々な時間周期で 情報を整理することができ，情報のもつ周期性や出現頻度といったことが分析可能となる．

木は，閉路をもたないグラフである．さらに，ルートを決めた場合，階層をもった有向木 となる．例えば，組織図の場合には，各階層は組織の単位を表し，系統図の場合には，年代 を表す．有向木を時系列階層で表現した場合，最新の情報は常に最下層に配置される．一方，

B

C

D

E

G

2003 2004

2005

2005

2004 2005

A 2003 F

A

B C

F D

G

2004

E 2005

波紋表現の場合は，最新情報は常に親ノードから見て最上層に配置される．すなわち，最新 の情報を知りたいときは波紋の発生点（親ノード）の近傍に注目するだけでよい．

波紋表現では，木の構造上，表現することができなかった，リーフ同士のリンク関係を角 度として表現できる．例えば，図 4

(a)

F

C

(b)

[32]

も視覚化することが重要である．

適用限界

波紋表現は，閉路のないグラフ構造すなわち木のみ表現可能である．また，表現すべき要 素の，ジオメトリックな変化は，そもそも時間的変化をレイアウトに反映させてしまってい るため，表現ができない．したがって，波紋表現で表現できるのは，トポロジ変化（グラフ 要素の増加）とその時間的変化の表現のみである．

4.2 ^{差分の可視化手法}

ネットワークの差分を表現するために，二つのグラフを重ねて表示するマージグラフを利 用する．グラフの物理モデルに

Spring-Embedding [33]

と名づけた．

4.2.1

差分表現では，二つのグラフを重ねることで，トポロジの変化とジオメトリの変化を表現 できる．具体的に，ある時刻tのグラフ

G

t+1

G

5(c)

G

G

G

G

G

G

仮想的に自然長

0

一方，追加によるトポロジ変化があった

G

c,

Bc,

Dc,

Bb,

Ab

この追加によるトポロジ変化と削除によるトポロジ変化（エッジ

Cb

G

G

b

b

は追加要素ではないが，トポロジ変化の結果として現れるジオメトリ変化のグラフ要素であ る．このグラフ要素は，

G

G

G

b

G

b

さらに，以上のようなルールを用いてトポロジ変化とジオメトリ変化をマージグラフにて 分かりやすく提示できるように，グラフ

G

G

図 5 差分表現 利点

エッジのトポロジの変化がそのままジオメトリ変化に反映され，その結果，ノードの移動 ということに帰着できる．また，エッジの長さも関係性の強さを対応させることで，ジオメ トリ変化に反映できる．このように，ジオメトリ変化を統一的に移動ベクトルによって表現 できる利点がある．

また，ノードの追加というトポロジ変化は，マージグラフにおいて色の特異点を見つける だけという作業で，比較的簡単に追加ノードを見つけることが出来る．このような，特徴を 備えた差分表現により，例えば可視化対象のグラフが大規模となった場合に，従来は間違い 探しといった前状態と次状態の図の比較作業では，ジオメトリ変化要素とトポロジ変化要素 の発見が困難であったが，この作業から解放できる．

適用限界

マージグラフでは，トポロジ変化のノードおよびエッジの追加のみ表現可能である．例え ば，ノードの削除は，マージグラフでは上側に重ねる前状態のノードに隠されてしまい，表

(a) 時刻tのグラフG1

マージ

(b) 時刻t+1のグラフG2 (c) グラフG1とG2のマージグラフ

A

B

C

D

E F

A B

C

D

E F

+

エッジ

A

B

C

D

E a F

b

a

c b b

c

a

b

自由ノード 

現することができない．また，エッジの削除も同様である．したがって，トポロジ変化のう ち，グラフ要素の増加だけ表現可能である．

また，ジオメトリ変化は，前状態のグラフ要素の位置から変化であり，少なくとも前状態 のグラフ要素に

1

1

第 5 章 波紋表現

グラフの「成長過程」を

1

5.2

5.3

5.1

5.1 ^{描画スタイル}

5.1.1

描画対象は，時間情報をもった根付き木である．この根付き木はG=(V,E)で与えられ，エ ッジの集合E⊂V×V とノードの集合Vで構成されている．また，子ノードにリーフノードし か持たないノードを根とする部分木をG_subと表記する．さらに，根付き木の各ノードv∈V は 属性として生成時刻とカテゴリの二つの属性を保持している．したがって，Vは時系列デー タとなっている．また，vの生成時刻をd(v)と表記する．

5.1.2

ノードの配置規約

Gsubの波紋表現の配置規約は，同心円配置である．従って，G_subの入れ子構造であるGの 波紋表現の配置規約は，再帰的同心円配置となる．

エッジの配線規約

配線規約を，エッジの線種と配置規約の座標系との関係で説明する．まず，波紋表現のエ ッジの線種は，直線配線である．また，この配線は波紋表現の座標系と独立している．

5.1.3

波紋表現の描画規則について，意味的規則と構造的規則に分けて述べる．まず，ノードの 持つ属性による配置規約（意味的規則）として， 時間属性が新しいノードの集合を中央付近 に配置 が挙げられる．また，Gが持つグラフ理論的な概念や特徴に関係した配置規則（構 造的規則）に関しては，特に制約を設けていない．

5.2 ^{自動レイアウト}

5.2.1

図 6 波紋表現の座標系

ノードの位置は，図

6

エッジの長さと角度をパラメータとして各ノードの位置を決定する．例えば，vの位置p(v)は，

エッジの長さをl_v(t)，角度を

θ

θ

5.2.2

波紋の描画は，G_subの親ノードの位置を中心として，ある一定時間ごとに波紋を生成して いる．そして，ノードと波紋の描画位置が互いに一致している．すなわち，G_subの親ノード 以外のノードの中で最も古い時刻のノード（一番外側のノード）をvとすれば，その時刻

)

0 d(v

t = から波紋が発生する．また，子ノード位置と一致している波紋以外に，一定の時間 間隔ごとに波紋が発生している．このように波紋は，ノードの時刻と経過時間のスケールを 視覚的に理解できる役目がある．

Gsubの親ノードを中心とする波紋の集合を{c₁,c₂,L,c_n}とする．時刻tにおける時刻t₀に発 生した波紋（最も外側の波紋）c₁の半径r₁(t)は

(9)

f ，波長を

λ

( ) (

)

1 t f t t

r =

λ

(1)

このとき，描画される波紋の個数nは

(10)





=

λ

1(t

n r

(2)

l

(t) l

(t)

θ x

y p(v)= (l

(t), θ)

c 1

c 2

v

u

c i

w

0